実践問題
解答＆解説は第1問から第10問までを列挙しています。
まず問題を解いてから解答&解説を見ることを推奨します。
第1問
木構造において、子を持たない節点を表す用語として最も適切なものはどれか。
A. 根
B. 葉
C. 部分木
D. 親
解答＆解説はこちら
第2問
あるノードの番号を i としたとき、完全二分木を配列で管理した場合の右の子ノードの位置はどれか。（ただし、根ノードが1始まりの場合）
A. i + 1
B. 2i
C. 2i + 1
D. i / 2
解答＆解説はこちら
第3問
二分探索木において、各節点について成立する条件として正しいものはどれか。
A. 左部分木のすべての値は親より大きい
B. 左右の部分木の高さは必ず等しい
C. 左部分木の値は親より小さく、右部分木の値は親より大きい
D. 親ノードは常に最大値である
解答＆解説はこちら
第4問
二分探索木を中間順でたどったときに得られる並びとして正しいものはどれか。
A. 降順になる
B. 昇順になる
C. 根からの距離順になる
D. 葉から順になる
解答＆解説はこちら
第5問
次の木を先行順で走査した結果として正しいものはどれか。
40
/ \
20 60
/ \ /
10 30 50A. 10, 20, 30, 40, 50, 60
B. 40, 20, 10, 30, 60, 50
C. 10, 30, 20, 50, 60, 40
D. 40, 60, 50, 20, 30, 10
解答＆解説はこちら
第6問
ヒープに関する説明として最も適切なものはどれか。
A. 左部分木の値は常に右部分木より小さい
B. 中間順で走査すると昇順になる
C. 親ノードと子ノードの大小関係が保たれる
D. 各ノードの子は必ず2つである
解答＆解説はこちら
第7問
最大ヒープにおいて、根ノードにある値として正しいものはどれか。
A. 最小値
B. 最大値
C. 中央値
D. 葉ノードの平均値
解答＆解説はこちら
第8問
木構造における深さの説明として適切なものはどれか。
A. そのノードから葉までの最長距離
B. 根からそのノードまでの辺の数
C. そのノードの子の個数
D. 部分木の数
解答＆解説はこちら
第9問
あるノード数が n の木構造において、閉路を持たない連結グラフであるとき、辺の数はいくつか。
A. n
B. n - 1
C. n + 1
D. 2n
解答＆解説はこちら
第10問
次の説明のうち、二分木と二分探索木の違いとして正しいものはどれか。
A. 二分木では左右に大小関係が必要である
B. 二分探索木では各節点の子は最大3つである
C. 二分木は子の数、二分探索木は値の順序に特徴がある
D. 二分木と二分探索木は同じ意味である
解答＆解説はこちら
解答&解説
解答：第1問
正解：B
解説：
子を持たない節点を葉という。
根は最上位の節点。
解答：第2問
正解：C
解説：
完全二分木を配列で表すと、
- 左の子：
2i - 右の子：
2i + 1
親は ⌊i/2⌋。
解答：第3問
正解：C
解説：
二分探索木では
- 左部分木 < 親
- 右部分木 > 親
が成立する。
解答：第4問
正解：B
解説：
二分探索木では、中間順（左→親→右）でたどると昇順になる。
解答：第5問
正解：B
解説：
先行順は
親 → 左 → 右
順番は
40 → 20 → 10 → 30 → 60 → 50
解答：第6問
正解：C
解説：
ヒープは親子間の大小関係のみを保証する。
左右の兄弟間の順序までは保証しない。
解答：第7問
正解：B
解説：
最大ヒープでは親が子以上なので、根には最大値が入る。
解答：第8問
正解：B
解説：
深さは根からそのノードまでの辺の数。
※ 葉までの最大距離は高さの考え方。
解答：第9問
正解：B
解説：
木は閉路のない連結グラフであり、
辺の数 = ノード数 − 1
となる。
解答：第10問
正解：C
解説：
- 二分木：子が最大2つ
- 二分探索木：左右に大小関係がある
ここは応用情報で非常に狙われやすいポイント。
本試験で特に重要な3つ
- 中間順 → 昇順（ただし二分探索木）
- 完全二分木 → 配列添字
- ヒープ → 親子だけ大小関係
配列添字
二分探索木を配列で表現する場合、インデックス (i) のノードに対して、左の子は (2i)、右の子は (2i+1) の添え字でアクセスします。
※根ノードが1から始まる場合。画像参照：https://basics.k-labo.work/2017/09/29/%E6%9C%A8%E6%A7%8B%E9%80%A0/
コメント