1、( 5分 )
对于给定函数1.png和2.png 如下表，
3.png
其中满足关系4.png的组号是：
A、 1
B、 2
C、 3
D、 4
E、 5
2、( 5分 )第1题中，满足关系1.png的组号是：
A、 1
B、 2
C、 3
D、 4
E、 5
3、( 1分 )
给定下述关于分治策略算法的时间复杂度1.png的递推方程
2.png
从上述方程中看出划分后的子问题有几个？
4、( 1分 )第三题中子问题规模是1.png，括号中应填：
5、( 1分 )第3题中，划分子问题并对子问题的解进行综合的工作量是 ：
A、
1.png
B、
2.png
C、
3.png
D、
4.png
E、
5.png
6、( 2分 )第3题中，最小的子问题规模和对最小子问题的工作量分别是：
A、 n, 1
B、 1, 1
C、 1, n
D、 1, n/2
E、 n/2, 1
7、( 5分 )第3题中递推方程的解是111111111111.png:
A、
a.png
B、
b.png
C、
c.png
D、
d.png
E、
e.png
8、( 10分 )
下述Find-Second-Min算法是找第二小算法. 输入是n个不等的数构成的数组S，输出是第二小的数SecondMin。在最坏情况下，该算法做多少次比较？从下述备选的答案中选择正确答案的标号填入（ ）内。
111111111111.png
A、
a.png
B、
b.png
C、
cs.png
D、
d.png
E、
e.png
9、( 10分 )
假设L含有n个不同的元素，其中2015-12-10_184303.png,k 为非负整数。如果已知x在表L中，且在L的每个位置的概率相等，那么用顺序搜索算法查找元素x，该算法平均情况下的比较次数是多少？从下面备选的答案中选出正确答案的标号填入括号内。()
A、
1.png
B、
2.png
C、
3.png
D、
4.png
E、
5.png
F、
6.png
10、( 5分 )设n是k的倍数，有k个排好序的数表1.png，每个数表都有n/k个数，现在需要把它们合并成一个含有n个数的排好序的数表。假设n个数彼此不等，并且归并长为m, n的两个数表最坏情况下的比较次数是2.png。使用顺序归并算法，即先归并3.png和4.png，接着把得到的数表2015-12-10_184826.png与2015-12-10_184805.png归并，再把得到的数表2015-12-10_184839.png与2015-12-10_184845.png归并，…，直到得到2015-12-10_184852.png。
例如2015-12-10_184905.png，那么归并过程是：2015-12-10_184927.png。当2015-12-10_184937.png顺序归并成数表2015-12-10_184945.png的过程中在最坏情况下的比较次数记作2015-12-10_184957.png,那么2015-12-10_185007.png满足递推方程和初值是:
2015-12-10_185018.png
从下述答案中选择适当的答案填入上面的括号内。
A、
b.png
B、
a.png
C、
c.png
D、
d.png
E、
E.png
11、( 10分 )以比较做基本运算，题11中的顺序归并算法最坏情况下的时间复杂度是（ ）。
A、
1.png
B、
2.png
C、
3.png
D、
4.png
E、
5.png
12、( 5分 )第10题的归并数表问题可以采用二分归并的算法。不妨设k为2的幂。将k个数表两两分组，即归并a.png得到k/2个归并好的数表，然后对这些数表再两两分组，继续归并。例如2.png，那么归并过程是：3.png 。以比较做基本运算，采用这种归并算法，最坏情况下的时间复杂度是( )。
A、
b.png
B、
c.png
C、
a.png
D、
d.png
E、
e.png
13、( 5分 )一条水平方向的公路上有n个地点，设公路的起点位置为0，对于1.png，地点i到起点的距离是2.png，且满足3.png，地点i放置广告牌的收益是4.png。上述距离和收益都是正整数。如果要求任意两个广告牌之间的距离至少是5公里，应该如何选择放置广告牌的位置使得总收益达到最大？
将问题的解看做0-1向量5.png，xi=1当且仅当在地点i放置广告牌。那么该问题的目标函数和约束条件分别是 ( )。
A、
a.png
B、
b.png
C、
c.png
D、
d.png
14、( 5分 )对第13题使用动态规划算法，设考虑前k个地点的最大收益是1.png那么递推方程是（ ）。
A、
b.png
B、
c.png
C、
d.png
D、
a.png
15、( 5分 )第14题的递推方程的初值是1.png。
A、
a.png
B、 0
C、 1
D、
b.png
16、( 5分 )
考虑第14题的动态规划算法的实现。如果在算法运行前通过预处理，对于1.png，将标号小于k、距离地点k至少5公里且离它最近的地点j找到（若不存在这样的j，则令j=0），并把这些数据存起来。例如初始数据是：2.png，那么预处理的结果是：
3.png
上述带有预处理的算法在最坏情况下的时间复杂度是( )。
A、
e.png
B、
b.png
C、
c.png
D、
d.png
E、
a.png
17、( 5分 )
有n项任务的集合1.png，每项任务需要先放到机器A上进行预处理，然后再放到机器B上加工。第2.png项任务的预处理和加工时间分别是3.png和4.png, 这里的3.png和4.png都是正整数。如果机器A只有1台，机器B的数量不限，即只要任务i在机器A上加工完毕，就可以立刻放到某台机器B上加工。问如何安排这些任务在机器A上的处理顺序，以使得总的加工时间最短？
总加工时间的含义是：从0时刻机器A开始预处理，到t时刻最后一台机器B停止工作，即全部任务在机器A、B上的加工都结束，那么总加工时间就是t。设该问题的解是n项任务安排在机器A上的加工顺序，用排列5.png表示。那么在机器A上排在第j位加工任务的完成时间是( )。
A、
a.png
B、
b.png
C、
c.png
D、
d.png
18、( 5分 )对第17题的调度问题使用贪心法求解，在机器A上安排加工顺序，正确的贪心策略是( )。
A、 在机器B上加工时间长的优先安排
B、 在机器A上加工时间短的优先安排
C、 在机器A和B上加工时间之和小的优先安排
D、 在机器A的加工时间减去在机器B的加工时间，这个差越小的越优先安排
19、( 3分 )
用回溯算法计算下述不等式的非负整数解
1.png
设解向量是，令2.png分别是在算法开始时刻确定的4.png的取值范围，那么 分别是集合（ ）。
A、
1.png
B、
2.png
C、
3.png
D、
4.png
20、( 2分 )第19题的搜索树在部分向量的结点1.png处的约束条件是：
A、
2.png
B、
1.png
C、
3.png
D、
4.png
21、( 5分 )
第19题的不等式有()个解。
A、 13
B、 14
C、 15
D、 16
E、 17