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

哈尔滨工程大学试卷 A 单源最短路径问题BN皇后问题C 最小花费生成树问题D背包问题考试科目： 《算法分析与设计》 2901.11.22（时间120分钟满分100分）一、选择题（30分,每题2分）。1.下列不是动态规划算法基本步骤的是（）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最解

贪心算法与动态规划算法的主要区别是（）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解实现最大子段和利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法12.舍伍德算法是（）的一种。回溯法解旅行售货员问题时的解空间树是（）。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法A、子集树B、排列树C、深度优先生成树D、广度优先生成树实现循环赛日程表利用的算法是（）。

13.下列算法中通常以自底向上的方式求解最优解的是（）。A、备忘录法B、动态规划法C、贪心法D、回溯法A、分治策略B、动态规划法C、贪心法D、回溯法 14.背包问题的贪心算法所需的计算时间为（）4.哈弗曼编码的贪心算法所需的计算时间为（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）5.回溯法的效率不依赖于下列哪些因素（）

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）下面不是分支界限法搜索方式的是（）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先A.满足显约束的值的个数 B. 计算约束函数的时间 二、填空题（20分,每空1分）。C. 计算限界函数的时间 D. 确定解空间的时间 1.算法由若干条指令组成的又穷序列，且满足输入、 、下面关于NP（）和 四个特性。ANP问题都是不可能解决的问题 2.单源最短路径问题可以由 和 两种算法来解决。P类问题包含在NPNPP类问题的子集

0-1PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级NP类问题包含在P类问题中 越 。7.下列哪一种算法不是随机化算法（）A. 蒙特卡罗算法B. 拉斯维加斯算法C.动态规划算法D.舍伍德算法

3个基本计算模型是 、 、 。分支限界法解旅行售货员问题时，活结点表的组织形式是（）。 6.回溯法是一种既带有 又带有 的搜索算法；分支A、最小堆B、最大堆C、栈D、数组--------------______------线号学------________-------------名姓_封---_-____--------_-级班----密-----------------------

限界法是一种既带有 又带有 的搜索算法。1设计动态规划算法的主要步骤是怎么的？请简述。用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为 2.何谓最优子结构性质nm的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则 3.何谓P、NP、NPC问题算法共耗时 ，构造相应的最短距离需要 时间。 4.简单描述回溯法基本思想。for(inti=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){

5.O、、fg阶最低和最高的函数：(1) f(n)=100 g(n)=100nlogn//该方格未标记 (2) grid[nbr.row][nbr.col]

g(n)=3nn2n=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布线Q.Add(nbr);}}8.f(n)=6×2n+n2，f(n)的渐进性态f(n)=O( )9.分治算法的时间复杂性常常满足如下形式的递归方程：

(3) f(n)=n/logn-1 g(n)=四、算法设计与分析（26分,111215）。1.分别动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di(nd , nn 公里，0=d1d0

dn

s，车加满油后可行驶m公里，出发之前汽车f(n)af(n/c)g(n) ,nn0

油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心-------------------线-------------------封-----------------密-----------------------其中，g(n)表示 。 法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最在忽略常数因子的情况下、