算法设计F卷.docx
《算法设计F卷.docx》由会员分享，可在线阅读，更多相关《算法设计F卷.docx（7页珍藏版）》请在冰点文库上搜索。
算法设计F卷
西北民族大学计算机科学与信息工程学院期末考试
算法设计与分析试卷（F卷）
专业:
课程代码:
15060221
学号:
姓名:
得分
评卷人
总分
题号
一
二
三
核分人
题分
复查人
得分
一一、填空（每空一分，共25分）
1、通俗地讲，算法是指解决问题的方法或过程。
严格地讲，算法是满足下述性质的指令序列：
、、、。
[能力层次：
记忆]；[难易度：
A]
2、程序（program）与算法不同。
程序是算法用
实现。
程序可以不满足算法的性质。
例如操作系统，它是在执行的程序。
[能力层次：
理解]；[难易度：
B]
3、回溯法在问题的解空间树中，按，它适用于
求解的问题。
[能力层次：
记忆]；[难易度：
A]
4、动态规划法的变形是。
[能力层次：
记忆]；[难易度：
B]
5、二分搜索方法充分利用了关系，采用分治策略，
可在最坏情况下在时间内完成搜索任务。
[能力层次：
理解]；[难易度：
B]
6、一般情况下，时间复杂度分为、
和。
但实践表明，可操作性最好且最有实际价值的
是下的时间复杂度。
[能力层次：
简单运用]；[难易度：
C]
7、回溯法搜索解空间树时，通常采用两种策略避免无效搜索提高回溯法
的搜索效率。
其一是用在扩展结点减去不满足约束的子树；
其二是用减去得不到最优解的子树。
这两类函数统称
为。
[能力层次：
理解]；[难易度：
C]
8、分支限界法常以或的方式搜索问题的解空间树。
[能力层次：
记忆]；[难易度：
B]
9、概率算法可分为：
算法、算法、
算法、算法。
[能力层次：
记忆]；[难易度：
D]
得分
评卷人
二、证明简答（共40分）
1.
（1）在下面的数组中查找一个键的时候，二分搜索最多需要进行多少次键值比较？
（4分）
[能力层次：
理解]；[难易度：
B]
3
14
27
31
39
42
55
70
74
81
85
93
98
（2）请列出所有符合条件的键，对于他们，二份搜索在查找该数组的时候，需要进行最多几次的键值比较。
（4分）
[能力层次：
理解]；[难易度：
C]
（3）在对该数组拆半查找成功的前提下，求键值比较的平均次数（假设查找每一个键的概率都是相同的）。
（6分）
[能力层次：
简单运用]；[难易度：
D]
（4）在对该数组拆半查找失败的前提下，求键值比较的平均次数（假设查找键位于该数组构成的14个区间内的概率都是相同的）。
（6分）
[能力层次：
创建和综合运用]；[难易度：
E]
2、用Kruskal算法来构造最小生成树的基本思想。
根据下面的连通带权图按Kruskal算法顺序得到的最小生成树（10分）
[能力层次：
理解]；[难易度：
B]
。
3、快速排序基本思想（既3个步骤）。
在快速排序算法中的partition算法的主要功能是什么？
（10分）
[能力层次：
理解]；[难易度：
C]
得分
评卷人
三、分析计算（共2题35分）
1动态规划算法求解矩阵连乘问题的算法描述如下：
补充完整。
（20分）
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];
}
}
}
试根据该算法完成下述6个矩阵的m[2][5],m[3][6,s[2][5],s[3][6]并对6个矩阵完全加括号。
6个矩阵及维数
A1
A2
A3
A4
A5
A6
30×35
35×15
15×5
5×10
10×20
20×25
0
15790
7875
9375
11875
15125
0
2625
4375
10500
0
750
2500
0
1000
3500
0
5000
0
m[i][j]
j123456
i
1
2
3
4
5
6
i123456
m[i][j]
mm[i][j]
0
1
1
3
3
3
0
2
3
3
0
3
3
0
4
5
0
5
0
j123456
i
1
2
3
4
5
6
s[i][j]
2、设计一个用分支限界法解旅行售货员问题的算法。
要求写出算法设计并描述。
（15分）
根据4顶点带权图画出解空间树。
升级会员 