針對一個具有n個節點的二元搜尋樹（binary search tree），下列敍述何者錯誤？
A由根節點（root）開始，以中序（inorder）方式走訪此二元搜尋樹的時間複雜度為 $\theta(n)$
B在最差狀況下搜尋一個數值的時間複雜度為 $\theta(n)$
C在最差狀況下新增一個數值的時間複雜度為 $\theta(n)$
D在最佳狀況下刪除一個數值的時間複雜度為 $\theta(n)$正確答案
答案與詳解
逐選項解析
A由根節點（root）開始，以中序（inorder）方式走訪此二元搜尋樹的時間複雜度為 $\theta(n)$✕ 錯誤
中序走訪必須拜訪每一個節點各一次，無論樹形如何，時間複雜度固定為 θ(n)，敘述正確。
B在最差狀況下搜尋一個數值的時間複雜度為 $\theta(n)$✕ 錯誤
BST 最差狀況為退化成鏈狀（skewed tree），搜尋需從根一路比對到葉，時間複雜度為 θ(n)，敘述正確。
C在最差狀況下新增一個數值的時間複雜度為 $\theta(n)$✕ 錯誤
D在最佳狀況下刪除一個數值的時間複雜度為 $\theta(n)$✓ 正確
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
同科目歷年考卷
計算機概要 相關題目
假設在 N 個資料中要搜尋資料 X，則對於二分搜尋（Binary search）…
計算機概要 · 107 年 · 第 18 題
利用由左而右順序的數字資料：7, 34, 17, 19, 16, 10, 23,…
計算機概要 · 104 年 · 第 28 題
如果一個二元搜尋樹最長的搜尋路徑包含節點數為 4，則這個二元樹可能包含最大的節點…
計算機概要 · 107 年 · 第 34 題
最小堆積樹（Min Heap）如圖所示，執行節點刪除後，此最小堆積樹前序走訪（P…
計算機概要 · 109 年 · 第 24 題
關於一個有 n 個節點的紅黑樹（red-black tree），下列敘述何者錯誤…
計算機概要 · 109 年 · 第 5 題
若使用陣列實作最大堆積（max-heap），下列敘述何者錯誤？
計算機概要 · 108 年 · 第 26 題
