作者yupog2003 (屁股)
看板Grad-ProbAsk
標題[理工] 105清大資工 計算機科學 對答案
時間Thu Jan 19 16:04:01 2017
發現自己字太醜，弄成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: 4.C transitive沒有R2吧 01/20 10:34
→ yupog2003: 我怎麼覺的應該有@@有(1,1),(1,2)=>有(1,2) ok 01/20 11:25
→ yupog2003: 阿阿我看出來了有(2,1),(1,2)但沒有(2,2)感謝w大 01/20 11:26
推 DZASHIANG: 請問1.E是16棵二元樹嗎？他這樣問是畫任意一棵都可嗎 01/20 14:25
→ yupog2003: 我覺得應該是畫出兩棵符合要求的然後跟老師說： 01/20 15:54
→ yupog2003: 你看看，這樣不會唯一的概念 01/20 15:54
→ hypnos135g: E. 找根A及左右子, 01/20 15:58
→ hypnos135g: A(BDE)(CFHGI) 01/20 15:58
→ hypnos135g: (EDB)(HFIGC)A 01/20 15:58
→ hypnos135g: 左:BDE EDB 唯一 01/20 15:58
→ hypnos135g: 右:C(FH)(GI) ...2*2=4種 01/20 15:58
※ 編輯: yupog2003 (219.85.61.62), 01/20/2017 16:11:49
→ hypnos135g: 我好像弄錯了左好像也不唯一 01/20 16:19
→ yupog2003: 好像BDE可以扭來扭去的樣子，不過這題3分，這樣畫畫不 01/20 16:21
→ yupog2003: 完，我個人認為畫兩個就好 01/20 16:21
※ 編輯: yupog2003 (219.85.61.62), 01/20/2017 16:23:07
→ yupog2003: 這樣可以回答D大的問題了，應該是16棵沒錯 01/20 16:28
→ DZASHIANG: 感謝回答，另外y大 2.A這樣寫是不是怪怪的，若G只有點 01/20 17:09
→ DZASHIANG: 沒有邊，他的反身遞移包關係矩陣元素會全為0 01/20 17:09
→ yupog2003: 2.A如果G只有點沒有邊的話，會是單位矩陣，對角線為1 01/20 17:18
→ yupog2003: 其他為0 01/20 17:18
→ yupog2003: 根據我的定義，因為每個點到自己都有邊長為0的path 01/20 17:18
→ yupog2003: 所以對角線都填1 01/20 17:18
→ yupog2003: 阿reflexive本來就自己跟自己要算進去，所以應該沒錯 01/20 17:20
→ yupog2003: 其實我一開始是寫aij=1, if 存在從vi到vj的path 或 01/20 17:21
→ yupog2003: i=j，aij=0,otherwise 01/20 17:22
→ yupog2003: 貼到imgur的是我從課本抄的定義，雖然應該是一樣的東西 01/20 17:23
→ DZASHIANG: 我寫的跟樓上你寫的這個一樣 01/20 17:31
→ DZASHIANG: 我以為要有selfloop才有邊長為0的path@@ 01/20 17:34
→ yupog2003: 其實我覺得我一開始寫的比較好懂，洪逸那本寫>=0還要想 01/20 17:35
→ yupog2003: 半天，也有可能造成你上述說的狀況... 01/20 17:35
※ 編輯: yupog2003 (219.85.61.62), 01/21/2017 16:18:26
推 k2shouai: 5.B(a) if SAT is polynomial time solvable則P=NP 01/22 00:11
推 k2shouai: 5.B(b) 只能證明X為NP-hard 01/22 00:13
→ yupog2003: 阿阿對，我打錯了，我在打什麼... 01/22 18:16
※ 編輯: yupog2003 (219.85.61.62), 01/22/2017 18:18:44
→ yupog2003: 5.B(b)感謝提醒，這個觀念老是疏忽... 01/22 18:19
推 kyuudonut: 5(A) 並不是karatsuba演算法ㄛ 01/27 17:00
推 a80093119: 6 B不是17嗎@@?! 01/28 17:53
→ DLHZ: 是51 你直接算也能知道 就是51 12/04 17:31
→ DLHZ: Karatsuba哪有錯 12/04 17:33