(2/17更新 感谢各位回文及推文的版友们QQ
我把大家说法跟我自己的一些观点整理一下)
这张几乎全部考我弱点...
我各种heap其实不是很熟XD
是非:
1.F(没特别说要怎么着色 应该False吧?)
jerry大说法:此题可能在问此问题是否为NPC
而考虑2-coloring即为False
FRAXIS大说法:若此题为True 则我们变成确定N!=NP
2.F
3.F
4.F(Fixed size让我有点犹豫...)
5.F(更正为T)
其实我觉得False的理由是因为不管是不是amortize分析都是O(1)
所以觉得他的语法有瑕疵
但是以事实来说的话应该是True
6.(更新为F)
应该可跑DFS看finish time解? O(V+E)
7.F
External Node要在同一层
有个好网站推荐给大家
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以看大部份会考的资料结构的操作过程
要选T也行
但是equal to 1的情况不会发生
就只能大家自行选择了
这些老师不能出的稍微好一点吗 QQ
8.T
9.T(吗??)
dddm49:complete graph至少砍n-1边
10.(更新为T)
这边还是不确定
但是答案是T基本上是肯定的
大家给的图都是bottom up的2-3 tree
但是top down的操作模式有点不同
https://www.youtube.com/watch?v=2679VQ26Fp4
我只能找到2-3-4的top down但是找不到2-3tree的
我照2-3-4的方法做会遇到尴尬的地方...
还是说对2-3来说两个会一样呢?
复选:
11.
BCDE
12.
CE(更新为ACE)
f1256421:Binomisl heap会存指向min的pointer
如果没有保存就需要用O(logn)
D:他是要合成两棵Binomial Tree变一棵Binomial Tree,那这选项应该没意义吧?
如果两棵树同level那O(1)就可以合并
若不同level则不一定可直接合并
而如果是合成两个Binomial Heap应是花O(logn)
13.
BC(更新为DE)
pups003: http://i.imgur.com/pyvKtoS.jpg
str[i]<<(i*2)
为向左shift
14.
CE(D不确定)
D应该是False吧?
这题我考量的点在于他是问paths而不是path的长度
所以感觉比较像是穷举所有路径的组合数?
我英文烂烂不是很确定...
15.
CE(目前应该ABCE都是False所以删去法可能是D)
A:好像大于O(2^n)?
我跟jerry大一样建出O(n!)之tree
D:因为黑白建期望为logn高度 所以反过来看应该也是50%而不会greter than?
E:我看到这个就以为他是问别种问题XD
16.
DE
B:不太清楚,是八个吗?
E:感觉要用reduce 但是不知道怎么设计
感觉我这张错超多
希望各位高手指正QQ