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

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

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

単方向連結リストでは、最後のノードの next ポインタには何が入っていますか。

1. Aリストのノードの数
2. B前のノードのアドレス
3. C最初のノードのアドレス
4. Dnull（ノードなし）

スタックの一番上に要素を追加する操作の名前は何ですか。

1. Aプッシュ（Push）
2. Bエンキュー（Enqueue）
3. Cポップ（Pop）
4. Dピーク（Peek）

二分探索木で最小のキーはどのように見つけますか。

1. A根から左の子がなくなるまで左の子をたどる
2. B根から右の子がなくなるまで右の子をたどる
3. C根だけを見る
4. Dすべての葉を訪問して比べる

2 つのスタックでキューを実装します。「in」スタックに push し、「out」スタックから pop し、「out」が空になったら「in」から補充します。1 回の操作あたりのならしコストはどれですか。

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

後置記法の式 3 4 + 2 * の値は何ですか。

1. A11
2. B14
3. C24
4. D10

あるオブジェクトをハッシュマップのキーとして格納した後、そのハッシュ関数で使われるフィールドを変更しました。起こりうる結果はどれですか。

1. Aマップが自動的にキーを新しいバケットに移す
2. Bフィールドが変更された瞬間にマップがエラーを投げる
3. Cオブジェクトは古いハッシュのバケットにあるので、検索に失敗することがある
4. Dキーのハッシュはプログラムの開始時に 1 回しか計算されないので、何も変わらない

ヒープソートについて正しい記述はどれですか。

1. A追加の記憶領域として二分探索木を必要とするので、O(n) の追加メモリを使う
2. B安定で、O(n) の追加メモリを必要とする
3. C最悪 O(n log n) 時間でその場でソートするが、安定ではない
4. Dどの入力に対しても O(n) 時間で動作する