2013　島根大学　推薦I総合理工（情報・情報システム）学部情報MathJax

丸は頂点と呼ばれ，線は辺と呼ばれる．また一番上の黒い頂点は根と呼ばれ，下にある灰色の頂点は葉と呼ばれる．

この$2$分木は以下のように機能的に定義される：

（帰納ステップの様子については下図を参照せよ．）

このように定義される$2$分木$T$の高さ$h(T)$は頂点から葉までいくときに通る辺の数の最大値で，以下のように帰納的に定義される：

このとき，以下の問に答えよ．すべての解答は解答用紙に記入すること．：

(a)　$2$分木の頂点数$n(T)$の帰納的定義を述べよ．

(b)　$2$分木の高さと頂点数に関する以下の不等式を帰納的に証明せよ．解答は以下の枠1)と2)に式や文を記入して証明を完成することで示せ．各枠の中には複数の式や文を記入してよい．

$n(T)\geqq 2h(T)+1$

証明：

基礎ステップ：ただひとつの頂点からなる$2$分木$T$に対しては，

となり，問題文の不等式は成り立つ．

帰納ステップ：$2$つの$2$分木$T_1$と$T_2$に対して不等式が成り立っていると仮定する．このとき，$2$分木の定義の帰納ステップを使って$T_1$と$T_2$から新たに作られる$2$分木$T$に対しては，

となり，やはり問題文の不等式は成り立つ．

以上より，すべての$2$分木に対して問題文の不等式が成り立つことが示された．（証明終わり）

　具体的な方法は以下のようになる．例えば，列$A=(6,5,8,7)$に対してこの方法を使うと，列$B=(5,6,7,8)$が得られる．

❲列$A$から列$B$を作り出す方法❳

(a)　上記の方法について述べた次の文章について，$\boxed{}$内を適当な数字または記号で埋めて，答えを解答用紙に記せ．

　列$A=(3,1,2,4)$を考える．まず，列$A$の$1$番目の数を取り出して，列$B$を作ると$B=(3)$となる．また，列$A$からは，$3$を取り出すので，$A=(1,2,4)$となる．

　次に，列$A$から$1$番目の数である$1$を取り出して，列$B$へ移す．このとき，$1$と列$B$の$1$番目の数$3$を大小比較する．$1$は$3$より小さいので，$3$の直前に挿入する．つまり$B=(1,3)$となる．$A$からは$1$を取り出したので，$A=(2,4)$となる，$1$を移すときに必要となる大小比較の回数は$1$回となる．

　続いて，$A$の$1$番目の数$2$を取り出して，列$B$へ移す．まず，$2$を$B$の$1$番目の数$1$と大小比較して，次に$B$の$2$番目の数$3$と比較する．$2$は$3$より小さいので，結局$B=\boxed{\text{ア}}$となる．また，$A$からは$2$を取り出したので，$A=\boxed{\text{イ}}$となる．$2$を移すときに必要となる大小比較の回数は$\boxed{\text{ウ}}$回となる．

　最後にもう一度$A$の$1$番目の数を取り出して，列$B$に移す．$B$の要素の$1$番目から順に大小比較をしていくと，最終的に列$B$は$(1,2,3,4)$となる．$A$には数が残っていないため，終了となる．$A$の最後の数を$B$に移す時に必要となる大小比較の回数は$\boxed{\text{エ}}$回となる．

(b)　列$A=(1,2,3,4)$に対して上記の方法を使って列$B$を作ると，大小比較は合計何回行われることになるか．

(c)　列$A=(n,n-1,\cdots ,2,1)$は，$1$から$n\text{（}n\geqq 2\text{）}$までの$n$個の数が，大きい方から順に並べられた列である．上記の方法を使って列$B$を作ると，大小比較は合計何回行われることになるか．$n$を使って示せ．また，なぜそのような結果が得られたかを説明せよ．

図　回転する座標

(a)　右図のように座標$x‐y$に対して座標$X‐Y$が一定の回転速度で回転しているとする．回転の中心は両座標に共通の原点$\mathrm{O}$とする．$x$軸と$X$軸とのなす角が$\theta$のとき，座標$X‐Y$において$(a,b)$という座標を持つ点は，座標$x‐y$においてはどのような座標をもつか答えよ．

(b)　座標$x‐y$において，$(p,q)$という座標を持つ点は，座標$X‐Y$においてはどのような座標を持つか答えよ．