基本情報技術者試験「2分木」の問題
ノード数が1000個の完全2分木のおよその高さ(根を第1段とする段数)はどれか。
アおよそ10段
イ段数はおよそ500
ウ約32段
エ約100段
正解
ア．およそ10段
完全2分木の高さはおよそlog2 n。2^9=512、2^10=1024なので1000個はほぼ10段に収まる(2^10-1=1023≧1000)。よって約10段で正しい。
?選択肢ごとの解説
ア ○完全2分木の高さはおよそlog2 n。2^9=512、2^10=1024なので1000個はほぼ10段に収まる(2^10-1=1023≧1000)。よって約10段で正しい。
イ ×段数500はノード数を2で割った値で、高さが対数的に増える性質を線形と誤解した典型的な誤りである。
ウ ×約32段は1000の平方根(約31.6)に近い値で、高さをlog2でなく平方根と取り違えた誤りである。
エ ×約100段はノード数の十分の一を高さとした根拠のない値で、対数のスケール感を誤っている。
✎くわしく
完全2分木は段が1段増えるたびノード数がほぼ倍になるため、高さはノード数の2を底とする対数で増える。n=1000で約10段、n=100万でも約20段にしかならない。この対数的な低さが平衡木の探索効率O(log n)を支えている。
✓本番での押さえどころ
試験のコツ
2の累乗(2^10≒1000、2^20≒100万)を覚え、ノード数を超える最小の2^kから段数を逆算する。
覚え方
倍々で増えるから1000個でも『たった10段』、と紙を10回折ると千枚超のイメージで覚える。
よくある誤り
高さがノード数に比例(n/2など)すると誤る、またはlog2を平方根や常用対数と混同する誤りがある。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0035