關務人員考試關務四等-資訊處理(選試英文)科別計算機概要110 年第 25 題單選題

若一個二元樹（binary tree ）有 $n$ 個節點，使用中序走訪（inorder traversal ）的時間複雜度，下列何者正確？

θ (lo g n)

θ (n)

正確答案

θ (n lo g n)

θ (n^{2})

答案與詳解

正確答案

中序走訪需訪問每個節點恰好一次,時間複雜度為

θ (n)

。

正確。走訪需拜訪所有 n 個節點,每節點 O(1),總共 $θ (n)$ 。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。

若一個二元樹（binary tree ）有 n 個節點，使用中序走訪（inorder traversal ）的時間複雜度，下列何者正確？