G卷标准答案

西北民族大学计算机科学与信息工程学院期末考试

算法设计与分析 试卷（ G 卷）

参及评分标准

专业: 课程代码:

一、填空题（每空 1 分，共25 分）

1．输入，输出，确定性，有限性。2。某种程序设计语言的具体实现，有限性，无限循环中。 3.时间复杂性，空间复杂性，空间复杂性，算法的输入，算法本身的函数。

4. 算法本身的函数，组合数较大。5.最优子结构性质，重叠子问题性质。6. （1）问题的解空间（２）易于搜索的解空间结构（３）深度优先方式7.数值概率算法，蒙特卡罗算法，拉斯维加斯算法，舍伍德算法。8.备忘录方法。

3、算法的复杂性是算法运行所需要的计算机资源的量，它有 时间复杂性 和空间复杂性

之分。这个量应该集中反映算法的效率。它只

依赖算法要解的 问题的规模 、算法的输入 和算法本身的函数 。 4、回溯法在问题的解空间树中，按算法本身的函数 ， 它适用于 求解组合数较大的问题。

5、动态规划算法的基本要素是 最优子结构性质和 重叠子问题性质 。

6、回溯法解题包含以下3个步骤（1）针对所给问题，定义 问题的解空间 ； （2）确定 ；（3）以 易于搜索的解空间结构搜索解空间，并用深度优先方式 避

免无效搜索。

8、动态规划法的变形是 备忘录方法 。

二、证明简答（共2题30分）

1. （1）在下面的数组中查找一个键的时候，二分搜索最多需要进行多少次键值比较？（4分） 3 14 27 31 39 42 55 70 74 81 85 93 98 （2）请列出所有符合条件的键，对于他们，二份搜索在查找该数组的时候，需要进行最多几次的键值比较。（4分）

（3）在对该数组拆半查找成功的前提下，求键值比较的平均次数（假设查找每一个键的概率都是相同的）。（6分）

（4）在对该数组拆半查找失败的前提下，求键值比较的平均次数（假设查找键位于该数组构成的14个区间内的概率都是相同的）。（6分） （1）（4分）4或5次。（2）（4分）比较１次 55，比较2次 27、85，比较3次 14、42、81、93，比较4次 3、39、74、98，比较5次 70。（3）（6分）3次。（4）（6分）4次 2. 简述最小生成树问题的贪心算法Prim，（6分） 设G=（V，E）是连通带权图，首先置S={1}，然后，只要S是V的真子集，就进行贪心选择： 选取满足条件i∈S,j∈V-S,且C[i][j]最小的边，将顶点j添加到S中，这个过程一直进行到S= V时为止。这个过程选取到的所有边恰好构成G的一棵最小生成树。 能够按步骤画出迭边过程4分。 三、分析计算（ 共2题45分）

算法设计与分析试卷参及评分标准第3页（共3页）

1.贪心算法解活动安排问题：写出完整程序12分，活动方案3分。 public static int greedySelector(int s[],int f[],boolean a[]) {

int n=s.length-1;

a[1]=true;

int j=1;

int count=1;

for(int i=2;i<=n;i++){

if(s[i]>=f[j]){

a[i]=ture; j=i; count++; }

else a[i]=false; }

return count;

}

11个活动的最优安排方案是：5，4，11，8 2.算法设计：采用下面策略解决：（1）首先将第一艘轮船尽可能装满；（2）将剩余的集装箱装上第二艘轮船；由此可知，装载问题等价于0-1背包问题。用子集树表示其解空间，采用广度优先搜索方法搜索该解空间树找出最优解。用队列式分支限界法，其解空间树是一子集树

其状态空间树：以n=3为例

1 1 1 0 1 0 0 1 0 1 0 0 0 3. 动态规划算法求解矩阵连乘问题的算法描述如下：补充完整(6分) MATRIXCHAIN(p[],m[],s[]) {

n=length[p]-1；

for(i=1；i<=n；i++) m[i][j]=0； for(r=2；r<=n；r++) for(i=1；i<=n-r+1；i++){

j=i+r-1；

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]； s[i][j]= i;

for(k=i+1；k算法设计与分析试卷参及评分标准第3页（共3页）

t= m[i][k]+ m[k+1][j]+ p[i-1]*p[i]*p[j]; if(t=m[i][j]){

m[i][j]=t; s[i][j]=k;}

}

} }

试根据该算法完成下述m[3][5],m[2][6],s[3][5],s[2][6]。并对6个矩阵完全加括号。 6个矩阵及维数 A1 30×35 i j 1 0 2 3 4 5 6

1

2 15790 0 3 7875 2625 0 4 9375 4375 750 0 5 11875 7125 2500 1000 0 6

15125 10500 5375 3500 5000 0 A2 35×15 A3 15×5 A4 5×10 A5 10×20 A6 20×25

i j 1 2 3 4 5 6

解：m[3][5]= 2500,m[2][6]= 10500,s[3][5]= 3,s[2][6]= 3 （8分） 6个矩阵完全加括号：（（A1(A2A3)）((A4A5)A6)）（6分）

算法设计与分析试卷参及评分标准第3页（共3页）