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

PAGE

PAGE4

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

姓名：___________________学号：___________________

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

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

目前比较排序所能够达到的最优计算复杂度为：

A：Θ(n)B:Θ(nlogn)C:Θ(n2)D:Θ(n2logn)

哪两个算法需要最优子结构性质

A:分治和动态规划B:分治和贪心

C:动态规划和贪心D:动态规划和回溯

线性规划

的标准形式是：

B.

C.D.

下列标准型化

转化为松弛型:

B.

C.D.

对于随机快速排序,以下描述错误的是:

A.随机快速排序消除或减少了一般快速排序的最坏时间复杂度

B.随机快速排序属于舍伍德算法

C.随机快速排序的时间复杂度一定比一般快速排序的时间复杂度好

D.随机快速排序的期望时间复杂度为O(nlogn)

对于拉斯维加斯和蒙特卡洛算法描述错误的是:

A.拉斯维加斯算法不一定获得解,但如果获得解一定是正确的

B.蒙特卡洛算法可能给出错误解

C.拉斯维加斯算法找到解得概率与算法执行时间成正比

D.随机选择属于蒙特卡洛算法

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

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

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

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

L1代表A的算法,L2代表B的算法,则L1(x)=L2(f(x)),其中f为规约函数

对NPC问题,以下说法正确的是：

A.这个问题是一定是NP问题

B.这个问题一定不是NP问题

C.已经证明这个问题一定是P问题

D.已经证明这个问题一定不是P问题

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

A.欧拉回路问题

B.最大团问题

C.3合取范式

D.0-1背包问题

在团问题(图G)规约为顶点覆盖问题(图)中,以下说法错误的是：

设（u,v）为的任意边，则（u，v）其中至少一个点不属于G的团

设（u,v）为的任意边，则（u，v）其中至少一个点属于的顶点覆盖

如果有两个顶点u,v都不属于的顶点覆盖，则这两个顶点一定属于G的团

图G中有规模为k的团，当且仅当图有规模为k的顶点覆盖

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

通常通过哈密顿回路来规约旅行商问题

在规约的过程中,目的是找一条成本为n(n为边数)的旅行线路

在规约的过程中,需要将原图扩展成一个完全图

扩展成完全图后,原来的边设成本为0,扩展的边设成本为1

下面对子集和的近似算法描述错误的是：

如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，则{x1,x2,x3,…,xi,xi+1}所有的子集和为。

在计算过程中，为了减少子集和的规模，算法通过去除大于目标值的子集和，以及删除相似子集和的方法实现

如果算法过程中，不删除相似的子集和（仅仅去除大于目标值的子集和），是可以得到精确的结果的

子集和的近似算法只是一个多项式时间近似算法，而不是一个完全多项式时间的近似算法

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

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

在线算法通常是近似算法

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

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

下面对最小生成树在线算法描述错误的是：

最小生成树在线算法是一种贪心算法

算法复杂度为O（n2）

算法竞争度为O（n）

生成树在线算法生成树中第k长的边长度小于等于2l/k，其中l为最小生成树的代价

下面对模拟退火描述错误的是：

Greedy算法，但是加入随机因素

若目标函数在第i+1步移动后比第i步更优，则总是被接受

以一定的概率来接受一个比当前解要差的解，用于跳出局部最优解

这个概率随着温度的降低，变的更大，以便更快的跳出局部最优解

二、计算、建模题（共40分）

已知线性规划问题,其对偶问题的最优解为*=(y1,y2,y3,y4)=(0,0,4,4)，试用对偶的互补松弛性求原问题的最优解（10分）

min8x1+12x2

s.t.

2x1+2x2≥2

2x2≥1

x1+x2≥5

x1+2x2≥6

x1,x2≥0

某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包