Re: [商管] [資結] 中山資料結構問題!
※ 引述《ybite (小犬)》之銘言：
: ※ 引述《st84514 (綜合水果武士)》之銘言：
: : 96年題目如下:
: : http://tinyurl.com/2fet7sg
: : 想問第一大題(B)的best case 為何是O(1)?
: 雖然我不認同O(1)這個答案，但我的想法是這樣的：
: 如果「找兩數相加的最大值」 = 「找樹中最大和次大的元素」，
: 如果樹長成這樣子的話：
: A
: /
: B
: 找最大值是一個O(1)的動作，而往下者次大值也應該只需要O(1)...吧...
: 歡迎指摘我的錯誤qqqqq
這樣講好像又有點牽強...我是寫若是完滿的情形是(logn)
: : 第二大題(A)(B)又該如何解釋?
: (A) 因為插入元素和印出所有元素的頻率很高，所以我會選AVL樹
: 主要原因是AVL樹的插入在最壞狀況下也只需要O(lgn)的時間複雜度
但若無碰撞情形下hash的儲存跟搜尋不是只要O(1)
順便問一下若發生碰撞時間會O(n)嗎?
: (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: 219.85.35.62
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：