問題プレビューID: b4ec8fb1基本情報技術者試験 午前免除試験 2012年1月22日

問 5
基本情報技術者試験 午前免除試験 2012年1月22日

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

ii12345678
A[i]01133555
解説

正解は「ウ」です。

配列 A は各節点の親の番号を格納しており,親として一度も現れない節点が葉(子をもたない節点)です。A[i] に現れる値は 1,1,3,3,5,5,5 であり(0 は根を表すので除く),親となっている節点は 1,3,5 の 3 個です。節点は全部で 8 個あるので,葉の数は 8−3=58 - 3 = 5 個となります。

なお,この木は節点 1 を根とし,節点 3 の子が 4 と 5,節点 5 の子が 6,7,8 という構造で,葉は 2,4,6,7,8 の 5 個です。よって「ウ」が正解です。

  • ア・イ・エ: 親として現れる節点の数え方や,根を葉に含めるかどうかを誤った場合の値である。

関連問題

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