[理工] DS台大電機丙104年

[wanedcol (草化)]

看完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
推 dddm49: 6的話我的想法是要找所有點+邊 所以是O(V+E)
→ dddm49: 11的話B應該是錯的  因為你要刪last 還是要找到last前一點
→ dddm49:  為O(n)
推 dddm49: 12我認為都要用worst case去看 所以find min為O(logn)
我也有想到因為最小不一定就是最完整的那棵樹
推 dddm49: 可以再討論看看
推 pups003: 6 wiki上寫的是O(n^2)
推 WES2163818: 6不就topological sort on DAG..
推 dddm49: 對啊 那不就是O(V+E)?
推 pups003: 你說的沒錯XD
所以第6題的內容是敘述拓樸sort的內容是嗎？
感謝各位
※ 編輯: wanedcol (180.217.4.201), 02/14/2016 12:42:39
推 dddm49: 12的D在ds中好像是O(1)
→ dddm49: 因為比較兩棵tree root. 較小的為新root合併 應該不用再作
→ dddm49: 調整
推 janus7799: 12(C)Horowitz裡說有一個指標min恆指向最小值。15(A)
→ janus7799: 我覺得前面的廢話意思是指degree=(k+2)
→ janus7799: 想請教各位第一題color problem的時間複雜度
推 dddm49: 我以為有指標指向min的是F堆積
→ wanedcol: 什麼意思
→ dddm49: 喔 沒事 我搞錯 B heap也可增加一指標永遠指向最小值