地方政府公務人員四等-電子工程類科計算機概要110 年第 17 題單選題
下列圖示中，左圖是一般樹而右圖是左子右兄弟樹（Left child-right sibling）的資料結構舉例。若此兩種資料結構中所有父子之間的連結和兄弟之間的連結均以雙向指標來實作，下列敘述何者錯誤？
A在一般樹的資料結構中，若使用固定個數的欄位儲存指標，則容易造成空間的浪費
B在計算節點與根節點（Root）的距離時，使用左子右兄弟樹不會比使用一般樹走訪（Traverse）更少的指標
C用左子右兄弟樹的資料結構來確認兩節點之間的父子關係在最差情況下需要檢查超過一個以上的指標
D用左子右兄弟樹的資料結構來確認兩節點之間的父子關係較一般樹的資料結構更有效率正確答案
D正確答案
左子右兄弟樹確認父子關係需走訪兄弟鏈，效率較差，故 D 錯誤。
逐選項解析
A在一般樹的資料結構中，若使用固定個數的欄位儲存指標，則容易造成空間的浪費✕ 錯誤
一般樹若以固定欄位陣列儲存子指標，當實際子數少於上限時會留下空欄，造成空間浪費。
B在計算節點與根節點（Root）的距離時，使用左子右兄弟樹不會比使用一般樹走訪（Traverse）更少的指標✕ 錯誤
在左子右兄弟樹中，節點向上走需先沿兄弟鏈回到最左子才能找到父，故走訪指標數不會少於一般樹。
C用左子右兄弟樹的資料結構來確認兩節點之間的父子關係在最差情況下需要檢查超過一個以上的指標✕ 錯誤
D用左子右兄弟樹的資料結構來確認兩節點之間的父子關係較一般樹的資料結構更有效率✓ 正確
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
