【院試解答】東大院工学系研究科電気系工学専攻 2022年 問題4
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
※昔から電子工作を趣味としている管理人は、問題4の難易度の感覚がバグっているので、「難しい」と記載したもの以外はあまり参考にしないでください。
I
(1-i) 難易度:普通※
(1-ii) 難易度:普通※
(1-iii) 難易度:普通※
(2) 難易度:普通※
(3-i) 難易度:普通※
(3-ii) 難易度:普通※
Ⅱ
(1) 難易度:普通※
解答は分かりやすいよう空欄だけでなくその行ごと書いてある。
// A
return new;
// B
root->left = add(root->left);
// C
root->right = add(root->right);
(2-i) 難易度:普通※
(2-ii) 難易度:普通※
(3) 難易度:普通※
解答は分かりやすいよう空欄だけでなく周りごと書いてある。
// D, E if (root->left != NULL) { enumerate(root->left); } // F, G if (root->right != NULL) { enumerate(root->right); }
(4) 難易度:普通※
0個の場合、そのノードをただ消せばよい。 1個の場合、そのノードを消すと同時にその子ノードをそのノードがあった場所に引き上げる。 2個の場合、そのノードを消すと同時に、右部分木の最小ノードを外して、 そのノードがあった場所へと移動する。 この最小ノードをはずす際はノードを削除する手順を再帰的に適用する。
(5) 難易度:普通※
同じsidを持つノードは追加されない。 問題点は一つのsidを複数個保持することはできない。問題点ってむしろそういう使い方だと思えば問題じゃないと思うけど。
(6) 難易度:普通※
要素数をnとすると、 利点は要素の探索にかかる平均計算量がO(n)の配列に比べて2分探索木はO(log n)と 短いことで、 欠点は要素の追加にかかる平均計算量がO(1)の配列に比べて2分探索木はO(log n)と 長いことである。
