國中教甄｜資訊科技資訊科技109 年第 79 題單選題

Given a binary search tree where its node numbers are in [1,1000], now we want to search the number 363. Which one of the following searching orders is impossible？

A925, 202, 911, 240, 912, 245, 363正確答案

B2, 252, 401, 398, 330, 344, 397, 363

C924, 220, 911, 244, 898, 258, 362, 363

D2, 399, 387, 219, 266, 382, 381, 278, 363

答案與詳解

正確答案

在二元搜尋樹中搜尋 363 時，路徑必須維持由先前比較節點決定的合法區間；A 在 911 之後出現 912，超出上界，因此不可能。

A925, 202, 911, 240, 912, 245, 363✓ 正確

925 大於 363，之後應小於 925；202 小於 363，之後應大於 202；911 大於 363，之後應小於 911；240 小於 363，之後應大於 240 且小於 911。接著出現 912，雖然大於 240，但已大於上限 911，不可能出現在 911 的左子樹中，故序列不合法。

B2, 252, 401, 398, 330, 344, 397, 363✕ 錯誤

2、252 逐步提高下限，401、398 設定上限，330、344 再提高下限，397 設定上限，最後 363 落在合法區間內，因此是可能的搜尋順序。

C924, 220, 911, 244, 898, 258, 362, 363✕ 易錯陷阱

D2, 399, 387, 219, 266, 382, 381, 278, 363✕ 易錯陷阱

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解