「AP過去問 令和6年度秋期 午前 問5」の版間の差分
| (同じ利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
[[AP過去問 令和6年度秋期 午前#問題 | [[AP過去問 令和6年度秋期 午前#問題|AP過去問 令和6年度秋期 午前 問題]]に戻る | ||
[[AP過去問 令和6年度秋期 午前 問4]]へ | [[AP過去問 令和6年度秋期 午前 問4]]へ | ||
| 12行目: | 12行目: | ||
table#tree { | table#tree { | ||
border-collapse: collapse; | border-collapse: collapse; | ||
width: | width: 500px; | ||
height: 300px; | height: 300px; | ||
table-layout: fixed; | table-layout: fixed; | ||
| 22行目: | 22行目: | ||
.tree { | .tree { | ||
position: relative; | position: relative; | ||
width: | width: 500px; | ||
height: 300px; | height: 300px; | ||
} | } | ||
| 54行目: | 54行目: | ||
<!-- Connectors --> | <!-- Connectors --> | ||
<!-- Level 1 to Level 2 --> | <!-- Level 1 to Level 2 --> | ||
<div class="line" style="top: 40px; left: | <div class="line" style="top: 40px; left: 200px; height: 70px; transform: rotate(45deg);"></div> | ||
<div class="line" style="top: 90px; left: | <div class="line" style="top: 90px; left: 250px; height: 70px; transform: rotate(135deg);"></div> | ||
<!-- Level 2 to Level 3 --> | <!-- Level 2 to Level 3 --> | ||
<div class="line" style="top: 90px; left: | <div class="line" style="top: 90px; left: 150px; height: 70px; transform: rotate(45deg);"></div> | ||
<div class="line" style="top: 140px; left: | <div class="line" style="top: 140px; left: 170px; height: 54px; transform: rotate(158deg);"></div> | ||
<div class="line" style="top: 90px; left: | <div class="line" style="top: 90px; left: 250px; height: 54px; transform: rotate(22deg);"></div> | ||
<div class="line" style="top: 140px; left: | <div class="line" style="top: 140px; left: 300px; height: 70px; transform: rotate(135deg);"></div> | ||
<!-- Level 3 to Level 4 --> | <!-- Level 3 to Level 4 --> | ||
<div class="line" style="top: 140px; left: | <div class="line" style="top: 140px; left: 100px; height: 70px; transform: rotate(45deg);"></div> | ||
<div class="line" style="top: 190px; left: | <div class="line" style="top: 190px; left: 150px; height: 70px; transform: rotate(135deg);"></div> | ||
<!-- Level 3 to Level 4 --> | <!-- Level 3 to Level 4 --> | ||
<div class="line" style="top: 140px; left: | <div class="line" style="top: 140px; left: 300px; height: 70px; transform: rotate(45deg);"></div> | ||
<div class="line" style="top: 190px; left: | <div class="line" style="top: 190px; left: 350px; height: 70px; transform: rotate(135deg);"></div> | ||
<!-- Level 4 to Level 5 --> | <!-- Level 4 to Level 5 --> | ||
<div class="line" style="top: 190px; left: | <div class="line" style="top: 190px; left: 250px; height: 58px; transform: rotate(33deg);"></div> | ||
<div class="line" style="top: 240px; left: | <div class="line" style="top: 240px; left: 280px; height: 58px; transform: rotate(147deg);"></div> | ||
<div class="line" style="top: 190px; left: | <div class="line" style="top: 190px; left: 350px; height: 70px; transform: rotate(22deg);"></div> | ||
<div class="line" style="top: 240px; left: | <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: 70px; left: | <div class="node" style="top: 70px; left: 130px;">4</div> | ||
<div class="node" style="top: 70px; left: | <div class="node" style="top: 70px; left: 230px;">8</div> | ||
<!-- Level 3 --> | <!-- Level 3 --> | ||
<div class="node" style="top: 120px; left: | <div class="node" style="top: 120px; left: 80px;">2</div> | ||
<div class="node" style="top: 120px; left: | <div class="node" style="top: 120px; left: 150px;">5</div> | ||
<div class="node" style="top: 120px; left: | <div class="node" style="top: 120px; left: 210px;">7</div> | ||
<div class="node" style="top: 120px; left: | <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: 170px; left: | <div class="node" style="top: 170px; left: 30px;">1</div> | ||
<div class="node" style="top: 170px; left: | <div class="node" style="top: 170px; left: 130px;">3</div> | ||
<div class="node" style="top: 170px; left: | <div class="node" style="top: 170px; left: 230px;">10</div> | ||
<div class="node" style="top: 170px; left: | <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: | <div class="node" style="top: 220px; left: 200px;">9</div> | ||
<div class="node" style="top: 220px; left: | <div class="node" style="top: 220px; left: 260px;">11</div> | ||
<div class="node" style="top: 220px; left: | <div class="node" style="top: 220px; left: 310px;">13</div> | ||
<div class="node" style="top: 220px; left: | <div class="node" style="top: 220px; left: 380px;">15</div> | ||
</div> | </div> | ||
| 125行目: | 125行目: | ||
=='''回答・解説'''== | =='''回答・解説'''== | ||
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> | |||
が答えとなります。 | |||
| 133行目: | 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
が答えとなります。