看完103，寫104時感覺又回到正常的出題
雖然今年離103很近
但還是希望不要遇到那個出題教授才好
104有幾題是怎麼想都想不通的
希望各位大大給點指點
(一)是非題
6.The ''dominator''d of a node v in a DAG is a node that
all the paths going from v to any of the sink nodes must
go through d.Let n be the number of nides in the graph,
then finding the set of dominators for all nodes in an
arbitrary DAG can be O(n).
(二)附選題
11.他是在考link list而已嗎
(A)
(B)
(C)合併link list應該是O(n)
(D)有序的刪除O(n)
12.binomial heap/tree
(A)拿最小的當ROOT 故O(1)
(B)false
(C)甘系?
(D)True
(E)採lazy merge的話是嗎?
15.tree
(A)unknown
(B)應該是inorder
(C)我寫TRUE 沒說Root算0還是1
(D)應該部會
(E)全黑的話就不成立了吧
有勞各位大大了

6的話我的想法是要找所有點+邊 所以是O(V+E)11的話B應該是錯的 因為你要刪last 還是要找到last前一點為O(n)12我認為都要用worst case去看 所以find min為O(logn)可以再討論看看

6 wiki上寫的是O(n^2)

6不就topological sort on DAG..

對啊 那不就是O(V+E)?

你說的沒錯XD

12的D在ds中好像是O(1)因為比較兩棵tree root. 較小的為新root合併 應該不用再作調整

12(C)Horowitz裡說有一個指標min恆指向最小值。15(A)我覺得前面的廢話意思是指degree=(k+2)想請教各位第一題color problem的時間複雜度

我以為有指標指向min的是F堆積

什麼意思

喔 沒事 我搞錯 B heap也可增加一指標永遠指向最小值