[理工] 105清大資工計算機科學對答案

看板Grad-ProbAsk作者yupog2003 (屁股)時間9年前 (2017/01/19 16:04)推噓6(6推 0噓 32→)

留言38則, 9人參與討論串1/3 (看更多)

發現自己字太醜，弄成ptt內文版的好了題目： http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/105/1901.pdf 有寫的一起來對答案囉！謝謝大家 1.A post-order:ab+c/de-* pre-order :*/+abc-de 1.B A /|\ / | \ B D G / \ /\ C E F I / H 1.C 45 / \ 37 77 \ / 44 66 / / \ 38 55 70 \ 40 55 / \ 37 77 \ / 41 66 / \ \ 38 45 70 \ 40 1.D A / \ B C / / \ D F G / / \ E H I the tree is unique 1.E A / \ B C / / \ D F G / / \ / \ E H H I I 應該要畫好多張圖才對，H跟I畫那樣代表他們可以出現在那些位置，BDE也可以扭來扭去 pre-order :ABDECFHGI post-order:EDBHFIGCA 都會符合，所以此樹不唯一感謝h大題點 1.F void longestDelay(node* root, int AccDelay){ if (root == null) return; int lDelay = 0, rDelay = 0; if (root -> lchild != null){ longestDelay(root -> lchild, AccDelay); lDelay = root -> lchild -> delay; } if (root -> rchild != null){ longestDelay(root -> rchild, AccDelay); rDelay = root -> rchild -> delay; } root -> delay = max{lDelay, rDelay} + root -> delay; MAX = root -> delay; } 2.A A*之中aij=1, if 存在從vertex i 到 vertex j的path or i=j aij=0, otherwise 2.B All pairs shortest path 2.C yes, 令G=(V1 ∪ V2,E)為bipartite 若G中無cycle，得證若G中有cycle，不失一般性令起點為u1 ∈ V1，若長度為奇數，則終點屬於V2，則終點不為u1，矛盾，得證 2.D 2.E DFS(G) for each vertex v ∈ G.V v.color = white for each vertex v ∈ G.V if v.color = white DFS-Visit(v) DFS-Visit(u) u.color = gray for each vertex ∈ adj[u] if v.color = white DFS-Visit(v) u.color = black insert u in front of list L L is a topological sort 3.A 4,2,9 3.B 9 3.C an=2*4^n, n>=0 bn=4^n, n>=0 4.A 420 4.B an=(1/2)*(8^n+10^n), n>=0 4.C symmetric:R2,R3 anti-symmetric:R4,R5,R6 transitive:R2,R4,R5,R6 更正：R4,R5,R6 5.A karatsuba演算法(沒背) 5.B (a)F, 應為：若SAT為polynomial-time solvable，則P=NP (b)F, 應為：若SAT可reduce to X，且X為NP，則可證明X為NP-complete (c)F, 例如find a Hamiltonian cycle in a graph為NP-complete，但若input graph 為一cycle，則找Hamiltonian cycle只須O(1)，因input graph就是 Hamiltonian cycle 6.A [ 1 1 -1] [ 2 2 1] [-1 -1 3] 6.B 51 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.85.61.62 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484813044.A.CF8.html

→

w181496

01/20 10:34, , 1^F

01/20 10:34, 1^F

→

[理工] 105清大資工 計算機科學 對答案

[理工] 105清大資工計算機科學對答案