基本情報技術者 2010年 秋期 午前（科目A） 問06

親配列表現の葉数【午前解説】

正解の理由

解法ステップ

1. 親配列A[1..n] を確認する（ここではA = [0,1,1,3,3,5,5,5]）。
2. 配列の値のうち0を除いた異なる値（distinct values）を求める。これが「親として出現する節点の集合」である。
3. 葉の個数は $n$ からその集合の要素数を引く：葉数 = $n-|\{\text{parents}\}|$。
4. 値を代入して計算する：$8-3=5$。

選択肢別の誤答解説

• ア: 1
  1を選ぶのは根だけを葉と誤認する場合に起こります。根は子を持たなければ葉になりますが、今回の根（節点1）は子（節点2,3）を持っているため葉ではありません。
• イ: 3
  「子が1つの節点」を数えるなどの別の誤りが考えられます。今回、子を持つ節点は1,3,5の3つですが、これは内部節点の数であって葉の数ではありません（葉は内部節点以外の節点）。
• エ: 7
  7を選ぶのは「重複をカウントしない」「親として現れるかどうかではなく、子の総数を誤って数えた」などの計算ミスが原因です。親配列中に現れる値の重複（例えば5が3回現れる）は内部節点の種類数を増やすものではありません。重複は1つとして扱います。

よくある誤解

• 「親配列での登場回数を数えれば良い」と思い込み、異なる親ノードの種類ではなく出現回数の合計を用いるミス。重複は1回しか数えない（集合で見なす）点に注意してください。
• 0を親集合に含めてしまうミス。0は根の印なので葉判定のための親集合には含めません。
• 親として出現する節点の種類数の下限を常に1としてしまう誤解。一般には $0\le |\text{parents}|\le n-1$ が成り立ちます（特に $n\ge 2$ のときは少なくとも1つの親が存在するため $1\le |\text{parents}|\le n-1$）。

補足コラム

• 一般的なアルゴリズム実装はO(n) で行えます。親配列を1回走査して0を除く親番号を集合に入れ、その集合のサイズを用いて葉数を求めます。
• 親配列は根を指す要素に0を使う慣習がありますが、別の表現（-1やself-indexing）を使う問題もあり得ます。符号や特別値に注意して同様の集合処理を行ってください。

A = [0,1,1,3,3,5,5,5]  # 長さn (=8)
parents = set(x for x in A if x != 0)
n = len(A)
leaves = n - len(parents)
print(leaves)  # 5

FAQ