Re: [理工] 成大資工96~100

看板Grad-ProbAsk作者Byzantin (拜占庭)時間14年前 (2012/02/24 21:02)推噓8(8推 0噓 17→)

留言25則, 7人參與討論串2/2 (看更多)

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

02/24 21:12, , 1^F

02/24 21:12, 1^F

→

Byzantin

02/24 21:17, , 2^F

02/24 21:17, 2^F

推

l998

02/24 21:25, , 3^F

02/24 21:25, 3^F