算法设计与分析考试题及答案.pdfVIP

一、填空题20分

1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此

外,算法还应具有以下五个重要特性:确定性有穷性可行性0个或多个输入一个或多个输

出

2.算法的复杂性有时间复杂性空间复杂性之分,衡量一个算法好坏的标准是时间复杂度高低

3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质

4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列

{BABCD}或{CABCD}或{CADCD｝

5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个最优解

6.动态规划算法的基本思想是将待求解问题分解成若干_子问题,先求解_子问题,然后从这些子

问题的解得到原问题的解;

7.以深度优先方式系统有哪些信誉好的足球投注网站问题解的算法称为回溯法

背包问题的回溯算法所需的计算时间为on2n,用动态规划算法所需的计算时间为omin{nc,2n}

9.动态规划算法的两个基本要素是最优子结构_和重叠子问题

10.二分有哪些信誉好的足球投注网站算法是利用动态规划法实现的算法;

二、综合题50分

1.写出设计动态规划算法的主要步骤;

①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造最

优解；

2.流水作业调度问题的johnson算法的思想;

①令N={i|ab},N={i|a=b}；②将N中作业按a的非减序排序得到N’,将N中作业按b的

1ii2ii1i12i

非增序排序得到N’；③N’中作业接N’中作业就构成了满足Johnson法则的最优调度;

212

3.若n=4,在机器M1和M2上加工作业i所需的时间分别为a和b,且

ii

a,a,a,a=4,5,12,10,b,b,b,b=8,2,15,9求4个作业的最优调度方案,并计算最优值;

12341234

步骤为：N1={1,3},N2={2,4}；

N’={1,3},N’={4,2}；

12

最优值为：38

4.使用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量

组成,要求用一棵完全二叉树表示其解空间从根出发,左1右0,并画出其解空间树,计算其最优值及

最优解;

解空间为{0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,

1,1,0,1,1,1};

解空间树为：

该问题的最优值为：16最优解为：1,1,0

5.设S=｛X,X,···,X｝是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二

12n

叉有哪些信誉好的足球投注网站树中有哪些信誉好的足球投注网站一个元素X,返回的结果有两种情形,1在二叉有哪些信誉好的足球投注网站树的内结点中找到X=X,其概率为