📖 講義スライド
ソート
開く ↗
ℹ️
注意: この年度では 「データ構造・ソート」 として統合試験になっています。
📝 データ構造 (2013)
PDF ↗ 1
データ列 2, 6, 8, 3 を右のアルゴリズム（挿入ソートの1パス）にかける。結果を示せ。 アルゴリズム: k=A[3], i=3-1から、A[i]>kならA[i+1]=A[i], i=i-1を繰り返し、A[i+1]=kとする
▶ 解答を表示
A. 2, 3, 6, 8
解説: k=3, i=2。A[2]=8>3なのでA[3]=8, i=1。A[1]=6>3なのでA[2]=6, i=0。A[0]=2<3なので終了、A[1]=3。結果: [2,3,6,8]
2
アルゴリズムA「基準値についてデータ列を二つの組に分割し、それを再帰的に繰り返す」、アルゴリズムB「整列済みの列の正しい位置にデータを挿入していく」の名称として適切な組を選べ
ア A. クイックソート, B. 基本挿入法
イ A. マージソート, B. 基本挿入法
ウ A. ヒープソート, B. バブルソート
エ A. クイックソート, B. バブルソート
▶ 解答を表示
A. ア
解説: クイックソートは基準値(ピボット)でデータを分割、基本挿入法は整列済み部分に挿入していく
3
二分探索において、データの個数が8倍になると、最大探索回数はどうなるか？
▶ 解答を表示
A. 3回増える
解説: 二分探索の計算量はO(log n)。8倍→log2(8n) = log28 + log2n = 3 + log2n。つまり3回増加
4
次のオーダーを小さい順に並び替えよ。 n², 2ⁿ, n log n, n!
▶ 解答を表示
A. n log n, n², 2ⁿ, n!
解説: 計算量の大小: O(n log n) < O(n²) < O(2ⁿ) < O(n!)
5
次の関数f(x, y)において、f(330, 231)を求めよ。 f(x, y): if y = 0 then return x else return f(y, x mod y)
▶ 解答を表示
A. 33
解説: ユークリッドの互除法: f(330,231)→f(231,99)→f(99,33)→f(33,0)=33。330と231の最大公約数は33