《高级算法设计与分析》试卷及答案 卷2.docx

PAGE6

PAGE

《高级算法设计与分析》期末试卷（试卷2）

姓名：___________________学号：___________________

要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号

一、选择题（每题3分，共45分）

下面问题不能用动态规划求解的是：

A：0-1背包问题B:矩阵连乘问题

C:两点之间最长路径问题D:最大子数组问题

贪心算法能够获得最优解的是：

A:旅行商问题B:0-1背包问题

C:最大团问题D:最小生成树问题

对如图所示的旅行商问题，用分支限界法求解时，其最优下界为：

A:16B:18C:13D:15

将下面非标准型的线性规划转化为标准型：

B.

C.D.

线性规划问题如下，

其对偶问题为：

B.

D.

对于随机算法的描述，以下描述错误的是:

A.算法运算很快B.算法有一定的概率产生错误的结果

C.算法的输出是确定的D.随机快速排序的期望时间复杂度为O(nlogn)

在随机快速排序算法中，设S(i)表示集合S中阶为i的元素，下面描述错误的是（注：ji）:

只有S(i)和S(j)这两个元素其一被选为主元素的时候，他们才进行比较

当元素S(k)(ikj)被选为主元素时，S(i)和S(j)肯定不会进行比较

S(i)和S(j)比较的概率为：pij=2/(j-i+1)

当元素S(k)(kj)被选为主元素时，S(i)和S(j)肯定会进行比较

以下对规约的描述错误的是：

，如果B是P问题，则A一定也是P问题

，如果A是NPC问题，则B一定也是NPC问题

如果A问题可以归约为B问题，则A问题和B问题必须是一一对应关系

规约函数必须是多项式时间复杂度的函数

以下问题不是NPC问题的是：

A.小数背包问题B.最大团问题

C.旅行商问题D.整数规划问题

在团问题的NP难证明过程中,以下说法错误的是：

3合取范式可以归约为团问题

归约的过程中，3合取范式会归约为一个特殊的图，所以我们只能说明这个特殊的图的团问题是NP难的，而无法证明所有的图的团问题都是NP难的

在规约的过程中,一个子句对应一组顶点，对于任意两个在不同组的顶点，如果满足“这两个顶点不是‘否’的关系”这一条件，就用一条边连接

如果3合取范式如果有k个子句，则需要证明图中有规模为k的团

针对集合覆盖问题，设wi为子集Si的权重，xi=0表示没有选中子集Si，xi=1表示选中子集Si。则集合覆盖问题建模成整数规划形式为（注：n为元素的个数，m为子集的个数）：

B.

C.D.

下面对旅行商问题（满足三角不等式）的近似算法描述错误的是：

算法的基本思想是：生成最小生成树，按对树进行先序遍历的顺序访问节点。

最小生成树的总代价小于等于旅行商回路的总代价

对T进行按先序往返遍历，其总代价小于等于2倍的旅行商回路的总代价

算法的总代价大于等于对T进行按先序往返遍历的总代价

下面对在线算法和离线算法比较，以下描述错误的是：

即使数据在计算时都已知，也可以采用在线算法来达到更好的结果

在线算法通常是近似算法

通常通过和离线最优算法的比较来判断在线算法的好坏，如果在线算法的代价Con和离线算法的代价Coff有关系，则称在线算法在实例IA上为α竞争度算法

最小生成树在线算法可通过贪心算法实现

在租卖问题的在线算法中，b=2为购买价格，l=3为天数，则所有的确定性算法如下表，其中Ai为第i天购买，Ii为滑雪场最后一天开放为第i天，其中错误的是：

最好的确定性算法为A2和A?，都是3/2竞争度

在线算法中，以1/3的概率执行A1策略，2/3的概率执行A2策略，可以实现竞争度4/3

在线算法中，以2/3的概率执行A1策略，1/3的概率执行A2策略，也可以实现竞争度4/3

本例子在线算法的最优竞争度为4/3

下面对禁忌表有哪些信誉好的足球投注网站（Tabusearch）算法描述错误的是：

算法的基本思想是标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程

那些目前在禁忌表的解或者求解过程是无条件被禁止的

进入禁忌表的解或者求解过程在一定的时间后会被解禁

禁忌表有哪些信誉好的足球投注网站每次迭代总是在前一次迭代的领