搜索
广东工业大学试卷用纸，共3页，第1页学院：专业：学号：姓名：装订线广东工业大学考试试卷(A)课程名称:算法设计与分析试卷满分100分考试时间:2013年6月11日(第17周星期二)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、选择题（每小题2分，共10分）1.算法时间复杂度函数增长次数小于等于g(n)以及其常数倍（n趋向于无穷大）的函数集合记作A.O(g(n))B.Ω(g(n))C.Θ(g(n))D.无此符号2.递推关系式M(n)=M(n-1)+2n，M(0)=0的算法时间复杂度为A.θ(n!)B.θ(n2)C.θ(n)D.θ(1)3.下列几种排序算法，运行占用内存最大的是A.插入排序B.选择排序C.快速排序D.归并排序4.使用Kruskal算法计算下图所得到的最小生成树的权重为A.10B.12C.15D.185.在堆中，把位于第i层的一个键移到第i+1层所需要的键值比较次数为A.1B.2C.2i-1D.2i广东工业大学试卷用纸，共3页，第2页二、简答题（每小题7分，共42分）1使用Horner法则求解多项式532()23518pxxxx在3x处的值（画出表格）。2在计数排序中使用count数组记录数组中小于该元素的个数。若使用计数排序对数组[4，1，6，9]进行排序，请给出count数组的动态变化过程。4169初始count数组0000第0遍后count数组第1遍后count数组第2遍后count数组3大整数乘法请写出使用大整数乘法计算67*49的的计算过程及其结果4.对于折半查找请回答以下问题（1）请写出折半查找的基本思想。（2）使用折半查找的前提条件是什么？（3）请估算：对于一个1000个元素的数组成功查找的话，使用折半查找比顺序查找要快多少倍？5时间复杂度定义请写出分治法、减治法思想的区别与联系，并分别给出使用这两种思想设计的算法名称。6用减一思想生成子集的方法，给出生成集合{a,b,c}的所有子集的过程。三、分析题（每小题12分，共48分）1时间复杂度分析算法Binomial(n,k)//用动态规划算法计算C(n,k)//输入：—对非负整数n=k=0//输出：C(n,k)的值fori←0tondoforj←0tomin(i,k)doifj=0orj=iC[i,j]←1elseC[i,j]←C[i-1,j-1]+C[i-1,j]returnC[n,k]（1）指出该问题的规模（2）指出该算法的基本操作（3）说明基本操作的次数取决于哪些因素广东工业大学试卷用纸，共3页，第3页（4）写出最差效率的求和表达式及估算效率类型（5）指出该算法的效率类型2请写出快速排序QuickSort（A[l,r]）,intPartition（A[l,r]）这两个函数的伪代码，并指出算法效率最坏的情形，及最坏情形下的时间复杂度,请演示如何对组[10,20,2,15,4,6,13,8]进行快速排序（4分）。102021546138第一趟排序第二趟排序第三趟排序3请写出Floyd算法的伪代码，并根据代码计算布尔矩阵的形式给出邻接矩阵041050260所代表的图的运行结果。4请写出Dijkstra算法的伪代码，并根据代码求从定点a到其它所有顶点的最短距离。abcef1429362h15