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

有向グラフとは何ですか。

1. A相異なるすべての頂点対が辺で結ばれているグラフ
2. B閉路をもたないグラフ
3. C辺がある頂点から別の頂点への向きをもつグラフ
4. Dすべての辺が重みをもつグラフ

配列の要素はメモリにどのように格納されますか。

1. A1 つの連続したブロックに、順に並んで
2. Bメモリページの木の中に
3. Cハッシュで選ばれたランダムな位置に
4. Dばらばらに、ポインタでつながれて

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

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

V 個の頂点と E 本の辺をもつグラフについて、隣接リストはどれだけのメモリを使いますか。

1. AO(E²)
2. BO(V²)
3. CO(V + E)
4. DO(V × E)

平衡二分探索木でキーを探索する時間計算量はどれですか。

1. AO(log n)
2. BO(n)
3. CO(n log n)
4. DO(1)

配列に格納された二分最小ヒープ（インデックスは 0 から）において、インデックス i のノードの子はどこにありますか。

1. A2i + 1 と 2i + 2
2. B2i と 2i + 1
3. Ci/2 と i/2 + 1
4. Di + 1 と i + 2

基数木（radix tree、圧縮トライ）は通常のトライをどのように改良していますか。

1. A各単語を別々のノードではなく、根にあるハッシュテーブルに格納する
2. B各単語の最初の文字だけを保持する
3. C各ノードの子を頻度順にソートする
4. D子が 1 つだけのノードの連なりを、文字列でラベル付けされた 1 本の辺にまとめる

AVL 木にキーを挿入すると、あるノードの左部分木が高くなりすぎました。新しいキーはその左の子の左部分木に入りました（左左の場合）。どのような修正が適用されますか。

1. A子で左回転し、次にそのノードで右回転
2. B平衡が崩れたノードで 1 回の右回転
3. Cそのノードとその子の色を塗り替える
4. D平衡が崩れたノードで 1 回の左回転