問題


問6　節点1，2，･･･,nをもつ木を表現するために、大きさnの整数型配列A[1],A[2],･･･,A[n]を用意して、節点iの親の番号をA[i]に格納する。節点kが根の場合はA[k] = 0とする。表に示す配列が表す木の葉の数は、幾つか。

ア　1
イ　3
ウ　5
エ　7

解説と解答

　木構造をプログラムで実装する場合は、リストや配列により表現します。この問題では配列を使って、木を表現しています。

　木構造では、親のない節を根、子のない節を葉と呼びます。実際に図を描いて確認すると良いでしょう。まず、A[1]が0であることから節点1が根であることがわかります。

　同様にして節点2と節点3の親が節点1、節点4と節点5の親が節点3、節点6と節点7と節点8の親が節点5なので、以下のような木となります。

　したがって、葉（子のない節）の数は5となります。答えはウです

過去の同じ問題
・平成20年秋期 ソフトウェア開発技術者 午前　問10

城田 比佐子
アイティ・アシスト　インストラクタ
ITに関するコンサルティングや教育を実施するアイティ・アシストのインストラクタ。新入社員研修やプロマネ育成研修をはじめ，基本情報技術者試験，応用情報技術者試験，プロジェクトマネージャ試験などの試験対策研修の実績も豊富。著書に「3週間完全マスター 基本情報技術者 2011年版」、「3週間完全マスター 応用情報技術者 2011年版」などがある。