修了試験 2014-12-21実施分 基本情報技術者試験 問6

解説

正解は3です。 配列A[i]に節点iの親の番号が入っているので、親子関係を復元して葉の数を数えます。 葉とは、子をもたない節点のことです。 【計算】 A[1]＝0なので、節点1が根です。 A[2]＝1、A[3]＝1なので、節点2と3は節点1の子です。 A[4]＝3、A[5]＝3なので、節点4と5は節点3の子です。 A[6]＝5、A[7]＝5、A[8]＝5なので、節点6、7、8は節点5の子です。 A[i]の値として現れる番号は0、1、3、5であり、親になっている節点は1、3、5の3つです。 残る節点2、4、6、7、8の5つは誰の親にもならないので、葉です。 【選択肢別解説】 1：× 葉が1つになるのは木が一直線につながる場合です。 この木は分岐しており、葉は5つあります。 2：× 3は親になっている節点（1、3、5）の数です。 葉は子をもたない節点なので、残りの5つです。 3：○ 子をもたない節点は2、4、6、7、8の5つであり、葉の数は5です。 4：× 7は根以外の節点の数です。 そのうち3と5は子をもつので葉ではありません。 【ポイント】 親を記録する配列では、配列の値に一度も現れない番号が葉です。 全節点数8から、親として現れる節点数3を引くと、葉の数5がすぐ求まります。