Re: [理工] [資結]-政大99-資科所
※ 引述《stevenwin (袋哥)》之銘言：
: 1. What is the complexity of inorder traversal of binary tree ?
: a. O(n)
: b. O(n^2)
: c. O(logn)
: d. O(nlogn)
Ans:a.
因為inorder traversal一般採用遞迴來解
best case:當binary tree是complete binary tree時
T(n)=2T(n/2)+1=O(n)
worst case:當binary tree是skew binary tree時
T(n)=T(n-1)+T(0)+1=O(n)
average case:T(n)=(1/n)*[T(0)+T(1)+...+T(n-1)+...+T(0)]+C=O(n)
其中C為常數(這樣解可能有錯?)
: 2. Which of the algorithm has stack property(LIFO)?
: a. Breath first search
: b. depth first search
: c. preorder of tree traversal
: d. none of the above
Ans:b,c
題目中有提到stack property就是具有Least In First Out的性質
(b)DFS須有Stack支援(因為DFS程式中有用到遞迴)
(c)preorder traversal程式中一樣有遞迴
不過題目用"has",那就挑一個吧
個人一些小小的想法，還請指教。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.37.2
→
03/06 17:38, , 1F
03/06 17:38, 1F
→
03/06 22:00, , 2F
03/06 22:00, 2F
→
03/06 22:01, , 3F
03/06 22:01, 3F
→
03/06 22:02, , 4F
03/06 22:02, 4F
推
03/06 22:14, , 5F
03/06 22:14, 5F
討論串 (同標題文章)