問9 葉以外の節点はすべて二つの子を持ち、根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち、適切なものはどれか。深さとは根から葉に至るまでの枝の個数を表す。
ア 枝の数がnならば、葉を含む節点の個数もnである。
イ 木の深さがnならば、葉の個数は2^(n-1)
ウ 節点の個数がnならば、深さはlog2nである。
エ 葉の数がnならば、葉以外の節点の個数はn-1である。
解答
エ
解説
これもよくでる木の問題ですねぇ。私は大嫌いです。
一応問題文の木は図のようなものでしょうかねぇ。
と一応図は貼っておきますが、まぁ、小さくて見えないので、念のためこんなものも書いてみました。
(*に意味はありません。Web表示したときに変にならないようにしただけの文字です。)
根
│
├───────────┐
│**********************│
節**********************節
│**********************│
├────┐************├─────┐
│********│************│**********│
節********節************節**********節
│********│************│**********│
├─┐****├─┐********├─┐******├─┐
│**│****│**│********│**│******│**│
葉**葉****葉**葉********葉**葉******葉**葉
この図は、問題文で言えば、深さが3の木を表しています。
これで選択肢を検証してみましょう。
ア 枝の数がnならば、葉を含む節点の個数もnである。
検証
枝の数は、2+4+8=14になります。
対して、節の個数は、1+2+4+8=15になります。
よって、誤りとなります。
イ 木の深さがnならば、葉の個数は2^(n-1)
検証
深さは3です。葉の数は8ですから、8=2^3!=2^(3-1)
よって、誤りとなります。
ウ 節点の個数がnならば、深さはlog2nである。
検証
節点の個数は、選択肢アで検証したとおり15です。
log215はちょっと求めづらいですねぇ。
15は2^3と2^4の間にあるので、
log215は3から4の間の数になります。
何となく正しいような間違っているような。
エ 葉の数がnならば、葉以外の節点の個数はn-1である。
検証
葉の数は8個です。拝外の節点数は7=8-1です。
何となく正しそうな気がします。
じつは、これが正解なんですねぇ。
「葉以外の節点はすべて二つの子を持ち、根から葉までの深さがすべて等しい木」なので、葉の数は、等比数列になり、具体的には、初項が1、公比が2の等比数列になります。
ただし、初項は深さ0の葉の数を表します。
よって深さと葉の数は以下の式で求められます。
An = 2^n An:葉の数 n:深さ
また、深さnの(葉を含む)節点の数は、公比数列の和で求められるので、以下のように求められます。
Sn-1 = (1-2^(n+1))/(1-2) = 2^(n+1)-1
ここで問題文の葉以外の節点数は2^(n+1)-1-2^nで求まります。この式を変形します。
2^(n+1)-1-2^n = 2*2^2-1-2^n=2^n(2-1)-1 = 2^n-1
となります。2^nは葉の数なので、葉の数-1が葉以外の節点の数になります。
よって、選択肢エが正解になります。
ちなみに各選択肢を正解にする文章は多分以下の通りでしょう。
ア 枝の数がnならば、葉を含む節点の個数はn+1である。
イ 木の深さがnならば、葉の個数は2^n
ウ 葉の個数がnならば、深さはlog2nである。
難易度(1(易)～5(難))
3 私が苦手と言うのも含めて、こんなもんでしょう。
問10 ビット列X1X2X3X4X5X6X7X8X9=010111111とY1Y2Y3=111に対して、次のアルゴリズムで表示されるkの変化はどれか。
k = 1;
d = 1;
while d ≠ 0;
print k;
if Xk ≠ Y1; ------(1)
d = 1;
esle if Xk+1 ≠ Y2; -----(2)
d = 2;
else if Xk+2 ≠ Y3; -----(3)
d = 3;
else
d = 0;
end if
k = k + d; ------(4)
end while;
ア 1,2,3,4
イ 1,2,4
ウ 1,3,4
エ 1,4
正解
イ
解説
この問題は、愚直にやっていくしかないですねぇ。
最初にk = 1、d = 1になっているので、最初は1が表示されますねぇ。
次に(1)の条件式をチェックします。
Xk = X1 = 0
Y1 = 1
if Xk ≠ Y1は成立するので、d = 1に成ります。
(4)式で kは2になります。そして、2が表示されます。
また、(1)の条件式をチェックします。
Xk = X2 = 1
Y1 = 1
if Xk ≠ Y1は成立しないので、(2)の条件式をチェックします。
Xk+1 = X(2+1) = X3 = 0
Y2 = 1
if Xk+1 ≠ Y2;は成立するので、d = 2に成ります。
(4)式でkは4に成ります。そして、4が表示されます。
まぁ、ここまでで1,2,4と表示されるイが正解となります。
難易度(1(易)～5(難))
1
ア 枝の数がnならば、葉を含む節点の個数もnである。
イ 木の深さがnならば、葉の個数は2^(n-1)
ウ 節点の個数がnならば、深さはlog2nである。
エ 葉の数がnならば、葉以外の節点の個数はn-1である。
解答
エ
解説
これもよくでる木の問題ですねぇ。私は大嫌いです。
一応問題文の木は図のようなものでしょうかねぇ。
と一応図は貼っておきますが、まぁ、小さくて見えないので、念のためこんなものも書いてみました。
(*に意味はありません。Web表示したときに変にならないようにしただけの文字です。)
根
│
├───────────┐
│**********************│
節**********************節
│**********************│
├────┐************├─────┐
│********│************│**********│
節********節************節**********節
│********│************│**********│
├─┐****├─┐********├─┐******├─┐
│**│****│**│********│**│******│**│
葉**葉****葉**葉********葉**葉******葉**葉
この図は、問題文で言えば、深さが3の木を表しています。
これで選択肢を検証してみましょう。
ア 枝の数がnならば、葉を含む節点の個数もnである。
検証
枝の数は、2+4+8=14になります。
対して、節の個数は、1+2+4+8=15になります。
よって、誤りとなります。
イ 木の深さがnならば、葉の個数は2^(n-1)
検証
深さは3です。葉の数は8ですから、8=2^3!=2^(3-1)
よって、誤りとなります。
ウ 節点の個数がnならば、深さはlog2nである。
検証
節点の個数は、選択肢アで検証したとおり15です。
log215はちょっと求めづらいですねぇ。
15は2^3と2^4の間にあるので、
log215は3から4の間の数になります。
何となく正しいような間違っているような。
エ 葉の数がnならば、葉以外の節点の個数はn-1である。
検証
葉の数は8個です。拝外の節点数は7=8-1です。
何となく正しそうな気がします。
じつは、これが正解なんですねぇ。
「葉以外の節点はすべて二つの子を持ち、根から葉までの深さがすべて等しい木」なので、葉の数は、等比数列になり、具体的には、初項が1、公比が2の等比数列になります。
ただし、初項は深さ0の葉の数を表します。
よって深さと葉の数は以下の式で求められます。
An = 2^n An:葉の数 n:深さ
また、深さnの(葉を含む)節点の数は、公比数列の和で求められるので、以下のように求められます。
Sn-1 = (1-2^(n+1))/(1-2) = 2^(n+1)-1
ここで問題文の葉以外の節点数は2^(n+1)-1-2^nで求まります。この式を変形します。
2^(n+1)-1-2^n = 2*2^2-1-2^n=2^n(2-1)-1 = 2^n-1
となります。2^nは葉の数なので、葉の数-1が葉以外の節点の数になります。
よって、選択肢エが正解になります。
ちなみに各選択肢を正解にする文章は多分以下の通りでしょう。
ア 枝の数がnならば、葉を含む節点の個数はn+1である。
イ 木の深さがnならば、葉の個数は2^n
ウ 葉の個数がnならば、深さはlog2nである。
難易度(1(易)～5(難))
3 私が苦手と言うのも含めて、こんなもんでしょう。
問10 ビット列X1X2X3X4X5X6X7X8X9=010111111とY1Y2Y3=111に対して、次のアルゴリズムで表示されるkの変化はどれか。
k = 1;
d = 1;
while d ≠ 0;
print k;
if Xk ≠ Y1; ------(1)
d = 1;
esle if Xk+1 ≠ Y2; -----(2)
d = 2;
else if Xk+2 ≠ Y3; -----(3)
d = 3;
else
d = 0;
end if
k = k + d; ------(4)
end while;
ア 1,2,3,4
イ 1,2,4
ウ 1,3,4
エ 1,4
正解
イ
解説
この問題は、愚直にやっていくしかないですねぇ。
最初にk = 1、d = 1になっているので、最初は1が表示されますねぇ。
次に(1)の条件式をチェックします。
Xk = X1 = 0
Y1 = 1
if Xk ≠ Y1は成立するので、d = 1に成ります。
(4)式で kは2になります。そして、2が表示されます。
また、(1)の条件式をチェックします。
Xk = X2 = 1
Y1 = 1
if Xk ≠ Y1は成立しないので、(2)の条件式をチェックします。
Xk+1 = X(2+1) = X3 = 0
Y2 = 1
if Xk+1 ≠ Y2;は成立するので、d = 2に成ります。
(4)式でkは4に成ります。そして、4が表示されます。
まぁ、ここまでで1,2,4と表示されるイが正解となります。
難易度(1(易)～5(難))
1