推 QQprob:真的太感謝了!!! 09/27 20:22
推 seanptt:11題 C是錯的吧 at most 要用到fib 01/09 17:45
※ 引述《QQprob (吃飯睡覺)》之銘言：
: http://www.lib.ntu.edu.tw/exam/graduate/97/97413.pdf
: 第2題
: 我得到的答案中A選項是對的
: 但A選項中包含卻不含相等，這樣是正確的嗎?(我以為相等才是定義)
這題我覺得怪怪的..
因為只有寫 O(g(n))-θ(g(n))不知道實際上是怎樣@@..
比如說g(n)是x^3
那像 2x^3是屬於O(g(n)) x^3屬於θ(g(n))
相減還是包含有x^3 所以不包在o(g(n))裡..
不過這題我不是很懂
所以可能還可以討論一下之類的
: 第4題
: A選項為何是正確的?
: D選項為何是錯誤的?(FIFO不也就代表LILO嗎?)
A整個敘述乍看之下都是對的..
你是有特別覺得哪裡錯嗎?
D選項我其實也覺得是對的XD
: 第8題
: 為何A選項是錯誤的?
因為要connected才行
: 第11題
: 我得到的答案CD選項都是對的
: 但C選項應該是at least吧?
: 還有D選項為何是對的?
C是最多沒錯
最少的話每個tree都是logn
討論最多才有意義
D選項我覺得是對的
最多都是轉LL LR RR RL類似這樣就能搞定
(可是要找適當位子轉)
如果你還是覺得怪怪的可能要重新去看一下AVL tree了
也可以上wiki看就好
http://en.wikipedia.org/wiki/Avl_tree
這兩題你的疑問應該都可以在裡面找到答案
: 第14題
: B選項為何是錯的?
: 而C選項為何是對的?
B選項
最糟狀況我覺得應該是n 不是logn
每個點都分開的時候就得花n
C選項..其實我覺得問為何是對的有點難回答
因為看起來就沒哪裡敘述錯誤XD
: 第15題的E選項為何是對的?
跟AVL tree類似 他就是對的.
: 第16題
: 所謂的branch factor應該是每個node的degree吧?
: 那為何DE選項是錯誤的?
D選項不一定比較小
有可能會一樣大
你就想像有一個tree長成一直線就會有一樣大的例子了
因為題目說always 所以錯
E選項
branch factor不是degree喔
branch factor會是degree-1 (要扣掉他老爸XD)
: 第17題
: 我得到的答案中AD選項都是對的
: 不知道這兩選項為何是正確的?而B選項為何是錯誤的?
B其實我不知道average是多少
可是最遭狀況O(n) 最好狀況是都1就是了@@..
: 第19題
: 我選的答案是BD，但我得到的答案是AC
: 請大家幫忙解惑~
A應該對 一開始檢察自己 t=1~9的時候各有用加的跟減的檢查一次
所以可以找過全部19個bucket
BCD選項你可能要自己再查一下@@
: 第20題
: 我得到的答案中AC選項都是對的
: 不知道這兩選項為何是正確的?而B選項為何是錯誤的?
A對 當tree完全傾向某一邊的時候就會n^2
如 1
/
2
/
3
...
/
n
那 E(n) = 1+2+3+...+n = n(n+1)/2 = θ(n^2)
B錯 因為就算最佳狀況 每個點也要花logn才能找到
所以至少要 θ(nlogn)
C對
因為最佳大約是長這樣
a
/ \
b c
/ \
d e
找a : 1
找b : 2
找c : 2
找d : 3
找e : 3
1+2+2+3+3 = 11
不會有更好的了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.195