📖 講義スライド
ソート
開く ↗
📝 ソート・探索 (2014)
PDF ↗ 1
データ列 2, 6, 8, 3 を右のアルゴリズムにかける。結果を示せ
▶ 解答を表示
A. 2, 3, 6, 8
解説: 挿入ソートのアルゴリズム。A[3]=3をキーとし、3より大きい要素を後ろにシフトする。8>3なのでA[3]=8、6>3なのでA[2]=6、2<3なのでA[1]=3。結果: [2,3,6,8]
2
探索方法とその実行時間のオーダーの次の表を埋めよ 線形探索: n、2分探索: ア、ハッシュ探索: 1 実行時間: n、イ、1
▶ 解答を表示
A. ア: ハッシュ探索、イ: log n
解説: 線形探索: O(n)、2分探索: O(log n)、ハッシュ探索: O(1)（平均）
3
二分探索において、データの個数が8倍になると、最大探索回数はどうなるか？
▶ 解答を表示
A. 3回
解説: 2分探索の計算量はO(log n)。8倍になると log2(8n) = log28 + log2n = 3 + log2n。つまり3回増加する
4
511個の相異なる要素が昇順に整列された表がある。2分探索して該当するキーを取出す。キーの比較回数は最大何回か？ヒント: n=7の時、3回である
▶ 解答を表示
A. 9
解説: 2分探索の最大比較回数は⌈log2(n+1)⌉。511個の場合: ⌈log2512⌉ = ⌈9⌉ = 9回
5
右のフローチャートに、x=18, y=5を入れた時、rとqを求めよ
▶ 解答を表示
A. r=3, q=3
解説: ユークリッドの互除法を実装したフローチャート。x=18, y=5の場合: 第1回: 18≥5 → r=18-5=13, q=1; 第2回: 13≥5 → r=13-5=8, q=2; 第3回: 8≥5 → r=8-5=3, q=3; 3<5なので終了。r=3, q=3