看完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)全黑的话就不成立了吧
有劳各位大大了

6的话我的想法是要找所有点+边 所以是O(V+E)11的话B应该是错的 因为你要删last 还是要找到last前一点为O(n)12我认为都要用worst case去看 所以find min为O(logn)可以再讨论看看

6 wiki上写的是O(n^2)

6不就topological sort on DAG..

对啊 那不就是O(V+E)?

你说的没错XD

12的D在ds中好像是O(1)因为比较两棵tree root. 较小的为新root合并 应该不用再作调整

12(C)Horowitz里说有一个指标min恒指向最小值。15(A)我觉得前面的废话意思是指degree=(k+2)想请教各位第一题color problem的时间复杂度

我以为有指标指向min的是F堆积

什么意思

喔 没事 我搞错 B heap也可增加一指标永远指向最小值