→ assassin88:第一題想錯我就不爽 03/06 17:38
→ leeheng:OS的stack也算？那我寫錯了...我寫d 03/06 22:00
→ leeheng:所有loop和recursive是可以等價轉換的 03/06 22:01
→ leeheng:我也可以不用遞迴寫...吧 XD 03/06 22:02
推 shortoneal:他只問有沒有這個property吧，可是我看到b就選了沒選c 03/06 22:14
※ 引述《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