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

デック（deque、両端キュー）とは何ですか。

1. A1 つの配列を共有する 2 つの別々のキュー
2. B両端での挿入と削除を許す構造
3. C末尾での削除だけを許すキュー
4. D優先度順に並べられたキュー

グラフにおいて、閉路（cycle）とは何ですか。

1. A同じ頂点から始まり同じ頂点で終わる経路
2. Bすべての頂点を訪問する経路
3. C辺をもたない頂点
4. D重みが 0 の辺

グラフは何で構成されていますか。

1. Aキーとハッシュ値のみ
2. B行と列
3. C辺（edge）で結ばれた頂点（vertex、ノード）
4. D根と葉のみ

無向グラフの隣接行列について正しいのはどれですか。

1. A常に上三角行列である
2. B主対角線に関して対称である
3. C主対角線には常に 1 が入っている
4. D各行にちょうど 1 つの 1 がある

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

1. Ai + 1 と i + 2
2. Bi/2 と i/2 + 1
3. C2i + 1 と 2i + 2
4. D2i と 2i + 1

ダイクストラ法が次に処理する頂点を選ぶために使う抽象データ型はどれですか。

1. A最小優先度付きキュー
2. BFIFO キュー
3. C順序のない集合
4. Dスタック

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

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

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

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