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

重み付きグラフとは何ですか。

1. Aディスクに格納されたグラフ
2. B頂点より辺の方が多いグラフ
3. C各辺がコストや距離などの数値をもつグラフ
4. D辺の数が多いために、一部の頂点が他の頂点より重くなっているグラフ

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

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

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

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

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

1. A双方向連結リスト
2. B動的配列
3. C単方向連結リスト
4. Dソート済み配列

インデックス 0 から始まる配列に格納された二分ヒープで、インデックス i のノードの親はどこにありますか。

1. Aインデックス ⌊(i − 1) / 2⌋
2. Bインデックス i − 1
3. Cインデックス ⌊i / 2⌋ + 1
4. Dインデックス 2i + 1

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

1. A2i + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. Di + 1

赤黒木が満たさなければならない性質はどれですか。

1. A根は赤でなければならない
2. Bすべてのノードが赤でなければならない
3. Cすべての赤ノードの子は赤でなければならないので、赤ノードは葉まで途切れなく連なる
4. Dあるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい

配列のサイズ k のすべてのウィンドウの最大値を合計 O(n) で計算できる構造はどれですか。

1. A値の降順にインデックスを保持するデック
2. Bずらすことで更新するソート済み配列
3. Cウィンドウごとに作り直す最小ヒープ
4. Dウィンドウの要素の単方向連結リスト