問題プレビューID: 7a485d61基本情報技術者試験 午前免除試験 2009年12月

問 5
基本情報技術者試験 午前免除試験 2009年12月

すべての葉が同じ深さをもち,葉以外のすべての節点が二つの子をもつ 2 分木に関して,節点数と深さの関係を表す式はどれか。ここで,n は節点数,k は根から葉までの深さを表す。例に示す 2 分木の深さ k は 2 である。

例に示す 2 分木は,根から深さ 2 まで,葉以外のすべての節点が二つの子をもつ木である。

解説

正解は「イ」です。

葉以外のすべての節点が二つの子をもち,すべての葉が同じ深さにある木は,完全 2 分木(perfect binary tree)である。深さごとの節点数は,根(深さ 0)が 1 個,深さ 1 が 21=22^1 = 2 個,深さ 2 が 22=42^2 = 4 個,…,深さ kk が 2k2^k 個となる。したがって,節点数の総数 nn は

n=20+21+22+⋯+2k=2k+1−1n = 2^0 + 2^1 + 2^2 + \cdots + 2^k = 2^{k+1} - 1

となる。例(k=2k = 2)では n=23−1=7n = 2^3 - 1 = 7 となり,図の節点数と一致する。

  • ア・ウ・エ: いずれも深さごとの節点数 2k2^k の関係を表しておらず,k=2k = 2 のとき n=7n = 7 とならない。

したがって,正解は「イ」です。

関連問題

本文が同じ・似ている問題を表示しています