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

グラフの隣接リスト表現では、各頂点について何が格納されますか。

1. AV 個の真偽値からなる行
2. B他のすべての頂点への最短経路
3. C隣接する頂点のリスト
4. Dグラフの辺の総数

二分木を定義するものは何ですか。

1. Aすべてのノードがちょうど 2 つの子をもつ
2. B木がちょうど 2 つのレベルをもつ
3. Cすべてのノードが 2 進数を格納する
4. Dすべてのノードが高々 2 つの子をもつ

静的配列と動的配列の主な違いは何ですか。

1. A動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる
2. B静的配列は数値しか格納できない
3. C動的配列は、より大きなメモリブロックに移ることで拡張できる
4. D静的配列はインデックスによるアクセスが遅い

サイズ 7 のハッシュテーブルが h(k) = k mod 7 と線形探査法を使っています。10 を挿入した後、17 はどこに格納されますか。

1. Aインデックス 3
2. Bインデックス 0
3. Cインデックス 4
4. Dインデックス 6

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

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

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

1. A2^h+1 − 1
2. B2h + 1
3. Ch²
4. D2^h

単方向連結リストをその場で反転させる時間と追加領域のコストはどれですか。

1. A時間 O(1)、追加領域 O(1)
2. B時間 O(n)、追加領域 O(1)
3. C時間 O(n log n)、追加領域 O(1)
4. D時間 O(n)、追加領域 O(n)

ある AVL ノードは、その左の子の右部分木が高くなりすぎたために平衡が崩れています（左右の場合）。どのような修正が適用されますか。

1. A左の子で右回転し、次にそのノードで左回転
2. B左の子で左回転し、次にそのノードで右回転
3. Cそのノードで 1 回の左回転
4. Dそのノードで 1 回の右回転