算法设计与分析试题B卷.doc

《算法设计与分析试题B卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学院数学学院班级107姓名学号…………………密……………封……………线……………密……………封……………线…………………嘉应学院数学学院2012-2013学年第二学期期末考试试卷《算法设计与分析》试题(B卷)（考试形式：开卷，考试时间：90分钟，考试范围：数学学院107班）题号一二总分复核人得分评卷人得分一、简答题（每题8分，共40分）1、按照渐近阶从低到高的顺序排列下列表达式。2,3n2＋10n,logn2,nn!,n!,10n2、用自然语言描述分治法的一般算法设计模式。3、什么是备忘方法，备忘录方法有何作用？。4、

2、如何使用贪心算法求活动安排问题的解？5、使用回溯法求装载问题的解，什么情况下剪去左子树？什么情况下剪去右子树？得分二、算法分析题（每题15分，共60分）1、若一图像各象素点灰度值为：10,9,12,11,15,13,33,35,37,42,45,57,5,7,6,4求使用动态规划法求其最优解时的矩阵b,l,s的值并给出最优解学院数学学院班级107姓名学号…………………密……………封……………线……………密……………封……………线…………………2、设计一个递归函数，用于计算Ackerman函数的值（不设计主函数）。3、使

3、用Kruskal算法构造最小生成树，给出Kruskal算法选边过程。4、使用分支限界法求单源最短路径问题，源点为A，终点为E，优先队列使用堆，要求画出解空间树和堆的变化图。