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

PAGE6

PAGE

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

姓名：___________________学号：___________________

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

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

下列描述，错误的是：

线性规划可在多项式时间内求解；

0-1规划可在多项式时间内求解；

整数规划采用的算法是分支限界

线性规划具有强对偶性

设X?是线性规划模型

的最优解，Y?是其对偶线性规划模型的最优解，则X?与Y?的关系是：

CX?BY?B.CX?=BY?C.CX?BTY?D.CX?=BTY?

在用原始-对偶算法求解顶点覆盖的近似解时，会随机选择一条边，并增加此边的y值，直到此边两个顶点中，某个顶点的约束条件等号约束成立，假设两个顶点的约束条件的等号约束都成立，应该选择哪个顶点加入顶点覆盖集：

两个顶点都加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除

第一个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除

第一个约束条件对应的顶点加入顶点覆盖集，但只和该顶点相连的边从Ey中删除

第二个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除

下图从s到t的最大流是多少：

A.8B.7C.6D.5

下图节点1，2,3,4，的中介中心性：

1，2.5，2，1.5;

1，1.5，2，1;

0，1.5，3，1;

0，2.5，3，1.5;

关于规约有下面三种陈述，则：

(b)对(a),(c)错B.(a),(b)对，(c)错C.(b),(c)对，(a)错D.(a),(c)对，(b)错

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

团问题B.子集和问题C.最大流问题D.0-1整数规划

在满足三角不等式的情况下，设G为完全图，G’也是完全图，且是G的子图，以下的描述错误的是：

图G的最小生成树的权重小于其旅行商回路的权重。

图G的旅行商回路的权重大于对其最小生成树按照先序遍历形成的回路。

图G的旅行商回路的权重小于等于其最小生成树权重的2倍

图G′上的旅行商回路小于等于图G的旅行商回路

请计算下图两个无权图的模块度：

20/196,36/196B.24/196,40/196C.40/196,36/196D.24/196,36/196

下面对集合覆盖的近似算法描述错误的是：

简单集合覆盖的近似算法是贪心算法。

该不等式成立是因为最优集合覆盖R*中包含所有的元素，且有可能对某个（些）元素包含多次。

该不等式成立是因为贪心选择。

该等式成立，说明近似算法覆盖所有的元素一次且仅一次。

对于最小圆覆盖，以下说法错误的是：

在最小圆覆盖算法中，当增加一个新的点pi时，如果点pi没有被当前圆所覆盖，则可以通过增大最小圆，将这个点包含在圆的内部。

最小圆覆盖的随机算法是为了避免落入最差的情况。

最小圆覆盖的最差情况下，复杂度为n3。

最小圆覆盖的期望复杂度为n。

对于弗里瓦德算法，下面描述错误的是：

弗里瓦德算法是蒙特卡洛算法。

弗里瓦德算法需要生成一个包含0,1元素的随机向量，如果生成的是全1元素，判断A*B*r=C*r重新变成了判断A*B=C，所以结果一定是正确的

弗里瓦德算法得出正确解的概率大于等于1/2.

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

对外汇兑换问题的在线算法描述错误的是：

当Φ较大时（如100）小数兑换能够比整数兑换得到更好的竞争度（更好收益）；

按照小数保守价格策略，如果第一天就达到最高的汇率，则收益最好；

按照小数保守价格策略，最后一天之前兑换的比例是固定的（无论汇率如何变动）

只要知道U和L的比值Φ，可得的在线算法

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

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

二、计算、简答题（共42分）

求如下线性规划的对偶问题(6分)

请用原始-对偶算法求图中的顶点覆盖近似解，写出具体的流程，如流程中涉及随机选择某个节点或者某条边，可做假设。（8分）

LPA算法对图进行社群划分，设节点的遍历顺