平成25年度秋期 応用情報技術者試験 午前 問6

正解：エ

AI解説

正解はエ。葉以外の節点がすべて二つの子をもち葉の深さが揃った完全な二分木では、葉の個数がnのとき葉以外の(内部)節点の個数はn−1になる。深さdの木で考えると葉は2^d個、内部節点は1+2+…+2^(d−1)=2^d−1個であり、確かに葉の数より1少ない。 ア: 木では節点の個数=枝の個数+1である(根以外の各節点が親への枝を1本ずつもつ)。枝がnなら節点はn+1であり誤り。 イ: 深さがnなら葉の個数は2^n個である。2^(n-1)は誤り。 ウ: 節点の個数nと深さdの関係はn=2^(d+1)−1であり、深さはlog₂(n+1)−1となる。log₂nではない。 エ: 正しい。葉がn=2^d個のとき内部節点は2^d−1=n−1個である。 💡 完全な二分木は「葉=2^深さ」「全節点=2^(深さ+1)−1」「内部節点=葉−1」の3公式で処理できる。迷ったら深さ2程度の小さな木を描いて確かめる。