山东理工大学《算法设计与分析》试卷纸。
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检查当前扩展结点的每一个儿子所相应的颜色的可用性...