算法分析与设计模拟试卷A

算法设计与分析 期末考试模拟试卷 A卷

考试说明： 承诺：

本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不。若有违反，愿接受相应的处分。

承诺人： 学号： 班号：

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

注：本试卷共 三 大题，共 6 页，满分100分，考试时答案请写在试卷空白处。

卷 面 成 绩 汇 总 表（阅卷教师填写） 题号 满分 得分 得 分 一 二 三 总成绩 一、算法时间复杂性问题（共30分）

Part 1. The Time Complexity Of the Algorithm Test

1、试证明下面的定理：[12分]

(1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n)) (2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks]

(1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n)) (2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n))

第 1 页 共 7 页

《 算法设计与分析 》 期末考试试卷

2、已知有如下的断言：

f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n))

请你举出一个反例。[8分] 2. Known as the following assertion

If f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。

Please cite a counter-example [8 marks]

3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n ，在A型计算机 上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。试求出若在先进的B型机上运行同一算法则在t秒内能求解 输入规模为多大的问题？[10分]

3. Assume that in the case of the input size is n, the computing time of the algorithm required is T（n）=3*2n. It would take t seconds to implement the algorithm on Computer A. Computer B is more advanced. The operation ability of Computer B is 256 times of Computer A. If the same algorithm running on Computer B, please find out the input size so that the algorithm would solve in t seconds.[10 marks]

第 2 页 共 7 页

《 算法设计与分析 》 期末考试试卷

得 分 二、简答题（本题共30分）

Part 2. Brief Answering Questions. [30 marks]

1、对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得

出评价某

类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立 一个问题的复杂性的下界要比确定它的上界困难得多！”。[7分]

1. Research on the computing complexity can make people understand the inherent difficulty of solving the problem, and get the guidelines to evaluate the algorithms with which could guide the design of more efficient algorithms. Use brief description to illustrate “It is much more difficult to establish a lower bound for the complexity of the problem than to determine its upper bound”. [7 points]

2、满足何种性质的问题被称为NP完全问题？请简述研究NP完全问题的意义；

第 3 页 共 7 页

《 算法设计与分析 》 期末考试试卷

[8分]

If a problem is called NP-complete problem, what properties should it to meet? Please describe the significance of studying NP-complete problems [ 8 marks]

3、“当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性 质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素。

(1) 试简要阐述“论证某一问题具有最优子结构性质”时的一般方法；[8分] (2) 试证明0/1背包问题满足最优子结构性质；[7分]

即证明：如果（x1,x2,...,xn）是所给0-1背包问题的最优解，则 (x1,x2,...,xn-1)是下列子问题的最优解。

3. If the optimum solution of the problem contains its sub problem’s optimum solution, then we call that the problem contains a property of optimal substructure. This property can be an essential element of using Dynamic programming algorithm to solve the problem.

(1) Briefly describe the general approach when we demonstrate a problem contains the optimal substructure. [8 marks]

(2) Prove that the 0/1 knapsack problem meets the property of optimal substructure . [7marks]

As to prove that if （x1,x2,...,xn）is the optimum solution of the given 0/1 knapsack problem, then (x1,x2,...,xn-1) is the the optimum solution of following question.

第 4 页 共 7 页

《 算法设计与分析 》 期末考试试卷

得 分 三、算法设计与分析问题（2题共40分）

Part 3. Algorithm Design and Analysis[a total of 40 marks]

1、TSP问题的动态规划算法（20分）

所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一 次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问 题等）。请用数学语言对该TSP问题加以抽象，在此基础上给出动态规划求解该 问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法步骤。

1. Dynamic programming algorithm for the TSP problem[20 marks]

TSP problem means that the traveling salesman will travel to n cities to sell goods, each city must be arrived and only once, and also be required to take the shortest route.

Please use abstract mathematical language to describe the TSP problem, and on the basis of this, use dynamic programming method to give the recursive formula of the problem. You should describe the meaning of the symbols in the formula in detail and give a brief description for the algorithm steps.

第 5 页 共 7 页

《 算法设计与分析 》 期末考试试卷

2、广义背包问题（20分）

广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定 的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物 品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次 或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽 象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号 意义加以详细说明，并简述算法步骤。

2. Generalized knapsack problem [20 marks]

The Description of generalized knapsack problem as follow: There are n kind of items and a package. The loading weight of the package is M. Each item has a certain weight and value. Now design the algorithm to meet the following rules:

In the premise of not over the loading weight, please choose the items cleverly so that the total value of the loaded items can be maximum. Each kind of items can be loaded repeatedly or not be loaded (but each item can not be loaded a part of it).

第 6 页 共 7 页

《 算法设计与分析 》 期末考试试卷

Please use abstract mathematical language to describe this problem, and on the basis of this, use dynamic programming method to give the recursive formula of the problem. You should describe the meaning of the symbols in the formula in detail and give a brief description for the algorithm steps.

第 7 页 共 7 页