📖 講義スライド
データ構造
開く ↗
ℹ️
注意: この年度では 「データ構造」 として統合試験になっています。
📝 データ構造 (2015)
PDF ↗ 1
次の順に到着するデータを二分木に登録する。最も検索効率が悪いものはどれか？ ア 27, 7, 51, 20, 6, 19 イ 19, 6, 20, 51, 7, 27 ウ 51, 27, 20, 6, 7, 19 エ 6, 7, 19, 27, 20, 51
ア 27, 7, 51, 20, 6, 19
イ 19, 6, 20, 51, 7, 27
ウ 51, 27, 20, 6, 7, 19
エ 6, 7, 19, 27, 20, 51
▶ 解答を表示
A. エ
解説: 二分探索木の検索効率が最も悪いのは、木が一方向に偏った場合。エの順序（6, 7, 19, 27, 20, 51）では、ほぼ昇順に並んでいるため、木が右に偏り、検索効率が線形時間O(n)に近くなる。バランスの取れた木ではO(log n)の効率が得られる。
2
ハッシュ関数 h を、h(x) = x mod 11 と定義する。次のデータの内、衝突が生じるものを挙げよ。 27, 7, 51, 20, 6, 19
▶ 解答を表示
A. 7, 51
解説: 各データのハッシュ値を計算:
- 27 mod 11 = 5
- 7 mod 11 = 7
- 51 mod 11 = 7 ← 7と衝突
- 20 mod 11 = 9
- 6 mod 11 = 6
- 19 mod 11 = 8
7と51が同じハッシュ値7を持つため衝突する。
3
データ 27, 7, 51, 20, 6, 19 が、先頭と末尾のポインタを持つ単方向リスト構造に格納されている。この時、ポインタを参照する回数が最も多い作業はどれか？ ア 27 を削除する。 イ 19 を削除する。 ウ 27 の次にデータ 33 を挿入する。 エ 19 の次にデータ 33 を追加する。
ア 27 を削除する。
イ 19 を削除する。
ウ 27 の次にデータ 33 を挿入する。
エ 19 の次にデータ 33 を追加する。
▶ 解答を表示
A. イ
解説: 単方向リスト: 27 → 7 → 51 → 20 → 6 → 19
ア: 27は先頭なので、先頭ポインタの変更のみ（1回）
イ: 19は末尾なので、19の前の要素（6）まで辿る必要がある（5回のポインタ参照）
ウ: 27の次に挿入するには、27を見つけて（1回）、その次のポインタを変更
エ: 19は末尾ポインタから直接アクセス可能（1回）
最も多いのはイの5回。
4
スタックだけを使って、1,2,3,4 の順に登録するデータを、3,2,4,1 の順序に並び替えよ。（並び替える操作を、「push 1, pop, push 2」等の様に回答せよ。）
▶ 解答を表示
A. push 1, push 2, push 3, pop, pop, push 4, pop, pop
解説: 操作の流れ:
1. push 1 → スタック[1]
2. push 2 → スタック[1, 2]
3. push 3 → スタック[1, 2, 3]
4. pop → 3を出力、スタック[1, 2]
5. pop → 2を出力、スタック[1]
6. push 4 → スタック[1, 4]
7. pop → 4を出力、スタック[1]
8. pop → 1を出力、スタック[]
出力順序: 3, 2, 4, 1
5
キューに関する操作 enq(A), enq(B), x = deq(), enq(C), enq(D), y = deq() を行った後、x, y を求めよ。
▶ 解答を表示
A. x = A, y = B
解説: キューの操作（FIFO: 先入れ先出し）:
1. enq(A) → キュー[A]
2. enq(B) → キュー[A, B]
3. x = deq() → Aを取り出し、x = A、キュー[B]
4. enq(C) → キュー[B, C]
5. enq(D) → キュー[B, C, D]
6. y = deq() → Bを取り出し、y = B、キュー[C, D]
したがって、x = A, y = B