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

PAGE6

PAGE

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

姓名：___________________学号：___________________

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

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

求解整数规划，可通过先将整数规划进行松弛，之后采用下面的哪种算法：

动态规划B.分支限界C.回溯D.贪心

在近似算法中，可采用以下哪种算法：

动态规划B.分治C.回溯D.贪心

对于弱若对偶性,以下表达正确的是，x为原问题（最大化）的解，y为对偶问题（最小化）的解：

B.

D.以上都不对

线性规划问题如下，

其对偶问题为：

B.

D.

下面描述正确的是：

整数规划问题是NPC问题，线性规划问题是NP问题

整数规划问题是NPC问题，线性规划问题是NPC问题

整数规划问题是NP问题，线性规划问题是NPC问题

整数规划问题是NP问题，线性规划问题是NP问题

设A问题可以归约到B问题，则以下说法错误的是：

如果A问题为NPC问题，则B问题必为NPC问题

A问题的任何一个实例x可以通过函数f转化为B问题的一个实例，且f为多项式时间

B问题的任何一个实例x也可以通过函数f’转化为A问题的一个实例，且f’为多项式时间

algoA代表A的算法，algoB代表B的算法，则algoB(f(x))=algoA(x)

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

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

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

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

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

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

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

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

如果算法不删除相似的子集和，是可以得到精确的结果的

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

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

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

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

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

此近似算法是近似因子为2的近似算法

随机快速排序算法中，元素S(i)和元素S(j)进行比较的概率是多少（注：S为排序好的元素序列）？

B.C.D.

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

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

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

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

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

G=(V，E)为多重图，C是最小割且|C|=k，以下描述错误的是：

G中任意顶点的度大于等于k

最小割即为最少的变数集合，除去这些边数，原图变成不连通

随机算法输出最小割的概率大于2/n2

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

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

算法复杂度为O（n2）

算法竞争度为O（n）

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

在租卖问题的在线算法中，b=2为购买价格，l=3为天数，则所有的确定性算法如下表，其中Ai为第i天购买，Ii为滑雪场最后一天开放为第i天，现有随机实例概率（I1=1/3,I2=2/3），以及随机算法概率（A2=2/3，A3=1/3），则在此随机实例下A2的竞争度，以及此随机算法在实例I2的竞争度分别为：

（4/3,5/3）B.（4/3,4/3）C.（5/3,4/3）D.（5/3,5/3）

下面对蚁群系统算法（AntColonySystem）描述错误的是：

采用利用和探索相结合，在利用时，选择最优路径，探索时，按选择概率选择路径

全局更新只更新最优路径上的信息素

局部更新时，信息素并不挥发

在路径选择时，即考虑信息素，也考虑路径长度

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

设某指派问题的效率矩阵为：

其中第i行表示第i个人被指派各个任务的效率，而第j列第j个任务被分配到各个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用。（10分）

某市下设八个区,下表给出救护车从