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

配列では O(1) だが、単方向連結リストでは O(n) となる操作はどれですか。

1. A先頭の要素の削除
2. B先頭への挿入
3. C最初の要素の読み取り
4. Dインデックス i の要素へのアクセス

木において、兄弟（sibling）ノードとは何ですか。

1. A異なる部分木の同じ深さにあるノード
2. B同じ親をもつノード
3. Cあるノードとその親
4. D子をもたないノード

無向グラフにおいて、頂点の次数（degree）とは何ですか。

1. Aその頂点につながっている辺の数
2. Bグラフの頂点の数
3. Cその頂点からの最長経路の長さ
4. D隣接リストにおけるその位置

二分探索木のあるノードが右部分木をもっています。その通りがけ順での次のノード（後続ノード）はどこにありますか。

1. A右部分木の最も左のノード
2. B左部分木の最も右のノード
3. C常にその親
4. D常にその右の子

実行中のプログラムが、有効な関数呼び出しとそのローカル変数を管理するために使うデータ構造はどれですか。

1. Aフレームの二分探索木
2. B関数のハッシュテーブル
3. Cヒープメモリのキュー
4. Dコールスタック

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

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

ある動的配列は満杯になるとサイズを 2 倍にします。多くの実装が、半分ではなく 4 分の 1 まで減ったときにだけ縮小するのはなぜですか。

1. A配列をソートされた状態に保つため
2. B境界付近で push と pop が交互に起こるときに、サイズ変更が繰り返されるのを避けるため
3. C半分で半減させると要素が失われるから
4. Dメモリアロケータはブロックの 4 分の 1 単位でしかメモリを解放できないから

オープンアドレス法を使うハッシュテーブルで、削除に「墓標」（tombstone）マーカーがよく使われるのはなぜですか。

1. Aテーブルがソートされた状態になるから
2. B墓標がハッシュ計算を高速化するから
3. Cスロットを空にすると、他のキーの探査列が途切れる可能性があるから
4. D安全のため削除したキーを永久に保持する必要があり、スロットを再利用できないから