※ 引述《st84514 (綜合水果武士)》之銘言：
: 96年題目如下:
: http://tinyurl.com/2fet7sg
: 想問第一大題(B)的best case 為何是O(1)?
雖然我不認同O(1)這個答案，但我的想法是這樣的：
如果「找兩數相加的最大值」 = 「找樹中最大和次大的元素」，
如果樹長成這樣子的話：
A
/
B
找最大值是一個O(1)的動作，而往下者次大值也應該只需要O(1)...吧...
歡迎指摘我的錯誤qqqqq
: 第二大題(A)(B)又該如何解釋?
(A) 因為插入元素和印出所有元素的頻率很高，所以我會選AVL樹
主要原因是AVL樹的插入在最壞狀況下也只需要O(lgn)的時間複雜度
(B) 這題我會選Hash Table，因為只需要「拿出值」的情況下，Hash Table會最快
: 第四跟第五大題也解不出來...
第四題是演算法中的遞迴問題，建議您去翻一下演算法的教科書...
（或著搜尋關鍵字「Master Theorem」）
第五題似乎是機率，得另請高明qqqqqq
: 95題目如下:
: http://tinyurl.com/28g4puq
: 想請問第四題如何證明?
我的證明：
假設樹有N層，Almost complete表示1~(N-1)層都是滿的，到N-1層為止會有
1+2+2^2+...+2^(N-1) = 2^N - 1個元素
然後Almost complete的情況下，第N層的第一個元素一定是在最左側
所以他的編號就一定會是2^N - 1 + 1 = 2^N
: 第七題解答給stack[++*top]=element；
: 但我是寫stack[top++]=element；請問哪個對?
: 且不知解答為啥要標*?他又沒說是指標!
: 他沒說陣列起始位置我假設他從1開始!
: 第八題解答給return stack[(*top)--]；
: 我寫return stack[--top]；
: 這題也沒說陣列起始位置所以依照上題我也假設他從1開始
: 這樣的話top所指的應該都是空的,請問哪個對?
: 懇請高手解答!感激不盡!
這題我也不太曉得 orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.179.82