电子科技大学研究生算法设计与分析拟考题及答案评分细则(1)

一、计算题或者简答题

1. 有一些区间段 (0,3), (1,4), (3,5), (6,8),(7,9)，给出个数最多的一组相容的区间段（两个区间相容当且仅当两个区间的交集为空）。

2. 如下可满足问题（SAT）是否有解，若有解该如何给变量赋值： 3. 求如下有向图中的一个最长路径，要求给出路径和路径长度的值。

21 m 30 45 a 30 22 b 35 n

4.智能计算，并行计算概念

二、将下列函数按照渐进增长率由大到小进行排列，并给出你的判断依据：

三、有一堆货物需要被运走，现在有三种运货车：推车的容量最小，小货车的容

量是推车容量的2倍，大货车的容量是两辆小货车的容量加上一辆推车的容量。假设以上三种车的数量都非常多。现在要求你设计一种方案派出最少辆车将货物全搬走，其中除了推车以外其它三种车都必须装满才能发车。为这个问题设计一个算法，并证明该算法的正确性。 提示：贪心算法

四、求如下图中s和t间的最小割。

五、对某个输入为n的问题有如下四个分而治之算法：

算法1将该问题分成2个子问题，子问题大小为n/3，将子问题的解合并得到上一级问题的解需要O(n)时间；

算法2将该问题分成3个子问题，子问题大小为n/2，将子问题的解合并得到上一级问题的解需要O(n)时间； 算法3

第 1 页 共 2 页

六、为最大独立集问题建立一个整数规划模型。

七、一个图中的一组边集A满足如下性质则称A为一个独立匹配：A中任何两

条边都没有公共顶点，任意两个来自A中两条不同边的顶点之间都不存在一条边。证明求一个图中最大独立匹配（含有最多条边的独立匹配）是NP难的。（提示：可以考虑利用最大独立集问题来构造归约）

八、子集和问题定义如下：输入为一个有n个正整数的集合A和一个正整数k，

问是否存在A的一个子集合其中所有元素之和正好等于k。为子集和问题设计一个动态规划算法，并用你的算法对如下实例进行求解（要求画出表格）：A={2,3,7,8,9}，k=18.

九、叙述带权重的点覆盖问题（Weighted Vertex Cover Problem）的竞价法（Pricing

Method），并证明这个算法是个2倍近似算法。

竞价法（参考PPT讲义） 2倍近似率的证明（参考PPT讲义） 十、利用超递增序列设计多维数据的聚合与提取；

第 2 页 共 2 页

本文来源：https://www.bwwdw.com/article/h0yw.html