原住民族考試四等考試-電子工程類科計算機概要105 年第 18 題單選題考點：違反左子樹上界考點：合法 BST 路徑
下列何者可能是在二元搜尋樹中從樹根至某樹葉節點的尋訪過程？
A$4 \rightarrow 90 \rightarrow 82 \rightarrow 80 \rightarrow 75 \rightarrow 73 \rightarrow 76 \rightarrow 74 \rightarrow 78 \rightarrow 77$
B$4 \rightarrow 95 \rightarrow 80 \rightarrow 20 \rightarrow 25 \rightarrow 70 \rightarrow 50 \rightarrow 55 \rightarrow 60 \rightarrow 59$正確答案
C$10 \rightarrow 20 \rightarrow 30 \rightarrow 60 \rightarrow 55 \rightarrow 35 \rightarrow 40 \rightarrow 45 \rightarrow 47 \rightarrow 58$
D$100 \rightarrow 2 \rightarrow 90 \rightarrow 70 \rightarrow 30 \rightarrow 60 \rightarrow 65 \rightarrow 55 \rightarrow 58 \rightarrow 57$
B正確答案
二元搜尋樹尋訪時，每次走左子樹則後續值必須 ≤ 父節點上界；走右子樹則必須 ≥ 父節點下界。檢查每步是否違反區間即可。
逐選項解析
A$4 \rightarrow 90 \rightarrow 82 \rightarrow 80 \rightarrow 75 \rightarrow 73 \rightarrow 76 \rightarrow 74 \rightarrow 78 \rightarrow 77$違反左子樹上界✕ 錯誤
4→90 往右（>4），90→82 往左，82→80 往左，80→75 往左，75→73 往左，73→76 錯誤：76>75 但此時上界已被 75 限制（73 是 75 的左子樹），76 不可能出現。
B$4 \rightarrow 95 \rightarrow 80 \rightarrow 20 \rightarrow 25 \rightarrow 70 \rightarrow 50 \rightarrow 55 \rightarrow 60 \rightarrow 59$合法 BST 路徑✓ 正確
逐步檢查區間：4→95(右,≥4)→80(左,4~95)→20(左,4~80)→25(右,20~80)→70(右,25~80)→50(左,25~70)→55(右,50~70)→60(右,55~70)→59(左,55~60)，每步皆合法。
C$10 \rightarrow 20 \rightarrow 30 \rightarrow 60 \rightarrow 55 \rightarrow 35 \rightarrow 40 \rightarrow 45 \rightarrow 47 \rightarrow 58$✕ 易錯陷阱
D$100 \rightarrow 2 \rightarrow 90 \rightarrow 70 \rightarrow 30 \rightarrow 60 \rightarrow 65 \rightarrow 55 \rightarrow 58 \rightarrow 57$✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
