大家好
因为问题规模都不大，整理在一起问好了，除了 103 那题 ...
1、101考题
http://i.imgur.com/2ywV1Fz.jpg
A 选项， sorted 过的 link list 搜寻时间可以到 O(logn)，所以这题应该是这个选项
错
可是 E 选项删除最大元素要找到最大元素的前一个是不是要 O(n)，找到之后才能改掉呢
？
2、102考题
http://i.imgur.com/VocGzRN.jpg
这题答案是 A 嘛？套用 Folyed 多项式时间就有解了，根据定义选 A 没错吧（bound不
紧不敢选 = =）
3、103考题
http://i.imgur.com/o7VXMnm.jpg
这题我没什么想法 >< 麻烦高手指点，我只想到多边形判断座标点在里面还是在外面的方
法
4、104考题
http://i.imgur.com/tgoyxcc.jpg
这题我写 B，我想的是着色他没有要求最小着色数只要求相邻颜色要不同，那就一个点一
个颜色给他，只要 O(1) 的时间即可。我这样想会很危险嘛 @@
若不能这样想麻烦纠正 感谢 ><

1. array才能用O(logn） A是对的2.B 不需要到2^n3.好像类似103台大资工的最后一题 我也不会orz

1(e) 如果 list 是可以修改的话 你只要把他下一个点的资料移到要被删除的节点里面 然后把下一个节点删除就好了3 是 power diagramhttps://en.wikipedia.org/wiki/Power_diagram

4. 但不知道点与点有没有相邻啊 而且要给这个点颜色也要先经过它吧 不会是O(1)

4的话是 false 因为如果是 true 的话就等价 P != NP

p.s. 可以附一下年份 这样之后的考生有相同问题的比较好找

我也想知道那种bound不够紧的要不要选欸第二题我也是照定义选true

所以第一题是B吗

疑想问一下第2题，我是分别用matrix和list表示来想的分别O(1)和O(e)都不是就选F了啊不对它是path我看错了，不过这应该作DFS就够了吧