解答つきデータ構造ワークシート

無向グラフにおいて、頂点の次数（degree）とは何ですか。

1. A隣接リストにおけるその位置
2. Bその頂点からの最長経路の長さ
3. Cグラフの頂点の数
4. Dその頂点につながっている辺の数

最大ヒープ性（max-heap property）とは何ですか。

1. Aキーが左から右へソートされている
2. Bすべての葉が最大のキーをもつ
3. Cすべての親のキーがその子のキー以上である
4. Dすべての左の子のキーが右の兄弟のキー以上である

ハッシュテーブルにおいて、衝突（collision）とは何ですか。

1. Aテーブルのメモリが不足すること
2. B2 つの等しいキーが 2 回格納されること
3. Cキーをまったくハッシュできないこと
4. D2 つの異なるキーが同じインデックスに対応すること

容量 n の配列に格納された循環キューで、インデックス i の次の位置はどのように計算されますか。

1. A2i + 1
2. B(i + 1) mod n
3. Ci + 1
4. D(i − 1) mod n

固定のアルファベットをもつトライで、長さ L の単語を探索するのにどれだけ時間がかかりますか。

1. A格納されている単語の数に関係なく O(L)
2. B単語の数を n として O(log n)
3. CO(L × n)
4. D単語の数を n として O(n)

オープンアドレス法を使うハッシュテーブルで、負荷率の最大値はいくつですか。

1. A2
2. B0.5
3. C最大値はない
4. D1

データベースがインデックスに通常の B 木ではなく B+ 木をよく使うのはなぜですか。

1. Aすべてのレコードが連結された葉にあるので、範囲の走査が効率的になるから
2. BB+ 木は平衡を保つ必要がないから
3. CB+ 木はデータを根にだけ格納するから
4. DB+ 木は二分の内部ノードを使うので、ディスクの読み取りが減るから

配列の各要素について、その右側にある次に大きい要素を、合計 O(n) 時間で求めたいとします。役立つ構造はどれですか。

1. Aすべての要素のハッシュテーブル
2. B答えを待っている要素を保持するスタック
3. C要素ごとに作り直す二分探索木
4. D要素のすべての組を保持するキュー