[理工] DS台大電機丙104年
看完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)全黑的話就不成立了吧
有勞各位大大了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.69.149.15
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455418622.A.A6F.html
推
02/14 11:02, , 1F
02/14 11:02, 1F
→
02/14 11:04, , 2F
02/14 11:04, 2F
→
02/14 11:04, , 3F
02/14 11:04, 3F
推
02/14 11:13, , 4F
02/14 11:13, 4F
我也有想到因為最小不一定就是最完整的那棵樹
推
02/14 11:15, , 5F
02/14 11:15, 5F
推
02/14 11:24, , 6F
02/14 11:24, 6F
推
02/14 11:34, , 7F
02/14 11:34, 7F
推
02/14 11:36, , 8F
02/14 11:36, 8F
推
02/14 12:30, , 9F
02/14 12:30, 9F
所以第6題的內容是敘述拓樸sort的內容是嗎？
感謝各位
※ 編輯: wanedcol (180.217.4.201), 02/14/2016 12:42:39
推
02/14 12:46, , 10F
02/14 12:46, 10F
→
02/14 12:48, , 11F
02/14 12:48, 11F
→
02/14 12:48, , 12F
02/14 12:48, 12F
推
02/14 16:23, , 13F
02/14 16:23, 13F
→
02/14 16:23, , 14F
02/14 16:23, 14F
→
02/14 16:24, , 15F
02/14 16:24, 15F
推
02/14 20:02, , 16F
02/14 20:02, 16F
→
02/15 12:32, , 17F
02/15 12:32, 17F
→
02/15 16:30, , 18F
02/15 16:30, 18F