「AP過去問 令和6年度秋期 午前 問5」の版間の差分
| (同じ利用者による、間の37版が非表示) | |||
| 1行目: | 1行目: | ||
[[AP過去問 令和6年度秋期 午前#問題 | [[AP過去問 令和6年度秋期 午前#問題|AP過去問 令和6年度秋期 午前 問題]]に戻る | ||
[[AP過去問 令和6年度秋期 午前 問4]]へ | [[AP過去問 令和6年度秋期 午前 問4]]へ | ||
| 6行目: | 6行目: | ||
=='''問5(問題文)'''== | =='''問5(問題文)'''== | ||
次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。 | |||
<yjavascript> | <yjavascript> | ||
</script> | </script> | ||
| 11行目: | 12行目: | ||
table#tree { | table#tree { | ||
border-collapse: collapse; | border-collapse: collapse; | ||
width: | width: 500px; | ||
height: | height: 300px; | ||
table-layout: fixed; | table-layout: fixed; | ||
} | } | ||
| 21行目: | 22行目: | ||
.tree { | .tree { | ||
position: relative; | position: relative; | ||
width: | width: 500px; | ||
height: | height: 300px; | ||
} | } | ||
.node { | .node { | ||
| 49行目: | 50行目: | ||
<tr> | <tr> | ||
<td > | <td > | ||
<div class="tree" style="background-image: url('https://wiki.yo-net.jp/images/HouganBG.png');"> | <!--<div class="tree" style="background-image: url('https://wiki.yo-net.jp/images/HouganBG.png');">--> | ||
<div class="tree"> | |||
<!-- Connectors --> | |||
<!-- Level 1 to Level 2 --> | |||
<div class="line" style="top: 40px; left: 200px; height: 70px; transform: rotate(45deg);"></div> | |||
<div class="line" style="top: 90px; left: 250px; height: 70px; transform: rotate(135deg);"></div> | |||
<!-- Level 2 to Level 3 --> | |||
<div class="line" style="top: 90px; left: 150px; height: 70px; transform: rotate(45deg);"></div> | |||
<div class="line" style="top: 140px; left: 170px; height: 54px; transform: rotate(158deg);"></div> | |||
<div class="line" style="top: 90px; left: 250px; height: 54px; transform: rotate(22deg);"></div> | |||
<div class="line" style="top: 140px; left: 300px; height: 70px; transform: rotate(135deg);"></div> | |||
<!-- Level 3 to Level 4 --> | |||
<div class="line" style="top: 140px; left: 100px; height: 70px; transform: rotate(45deg);"></div> | |||
<div class="line" style="top: 190px; left: 150px; height: 70px; transform: rotate(135deg);"></div> | |||
<!-- Level 3 to Level 4 --> | |||
<div class="line" style="top: 140px; left: 300px; height: 70px; transform: rotate(45deg);"></div> | |||
<div class="line" style="top: 190px; left: 350px; height: 70px; transform: rotate(135deg);"></div> | |||
<!-- Level 4 to Level 5 --> | |||
<div class="line" style="top: 190px; left: 250px; height: 58px; transform: rotate(33deg);"></div> | |||
<div class="line" style="top: 240px; left: 280px; height: 58px; transform: rotate(147deg);"></div> | |||
<div class="line" style="top: 190px; left: 350px; height: 70px; transform: rotate(22deg);"></div> | |||
<div class="line" style="top: 240px; left: 400px; height: 70px; transform: rotate(135deg);"></div> | |||
<!-- Top Node --> | <!-- Top Node --> | ||
<div class="node" style="top: 20px; left: | <div class="node" style="top: 20px; left: 180px;">6</div> | ||
<!-- Level 2 --> | <!-- Level 2 --> | ||
<div class="node" style="top: | <div class="node" style="top: 70px; left: 130px;">4</div> | ||
<div class="node" style="top: | <div class="node" style="top: 70px; left: 230px;">8</div> | ||
<!-- Level 3 --> | <!-- Level 3 --> | ||
<div class="node" style="top: | <div class="node" style="top: 120px; left: 80px;">2</div> | ||
<div class="node" style="top: | <div class="node" style="top: 120px; left: 150px;">5</div> | ||
<div class="node" style="top: | <div class="node" style="top: 120px; left: 210px;">7</div> | ||
<div class="node" style="top: | <div class="node" style="top: 120px; left: 280px; border: 4px solid #4682b4;">12</div> | ||
<!-- Level 4 (left side) --> | <!-- Level 4 (left side) --> | ||
<div class="node" style="top: | <div class="node" style="top: 170px; left: 30px;">1</div> | ||
<div class="node" style="top: | <div class="node" style="top: 170px; left: 130px;">3</div> | ||
<div class="node" style="top: 170px; left: 230px;">10</div> | |||
<div class="node" style="top: 170px; left: 330px;">14</div> | |||
<!-- Level 5 (right side) --> | <!-- Level 5 (right side) --> | ||
<div class="node" style="top: 220px; left: 200px;">9</div> | |||
<div class="node" style="top: 220px; left: 260px;">11</div> | |||
<div class=" | |||
<div class=" | |||
<div class="node" style="top: 220px; left: 310px;">13</div> | |||
<div class=" | <div class="node" style="top: 220px; left: 380px;">15</div> | ||
<div class=" | |||
</div> | </div> | ||
</td> | </td> | ||
| 95行目: | 112行目: | ||
<script> | <script> | ||
</yjavascript> | </yjavascript> | ||
ア 9 | |||
イ 10 | |||
ウ 13 | |||
エ 14 | |||
=='''回答・解説'''== | =='''回答・解説'''== | ||
2分探索木は自ノードの左側は全て小さい値である必要があり、右側は全て大きい値である必要があります。9を移動すると左に9より大きい10や11が残り駄目です。10を移動すると11をどこにつけるかという問題も生じますが、どこに付けたとしても、10より大きい11が左の残るので駄目です。14も同じようなことで、13をどこにつけるかという問題が生じつつ、どこに付けたとしても、14より小さい13が右に残るので駄目です。したがって、13がうまく行きます。11でもうまく行きますが、11は選択肢にないので、答えになりません。したがって、 | |||
<span style = "background:linear-gradient(transparent 75%, #7fbfff 75%); font-weight:bold; "> | |||
ウ 13</span> | |||
が答えとなります。 | |||
| 107行目: | 141行目: | ||
[[AP過去問 令和6年度秋期 午前 問6]]へ | [[AP過去問 令和6年度秋期 午前 問6]]へ | ||
[[AP過去問 令和6年度秋期 午前#問題 | [[AP過去問 令和6年度秋期 午前#問題|AP過去問 令和6年度秋期 午前 問題]]に戻る | ||
2024年12月23日 (月) 23:10時点における最新版
問5(問題文)
次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。
|
6
4
8
2
5
7
12
1
3
10
14
9
11
13
15
|
ア 9
イ 10
ウ 13
エ 14
回答・解説
2分探索木は自ノードの左側は全て小さい値である必要があり、右側は全て大きい値である必要があります。9を移動すると左に9より大きい10や11が残り駄目です。10を移動すると11をどこにつけるかという問題も生じますが、どこに付けたとしても、10より大きい11が左の残るので駄目です。14も同じようなことで、13をどこにつけるかという問題が生じつつ、どこに付けたとしても、14より小さい13が右に残るので駄目です。したがって、13がうまく行きます。11でもうまく行きますが、11は選択肢にないので、答えになりません。したがって、
ウ 13
が答えとなります。