: 是非:
: 1.F(没特别说要怎么着色 应该False吧?)
写F 但我的理由是 它取omega 所以k取大一点的话 就不满足了
: 2.F
: 3.F
: 4.F(Fixed size让我有点犹豫...)
: 5.F
是因为写rarely called才选F吗 我选T
: 6.??
我选T诶 感觉跟林立宇老师讲的Tree上找diameter有点像
等下再问问她
: 7.F
感谢dddm49帮助厘清观点
B-tree的External Nodes必须在同一level所以它写can be less than or "equal to 1"
是错的
: 8.T
: 9.T(吗??)
感谢dddm49的解释
Kn图至少要砍n-1个边才会不连通
: 10.Top-Down 2-3-4ok 但是2-3就不是很确定 希望高手画一下 囧
T
感谢jerry031181、odanaga解释
画法照level-order是 7、35、9、12、4、6、8、10
*2-node 3-node指的是external node数
: 复选:
: 11.
: BCDE
感谢jerry031181解释
: 12.
: CE
A DS说O(1) Algo说O(logn) =""= 我看了一下wiki后决定选了
D 就是Merge 2个BinomialTree 我有选
: 13.
: BC
: 不熟c++的写法
: t+=(str[i]<<(i*2))
: 等于
: str[i] = 2*i
: t+=str[i]
: 吗?
E说的没错吧 就新增加的100-199slot不会用到
其他不太确定orz
: 14.
: CE
: D应该是False吧?
D我有选诶 假如到leaf的path有长有短 那就是取max 求高手解释
: 15.
: CE
: A:好像大于O(2^n)?
: D:因为黑白建期望为logn高度 所以反过来看应该也是50%而不会greter than?
A看不懂..
C是错的 h=4时才会是7
E是错的吧 level-order建树 黑黑红红红黑黑 不会是2*r+1
因此我有选D.. 但不会证
: 16.
: DE
: B:不太清楚,是八个吗?
: E:感觉要用reduce 但是不知道怎么设计
D觉得写exponential怪怪的不敢选诶 求解释

15c没定义root从0还1开始算 从0的话是正确的9的话应该是问最少去掉多少边才能使complete graph 不连通所以应该是T

10不是T吗 2-node的意思不是branch factor为2吗@@1.我的想法是 他想问coloring是不是NPC吧lower boundn^k是讲是不是有polynomial解 可是2color有 所以选F

10是T

5.binomial heap不是除了insert,Dec key外其他op都花O(logn) 所以应该还是Logn吧问一下为什么14d 还要取log 到树叶的path=leaf数吧leaf 最多不是到约1/2的node 所以感觉O(max na,nb))

14(D)同楼上在DS里binomial heap是insert和combine "tree"是O(1) actual and amortized

11b 还要maintain last还是O(n) E确认空只要O(1)把最大删除=删last node 但single link不知道前一点所以要花O(n)去找到下一个last node阿

感觉第5题还是没有一个比较合理的解释他是问假设insert很少被called 那f heap 的各种operation的amortized time complexity吧 还是我理解有误我知道insert是O(1)没错

求其他高手解释了qq

12题 merge要看是不是采用lazy merge吧QQ第7题10~-2插入 再将-2,-1删除http://i.imgur.com/9aSb9ts.jpg 应该长这样?

你这样external node就不在同一层啦

高手好多 感动QQ

没事 我脑残了QQ 上面图也是错的

F5应该是5唷 不是8

对诶= = 我在讲什么咦 那这样的话要h=4 F6-1才会是7啊 ；；

如果 insert 很少被 call 那 heap 里面根本没什么元素啊..

那感觉就是O(1)了 谢谢F大

http://mathworld.wolfram.com/CliqueNumber.html 16(B)