(完整版)算法设计与分析考试题及答案 .pdfVIP

(完整版)算法设计与分析考试题及答案--第1页

(完整版)算法设计与分析考试题及答案

一、填空题（20分）

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

一系列运算，此外,算法还应具有以下五个重要特性：

_________,________,________，__________，__________。

2。算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准

是______________________。

3。某一问题可用动态规划算法求解的显著特征是

____________________________________.

4.若序列X={B，C,A，D,B，C,D},Y={A，C，B,A，B，D，C,D}，请给出序列X和Y

的一个最长公共子序列_____________________________.

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含

___________。

6。动态规划算法的基本思想是将待求解问题分解成若干____________，先求解

___________，然后从这些____________的解得到原问题的解。

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

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需

的计算时间为____________.

9。动态规划算法的两个基本要素是___________和___________。

10。二分有哪些信誉好的足球投注网站算法是利用_______________实现的算法。

二、综合题（50分）

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

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

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

ii1234

（4，5，12,10），(b,b,b，b)=（8，2，15,9)求4个作业的最优调度方案，并计

1234

(完整版)算法设计与分析考试题及答案--第1页

(完整版)算法设计与分析考试题及答案--第2页

(完整版)算法设计与分析考试题及答案

算最优值。

4。使用回溯法解0/1背包问题：n=3，C=9，V={6，10，3｝，W={3,4，4}，其解空

间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，

左1右0），并画出其解空间树，计算其最优值及最优解。

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

12n

素，在表示S的二叉有哪些信誉好的足球投注网站树中有哪些信誉好的足球投注网站一个元素X，返回的结果有两种情形,（1）在二

叉有哪些信誉好的足球投注网站树的内结点中找到X=X，其概率为b。（2）在二叉有哪些信誉好的足球投注网站树的叶结点中确定X

ii

∈（X，X），其概率为a。在表示S的二叉有哪些信誉好的足球投注网站树T中，设存储元素X的结点深

ii+1ii

度为C；叶结点（X,X)的结点深度为d，则二叉有哪些信誉好的足球投注网站树T的平均路长p为多少？

iii+1i

假设二叉有哪些信誉好的足球投注网站树T［i]［j］={X，X，···,X｝最优值为m[i］［j］，W［i][j］=a

ii+1ji

+b+···+b+a，则m［i］[j]（1〈=i=j=n