作者Byzantin (拜占庭)
看板Grad-ProbAsk
標題Re: [理工] 成大資工96~100
時間Fri Feb 24 21:02:32 2012
Hi, 我想你說的"出好幾年的那4題 True or False"
應該是這一題：
a. In a directed graph G, if vertex x has both incoming and outgoing edges,
its tree in the DFS forest contains more than one vertex.
b. A d-ary heap is like a binary heap, but non-leaf nodes have d children
instead of 2 children. The running time of the efficient implementation
of Extract-Max in a d-ary max heap with n elements is Θ(log n).
d
c. A Hamiltonian Path in graph G passes through each node v∈V exactly once.
Given a directed acyclic graph G = (V,E), its Hamiltonian Path
v1,v2, ... , vn must be a topological ordering of G.
d. In an undirected graph G, if there is a path between two vertices
x and y then in the DFS tree of G, either x is a descendant of y
or y is a descendant of x.
很多人因為沒題目所以無法回答 就幫你打出來讓大家討論了
如果不是指這題也告知一下囉
然後以下是我的看法：
a. 考慮此圖 w←u←v , visit順序為w再u再v
則u有incoming edge及outgoing edge但u的DFS tree只有一個node
因此False
b. True
c. True, 若一Hamiltonian path不是topological ordering
則v1,v2,..,vn存在vi,vj , i<j edge(vj,vi)存在
但這樣會造成cycle 矛盾
d. True
有錯誤請告知了!
※ 引述《wong0101 (汪汪)》之銘言：
: (5)
: 還有資結出好幾年的那4題 True or False
: 我怎麼看到好多版本的答案阿,不知道大家答案寫什麼QQ?
: 看到我打這麼久的份上QQ,請各位高手替我解惑一下吧,先謝謝大家了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.145.187
推 l998:翻以前討論過的結果似乎只有hamilton那個是true 02/24 21:12
→ Byzantin:是喔 錯真多XD 02/24 21:17
推 l998:d. 考慮 x-z-y 從z開始作DFS 則x,y為兄弟 02/24 21:25
→ l998:b. 應該是 d log n 02/24 21:26
→ l998: d 02/24 21:26
→ l998:厄 ..打錯 d應該在log下面也就是以d為底 02/24 21:28
→ Byzantin:可是b在cormen習題有 複雜度沒錯說@@ 02/24 21:28
推 l998:我也決得很怪因為d應該是常數才對 這邊只是我爬文看到的結論 02/24 21:32
→ Byzantin:可以請問文章代碼嗎~ 02/24 21:35
推 l998:我找找 02/24 21:40
推 wong0101:對我就是問這題 謝拉xd,可以在問一下98年計組第五題 02/24 21:52
→ wong0101:為何不需考慮優先權?? RR排班也是可以搭配優先權吧 02/24 21:53
推 s09759017:樓上的意思是會不會被插隊? 02/24 22:01
→ wong0101:答案說P1>P2>..P5>P1這樣輪,But我是寫優先權高的P2先執行 02/24 22:06
推 KobeIsDoggy:RR應該就不用看優先權了 02/24 22:23
→ metalalive:選項B應該是true沒錯,wiki有 (不過好像只有成大會考) 02/24 22:24
→ metalalive:(b小題)我也是把d視為常數 02/24 22:26
→ metalalive:請教Byzantin,C小題意思是不是如果G中存在h.p.且此H.P. 02/24 22:27
→ metalalive:不為 topology sort 的話,把g中的點以topo. sort 從左 02/24 22:28
→ metalalive:排到右,必定存在一個右邊的點會連回左邊的點,形成CYCLE 02/24 22:29
→ metalalive:感謝@@ 02/24 22:29
→ Byzantin:是的 就是這個意思 02/24 23:27