修了試験 2012-01-22実施分 基本情報技術者試験 問5

解説

正解は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の子です。 親として現れる節点は1、3、5の3個です。 それ以外の節点2、4、6、7、8の5個が葉となります。 【選択肢別解説】 1：× 葉が1個になるのは木が一直線につながる場合です。 この配列では子をもたない節点が5個あります。 2：× 3は親として現れる節点（1、3、5）の個数です。 葉の数は全8節点からこれを除いた5個です。 3：○ 節点2、4、6、7、8は誰の親にもなっていないので葉です。 合計は5個です。 4：× 7は根以外の節点の個数です。 根以外の節点がすべて葉になるわけではありません。 【ポイント】 親を格納する配列表現では「配列の値に現れない番号が葉」と覚えると素早く解けます。 不安なときは、根から子をたどって木の形を実際に描いてみましょう。