「AP過去問 令和6年度秋期 午前 問5」の版間の差分
(ページの作成:「|AP過去問 令和6年度秋期 午前 問題に戻る AP過去問 令和6年度秋期 午前 問4へ AP過去問 令和6年度秋期 午前 問6へ =='''問5(問題文)'''== =='''回答・解説'''== AP過去問 令和6年度秋期 午前 問4へ AP過去問 令和6年度秋期 午前 問6へ AP過去問 令和6年度秋期 午前#問題||AP過去問 令和6年度秋期 午前…」) |
|||
| (同じ利用者による、間の44版が非表示) | |||
| 1行目: | 1行目: | ||
[[AP過去問 令和6年度秋期 午前#問題 | [[AP過去問 令和6年度秋期 午前#問題|AP過去問 令和6年度秋期 午前 問題]]に戻る | ||
[[AP過去問 令和6年度秋期 午前 問4]]へ | [[AP過去問 令和6年度秋期 午前 問4]]へ | ||
| 6行目: | 6行目: | ||
=='''問5(問題文)'''== | =='''問5(問題文)'''== | ||
次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。 | |||
<yjavascript> | |||
</script> | |||
<style> | |||
table#tree { | |||
border-collapse: collapse; | |||
width: 500px; | |||
height: 300px; | |||
table-layout: fixed; | |||
} | |||
td#tree { | |||
text-align: center; | |||
vertical-align: middle; | |||
} | |||
.tree { | |||
position: relative; | |||
width: 500px; | |||
height: 300px; | |||
} | |||
.node { | |||
position: absolute; | |||
width: 40px; | |||
height: 40px; | |||
background-color: #f0f8ff; | |||
border: 2px solid #4682b4; | |||
border-radius: 50%; | |||
display: flex; | |||
align-items: center; | |||
justify-content: center; | |||
font-size: 14px; | |||
font-family: Arial, sans-serif; | |||
font-weight: bold; | |||
box-shadow: 2px 2px 4px rgba(0, 0, 0, 0.2); | |||
} | |||
.line { | |||
position: absolute; | |||
width: 2px; | |||
background-color: #4682b4; | |||
transform-origin: top center; | |||
} | |||
</style> | |||
<table> | |||
<tr> | |||
<td > | |||
<!--<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 --> | |||
<div class="node" style="top: 20px; left: 180px;">6</div> | |||
<!-- Level 2 --> | |||
<div class="node" style="top: 70px; left: 130px;">4</div> | |||
<div class="node" style="top: 70px; left: 230px;">8</div> | |||
<!-- Level 3 --> | |||
<div class="node" style="top: 120px; left: 80px;">2</div> | |||
<div class="node" style="top: 120px; left: 150px;">5</div> | |||
<div class="node" style="top: 120px; left: 210px;">7</div> | |||
<div class="node" style="top: 120px; left: 280px; border: 4px solid #4682b4;">12</div> | |||
<!-- Level 4 (left side) --> | |||
<div class="node" style="top: 170px; left: 30px;">1</div> | |||
<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) --> | |||
<div class="node" style="top: 220px; left: 200px;">9</div> | |||
<div class="node" style="top: 220px; left: 260px;">11</div> | |||
<div class="node" style="top: 220px; left: 310px;">13</div> | |||
<div class="node" style="top: 220px; left: 380px;">15</div> | |||
</div> | |||
</td> | |||
</tr> | |||
</table> | |||
<script> | |||
</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> | |||
が答えとなります。 | |||
| 19行目: | 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
が答えとなります。