山东理工大学《算法设计与分析》试卷纸。
b ）卷 10-11学年第二学期班级姓名学号：
装订线。山东理工大学《算法设计与分析》评分标准。
b ）卷 10-11学年第二学期班级姓名学号：
装订线。简答题（每题5分，共20分）
程序的时间复杂性和空间复杂性。
算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的量称为时间复杂性。需要空间资源的量称为空间复杂性。
回溯法与分支限界法的区别。
两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的。
解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
写出3个np完全问题。
团问题、子集和问题、旅行售货员问题。(任意3个即可)
概率算法的分类。
数值概率算法、舍五德算法、拉斯维加斯算法、孟特卡罗算法。
二．解下列递推方程（10分）： t(n)=1n=1
t(n)=8t(n/2)+o(n2) ,n>1
t(n)= 8t(n/2)+o(n2)
8(8t(n/22)+o(n/2)2)+ o(n2)
82t(n/22)+ o(n2)
8k3t(n/2k)+ o(n2) (n=2k6分）
8logn=o(n34分）
实例题（每题10分，共40分）
1.45 13 12 16 9 5 22 最大总费用：每次合并最多的2组45+22+（67+16）+（83+13）+（96+12）+
108+9）+117+5=5935分）
最小总费用：每次合并最少的4组 5+9+13+12+（39+16+22+45）=1615分）
2.给出一个赋权无向图如下，求最小生成树。
每错一边扣2分。
共 3 页第 1 页。
3.123*789的计算过程如下：
令 x=123 y=789 则把x,y分为两段得。
x=1*102+23 y=7*102+89 记a=1 b=23 c=7 d=89
则由大整数乘法得公式得。
x*y=ac104+( a-b)(d-c) +ac+bd) 102+bd
4. n=4, w=[15,10,8，13], p =[20,15,13,18], c = 30。
m(i,j)为背包容量为j，可选择物品为i,i+1,…,n时0-1背包问题的最优值 （-2分）
m(1,30)=max=33
m(2,30)= max= =334分）
m(2,15)= max==18
m(3,30)= max==31
m(3,20)= max==18
m(3,15)= max==18
m(3,5)= m(4,5)=04分）
最优值为33，最优解为（1,0,1,0）
四．编程题（每题15分，共30分）
1：code:
#include<>#include<>#define n 600 //n 不能太大了int max(int a, int b)
int main()}printf("%d",f[w][v]);
共 3 页第 2 页。
for(j = 1; j <=c[i]; j *=2)}c[i] -j;}2. 对关键字序列 (265，301，751，129，937，863，742，694，076，438)，试用分治算法实现快速排序。略。
共 3 页第 3 页。
算法设计与分析试题2019秋
中国科学院研究生院课程编号 711008z 1 试题专用纸课程名称 计算机算法设计与分析。任课教师 陈玉福。姓名学号成绩。一 回答下列问题 每小题5分 1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度 这两种评估算法复杂性的方法各自有什么实际意义？2.阐述动态规划算法与贪心算法的区别，它们都有那...
算法设计与分析试题2019补考
中国科学院研究生院课程编号 711008z 1 试题专用纸课程名称 计算机算法设计与分析。试卷 b任课教师 陈玉福。姓名学号成绩。一 25分 下面是归并排序算法 递归程序 mergesort low,high a low high 是一个全程数组，含high low 1 个待排序的元素。intege...
算法分析与设计期末
11.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需o 1 的时间，l为最短布线路径的长度，则算法共耗时 o mn 构造相应的最短距离需要 o l 时间。12.用回溯法解图的m着色问题时，使用下面的函数ok检查当前扩展结点的每一个儿子所相应的颜色的可用性...