如题
选择题上来跟大家对对看
顺便问问
1. 3
2. 4
3. 3
4. 14
5. 235
6. 1
7. 134
8. 1245
9. 1234
10. 4
11. a)
1. 将input两两分组，input = 偶数分成n/2组，input = 奇数则分成[n/2]+1组
2. 将这些两两一组先比出大小
3. 将每组大的和大的比，小的和小的比
4. 递回做step3
5. return (min,Max)
b)
(3n/2) - 2
12. 看不懂题目中第二句的叙述，估计是用dp做类似rod cutting
13.
14.
a)
b)
o
/ | \
o o o
/ | \ / | \ / | \
o o oo o oo o o
c) 用矛盾证法，如果说center不在T的diameter里面的话，会违背题目对center的
定
(radius为T中的min，如果T的diameter长度一定会超过radius，那表示这条路
径?
radius)
15. a)
不太确定题意，但应该是在说set cover
u = {1,2,3,4,5,6,7,8}
F1 = {1,2,3,4}
F2 = {5,6,7,8}
F3 = {1,3,4,5,6}
F4 = {1,7,8}
F5 = {2}
greedy: C = {F3, F4, F5}
optimal = {F1, F2}
b)
given a subset D{Fi~Fj}，可以在polynimal time(O(n))确定是否每个元素都在
u?