山东理工大学《算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与分析》试卷纸
（A ）卷 11-12第 一学期 班级： 姓名： 学号：
…………………………………装……………………………订…………………………线………….………………………………
适用专业
08算机科学1—6
考核性质
考试
开 卷
命题教师
石少俭、张立红
考试时间
100分钟
题号
一
二
三
四
五
六
七
八
九
十
十一
总分
得分
评阅人
复核人
一． 简答题（每题5分，共20分）
1． 程序的时间复杂性和空间复杂性
2． 回溯法与分支限界法的区别
3． 写出3个NP完全问题
4． 概率算法特征
二．解下列递推方程（10分）： T(n)=1 , n=1
T(n)=4T(n/2)+O(n) , n>1
三． 实例题（每题10分，共50分）
1. 货物装箱问题：设有一艘货船装物品。共有n=6件物品，它们的重量如下表示：
[w1,..., w6] = [95, 200, 60, 90, 50, 20]，船的限载重量是c=300。试用贪心算法装船，
要求物品装得最多。贪心准则：从剩下的货箱中选择重量最小的货箱。
2. 给出一个赋权无向图如下，求顶点S到T的最短路
6
6 5 8 6
3 7 7 5
S T
3 6 8
6
4 9
共 3 页 第 1 页
山东理工大学《算法设计与分析》试卷纸
（A ）卷 11-12 学年第 一 学期 班级： 姓名： 学号：
…………………………………装……………………………订…………………………线………….………………………………
3. 用分治算法计算1234*6789。
4.0-1背包问题:n=4, w=[2,4,6,7], p =[6,10,12,13], c = 11。
5.用快速排序算法对序列45 ，35， 65，97 ，78， 13 ，27 进行排序。（每一趟排序以第一个元素为数轴。要求每一趟排序有完整的过程。）
共 3 页 第 2 页
山东理工大学《算法设计与分析》试卷纸
（A ）卷 11-12 学年第 一 学期 班级： 姓名： 学号：
…………………………………装……………………………订…………………………线………….………………………………
四．综合题（每题10分，共20分））
1．在一个操场的四周摆放着7堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选3堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将7堆石子合并成一堆的最大总费用和最小总费用。7堆砂子的量分别是：45 13 12 16 9 5 22
提示：贪心算法，要求给出贪心策略。
2. 动态规划算法：已知A={x,y,x,z,y,x,y,z,z,y}，B={x,z,y,z,x,y,z,x,y,z,x,y}，求2个序列的最长公共子序列
共 3 页 第 3 页
浙公网安备 33021202002483