アルゴリズムとプログラミング
基本情報技術者試験｜ノード数が1000個の完全2分木のおよその高さ(根を第1段とする段数)はどれか
ノード数が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段はノード数の十分の一を高さとした根拠のない値で、対数のスケール感を誤っている。
アルゴリズムとプログラミングの他の問題
高さが4(根を第1段とし全4段が完全に埋まっている)の完全2分木の全ノード数はいくつか。頂点数nのグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。単方向連結リストと比べた双方向連結リストの利点として最も適切なものはどれか。循環連結リスト(環状リスト)の特徴として最も適切なものはどれか。後入れ先出し(LIFO)のデータ構造が処理の仕組みとして最も自然に当てはまる場面はどれか。先入れ先出し(FIFO)のデータ構造を用いるのが最も適切な処理はどれか。2分探索木(BST)が満たすべき構造的性質として最も適切なものはどれか。AVL木などの平衡2分探索木を用いる主な目的として最も適切なものはどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0035