(2/17更新 感謝各位回文及推文的版友們QQ
我把大家說法跟我自己的一些觀點整理一下)
這張幾乎全部考我弱點...
我各種heap其實不是很熟XD
是非:
1.F(沒特別說要怎麼著色 應該False吧?)
jerry大說法:此題可能在問此問題是否為NPC
而考慮2-coloring即為False
FRAXIS大說法:若此題為True 則我們變成確定N!=NP
2.F
3.F
4.F(Fixed size讓我有點猶豫...)
5.F(更正為T)
其實我覺得False的理由是因為不管是不是amortize分析都是O(1)
所以覺得他的語法有瑕疵
但是以事實來說的話應該是True
6.(更新為F)
應該可跑DFS看finish time解? O(V+E)
7.F
External Node要在同一層
有個好網站推薦給大家
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以看大部份會考的資料結構的操作過程
要選T也行
但是equal to 1的情況不會發生
就只能大家自行選擇了
這些老師不能出的稍微好一點嗎 QQ
8.T
9.T(嗎??)
dddm49:complete graph至少砍n-1邊
10.(更新為T)
這邊還是不確定
但是答案是T基本上是肯定的
大家給的圖都是bottom up的2-3 tree
但是top down的操作模式有點不同
https://www.youtube.com/watch?v=2679VQ26Fp4
我只能找到2-3-4的top down但是找不到2-3tree的
我照2-3-4的方法做會遇到尷尬的地方...
還是說對2-3來說兩個會一樣呢?
複選:
11.
BCDE
12.
CE(更新為ACE)
f1256421:Binomisl heap會存指向min的pointer
如果沒有保存就需要用O(logn)
D:他是要合成兩棵Binomial Tree變一棵Binomial Tree,那這選項應該沒意義吧?
如果兩棵樹同level那O(1)就可以合併
若不同level則不一定可直接合併
而如果是合成兩個Binomial Heap應是花O(logn)
13.
BC(更新為DE)
pups003: http://i.imgur.com/pyvKtoS.jpg
str[i]<<(i*2)
為向左shift
14.
CE(D不確定)
D應該是False吧?
這題我考量的點在於他是問paths而不是path的長度
所以感覺比較像是窮舉所有路徑的組合數?
我英文爛爛不是很確定...
15.
CE(目前應該ABCE都是False所以刪去法可能是D)
A:好像大於O(2^n)?
我跟jerry大一樣建出O(n!)之tree
D:因為黑白建期望為logn高度 所以反過來看應該也是50%而不會greter than?
E:我看到這個就以為他是問別種問題XD
16.
DE
B:不太清楚,是八個嗎?
E:感覺要用reduce 但是不知道怎麼設計
感覺我這張錯超多
希望各位高手指正QQ

明天早上才要寫qq

那明天指教一下QQ

6 應該是 false O(n) 連 BFS 都不行了..

15 E是錯的吧 全黑就沒有紅了 然後我寫A是對的全滿的node數是O(2^(n+1)-1)=O(2*(2^n)-1)=O(2^n) 我是這樣看的QQ14 D我有寫 O(log(max(na,nb)+1) 我就把1刪了...12 我有寫A Binomial Heap有指標會指向最小的nodehttp://i.imgur.com/EpDM2n6.jpg 10的圖7 我寫T 因為看到can be =_=

15A沒選 一題意他的full node的子點會隨著level增加然後我就推出了一個n!的node數QQ 6.false跟F大一樣

11B為什麼錯啊？？12A好像有兩種說法，O(log n)是指沒有指標只想最小node的版本，所以要checklist n個root,但是洪逸書上寫的是有最小node指標的版本，只要O(1)13我是這樣想 http://i.imgur.com/pyvKtoS.jpg<<是shift left

13 e也是對的吧想問第5題 雖然我也是選F 但不太確定概念是否正確

13e我手誤忘了寫哈哈

11b 是因為要先找到last前一node. 要花O(n)

懂了，感謝d大，另外5我寫true，wiki上也是寫「work in constant amortized time」

insert 的 amortized complexity 是O(1) 但扣掉之後我就不太清楚分攤成本是多少了有看到Horowitz寫複雜度是O(i+c+dk+(dm+d)logi)

6是true喔！如果是DAG就走一次topology即可

false吧 要O(V+E)不是嗎

因為題目用can，我想說edge最少是(n-1)，所以就選了

7寫T +1 想說小於等於敘述對12題c資結和演算不同 d我有寫@@16題 b後來查是正八面體 一堆正三角形那個 順便問一下16d

7是true吧2-3-4樹 外部結點高度相等

可是7 兩邊高度不能相差1吧

有道理 那又是題意問題惹QQ

想問4為什麼false 如果array是sort過的而且是遞減 這樣也沒辦法嗎

如果sorted且知道最後一個為min那就可以但是一般來說不行我覺得即使用can也有點太牽強 不足以讓我選T哈哈

題目講的是一般的情況 所以不能自己加條件

15 所以台大的TREE高度要從0開始看喔@@

台大題目寫起來都是這樣的 或你直接用Fh+2-1來看更保險

可是Fh+2-1看也不能確定是0開始還1開始吧QQ

古代台大電機題目是假設root是1

只好看他會不會說了冏

像這題 就h=3 算F5-1 就避掉root是0還是1開始的問題了上一行講錯了這樣必須要h=4 才會是7個node啊因為洪逸很常用h=5 12個點的例子 所以我看到7個點直覺就是 h是4才對

我寫成F5=8了= =所以算錯QQ