《算法分析与设计试卷2019-2020》

算法设计卷

1 哈尔滨工程大学试卷 考试科目： 《 算法分析与设计》 2901.11.2

2 （时间120分钟 满分100分） 一、选择题（30分,每题2分）。 1.下列不是动态规划算法基本步骤的是（ ）。 A 、找出最优解的性质 B 、构造最优解 C 、算出最优解 D 、定义最优解 2.回溯法解旅行售货员问题时的解空间树是（ ）。 A 、子集树 B 、排列树 C 、深度优先生成树 D 、广度优先生成树 3.实现循环赛日程表利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 4.哈弗曼编码的贪心算法所需的计算时间为（ ）。 A 、O （n2n ） B 、O （nlogn ） C 、O （2n ） D 、O （n ） 5.回溯法的效率不依赖于下列哪些因素（ ） A. 满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间 6.下面关于 NP 问题说法正确的是（ ） A NP 问题都是不可能解决的问题 B P 类问题包含在 NP 类问题中 C NP 完全问题是 P 类问题的子集 D NP 类问题包含在 P 类问题中 7.下列哪一种算法不是随机化算法（ ） A. 蒙特卡罗算法 B. 拉斯维加斯算法 C.动态规划算法 D. 舍伍德算法 8.分支限界法解旅行售货员问题时，活结点表的组织形式是（ ）。 A 、最小堆 B 、最大堆 C 、栈 D 、数组 9.下面问题（ ）不能使用贪心法解决。 A 单源最短路径问题 B N 皇后问题 C 最小花费生成树问题 D 背包问题 10.贪心算法与动态规划算法的主要区别是（ ）。 A 、最优子结构 B 、贪心选择性质 C 、构造最优解 D 、定义最 优解 11.实现最大子段和利用的算法是（ ）。 A 、分治策略 B 、动态规划法 C 、贪心法 D 、回溯法 12.舍伍德算法是（ ）的一种。 A 、分支界限算法 B 、概率算法 C 、贪心算法 D 、回溯算法 13.下列算法中通常以自底向上的方式求解最优解的是（ ）。 A 、备忘录法 B 、动态规划法 C 、贪心法 D 、回溯法 14.背包问题的贪心算法所需的计算时间为（ ） A 、O （n2n ） B 、O （nlogn ） C 、O （2n ） D 、O （n ） 15.下面不是分支界限法搜索方式的是（ ）。 A 、广度优先 B 、最小耗费优先 C 、最大效益优先 D 、深度优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、 、 和 四个特性。 2.单源最短路径问题可以由 和 两种算法来解决。 3.解决0-1背包问题 4.PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。 5.在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。

3 个基本计算模型是 、 、 。 6.回溯法是一种既带有 又带有 的搜索算法；分支 限界法是一种既带有 又带有 的搜索算法。

算法设计卷

2

7.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为 n m 的方格阵列，扩展每个结点需 O(1) 的时间， L 为最短布线路径的长度，则 算法共耗时 ，构造相应的最短距离需要 时间。 for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 该方格未标记 grid[nbr.row][nbr.col]

= grid[here.row][here.col] + 1; if ((nbr.row == finish.row) &&

(nbr.col == finish.col)) break; // 完成布线 Q.Add(nbr);} }

8.f(n)= 6×2n

+n 2

，f(n)的渐进性态f(n)= O( ) 9.分治算法的时间复杂性常常满足如下形式的递归方程：

?

??>+===00n n , g(n)af(n/c)f(n)n n ,

d )n (f

其中，g(n)表示 。

10.在忽略常数因子的情况下，O 、Ω和Θ三个符号中， 提供了算法运行

时间的一个上界。

11.许多可以用贪心算法求解的问题一般具有2个重要的性质： 性质和 性质。

12.动态规划和分治法在分解子问题方面的不同点是 。 三、问答题（30分，每题6分）。

1. 设计动态规划算法的主要步骤是怎么的？请简述。

2.何谓最优子结构性质？

3.何谓P 、NP 、NPC 问题

4.简单描述回溯法基本思想。

5.用O 、Ω、Θ表示函数f 与g 之间阶的关系，并分别指出下列函数中 阶最低和最高的函数：

(1) f (n)=100 g(n)=

100

n

(2) f(n)=6n+n ??n log g(n)=3n (3) f(n)= n/logn-1 g(n)=n 2

四、算法设计与分析（26分,1题11分，2题15分）。 1.分别动态规划法、回溯法设计0-1背包问题。

要求：说明所使用的算法策略；写出算法实现的主要步骤； 分析算法的时间。

一个旅行者要驾车从A 地到B 地，A 、B 两地间距离为s 。

A 、

B 两地之间有n 个加油站，已知第i 个加油站离起点A 的距离为i d 公里，0=s d d d n 21≤<<< ，车加满油后可行驶m 公里，出发之前汽车 油箱为空。应如何加油使得从A 地到B 地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。