データ構造とアルゴリズム’01　試験解答例

問題１　30点　問題２　30点　問題３　30点問題2　の各小問と問題3 で、　説明が完璧な回答（ほとんど皆無でしたが）に対しては5点づつ加点

問題１木の探索(preorder, inorder) 、ハッシュの更新、木の高さの評価

　この問題に関しては、基本問題なので､教科書を見てください。ほぼ昨年と同じ傾向の問題を出しました。
（３）で、ｎ頂点の2分木の高さの最大はn-1 (なお、木の高さが１ずれていても減点は無しにしました。）高さの最小値を求める問題で、
完全2分木の高さが[log n]　(ここで[]はフロア関数のつもり）であることをまず確かめます（これは多くの人が出来ていました）。これだけでも減点はしませんでしたが、厳密には下記のような議論が必要です。与えられた木が完全2分木でなければ、次数１の頂点に子供を付け加えることで、高さhを変えずに頂点を増やすことが出来ます。このように頂点を増やして行くと、いずれ完全2分木になります。ｋ個の頂点を付け加えたとしましょう。すると、木の高さは、完全2分木ですから、[log (n+k)] になります。この値は[log n]より大きいので、完全2分木の場合が最小になります。その他、帰納法での証明（帰納法での回答で完全なものには加点しました）でもいいです。

問題2：漸近評価式の証明　

多分出来が悪いとは予想していましたが、予想以上に悲惨な結果でした。正しいかどうかを判定し，証明せよという問題。
証明はともかく、特に（1）の正誤の判定は感覚的に出来ないといけない。 3つとも正しい式でした。　
k,n は正整数。(TEXの数学表記を使います）

　 2n^2 + n \log ^4 n^2 = O(n^2)
対数項は、何乗されても、また、対数の中にどんな多項式が入っても、n より漸近的には小さいです。この感覚が大切。　
証明としては、上記の感覚だけ述べればOK. もちろん、正確に証明（下記の各門のように）してもいいです。
ｎを幾つか代入してみて、第2項が大きいから支配的だという誤回答がかなり多かったです。よく復習してください。
kがn以下ならば、k\log (n/k) = O(n)
証明できた人が全くいなかったので、少し出題を反省しています。ｋを定数として、O（\log n) だから｢この式は間違っている」という回答が幾つかありました。
一方、O(\log n) だから、｢この式は正しい」という回答もありました。後者には部分点を与えてあります。
\log n = O(n) は正しい式です　（授業でやったはずです。教科書を見てください）。一方、もちろん　n = O( \log n )は誤っています。　この辺が漸近評価式のいやらしいところではあります。
さて、ｋが定数とはどこにも書いてありません。証明をして見ましょう。
正の定数ｃが存在して、 k \log (n/k) ＜ cn であることを証明すればいいです。
k が正なので、 \log (n/k) ＜ c(n/k) を示せばいいです。 n/k をtとすると、ｋがｎ以下なので、t＜1 です。
c=１　とすると、　log t ＜　t　を示せばいいです。これを示すには、グラフを書いてもいいし、微積分を用いてもいいです。
切り上げ関数の記号を、面倒なので｛｝で書きます。
f(1)=1 かつ　f(n) ＜　f({n/2}) + f({n/4}) + n ならば　f(n) = O(n)
授業でさんざんやったはずの「帰納法による説明」が出来るかどうかの問題。　ほぼ全滅状態
ただし，証明よりも、｢答えが正しい」という直感が大切で、その直感がわかる説明があればOKです。下記のような厳密な証明は要求しません。
充分大きなｎでは、 f(n) ＜ cn であることを示します。（ｃは後で決めます） n以下のｋでは　f(k) ＜ ck が成立しているとしましょう。
すると f(n) ＜ c({n/2})　+ c({n/4}) + n ですから。 cn ＞ c({n/2}) + c({n/4}) + n を示せばいいです。 {n/2} と{n/4}は　n/2 +1，n/4+1　よりは小さいですから、
cn ＞　3cn/4 + n + 2c
cn /4 ＞ n + 2c
c=8とすると、n ＞ 16 でこの式が成り立ちます。正確には　n が15以下で f(n) ＜　8n であることを確かめておかないと帰納法としては厳密ではないですが、これは、漸近評価式の場合は省いてもそれほどしかられません。
他にも証明の方法はいろいろあります。教科書（「ｋ番目の値の選択」のところなど）を読み直してください。
f(n) ＜　f({3n/4}) + f({n/4}) + n だと答えが変ります。どうなるでしょうか??

問題３

　 0から100までの値を取るｎ個の実数データから、平均が70を超えるように出来るだけたくさんのデータを選ぶアルゴリズムを記述し、計算時間を解析しなさい

この問題は出来がよかったです。応用能力はあるみたいです。

データを大きい順にソートし、大きい順に選びます。
70を各データから引いたものを加えていき、和が負になったら、直前まで選んだデータたちを出力します。

計算時間はソート以外はO(n)、ソートが支配的になり、全体でO(n \log n)

多かった誤答：　直前に授業でやったせいか、ナップザック問題と混同している人が数人いました。　難しく考えすぎないように。

一つデータを増やすとき、過去の平均に加えて２で割ったものは平均になりませんから、ご注意を。

減点はしませんが、データが｢整数」であるとして、バケットソートやRadix　ソートを使っている人がいました。条件をよく読んでください。

　計算時間がO(n^2) になってしまった回答はある程度減点

データ構造とアルゴリズム’01 試験解答例

データ構造とアルゴリズム’01　試験解答例