05计本算法设计与分析期考试卷(c卷)

《05计本算法设计与分析期考试卷(c卷)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一．填空题（每空2分，共30分）1．计算复杂性包括两个方面。2．在忽略常数因子的情况下，提供了算法运行时间的一个界。3．算法的平均情况下时间复杂性A(n)=，其中Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间,p(I)表示。4．从算法时间复杂性的角度看，时间复杂性阶为的算法是实际可接受的。5．用动态规划算法解题时，，算法的效率越高。6．分治算法的基本步骤包括。7．回溯算法的搜索顺序是。8．贪心法通常用于求解问题。9．PQ式的分支限界法中，活结点表的结构是。10．Prim算法、Dijkstra算法、快速排序算法和Huffman算

2、法中不是贪心算法。11．一个问题满足递归关系是指。12．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间。13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤，就可得到一个随机化查找算法。算法BISEARCH输入：正整数n，n个元素的升序数组A[1..n]和元素x。输出：如果存在j，1<=j<=n使得x=A[j]，则输出j，否则输出0。1.low=1;high=n;j=02.while(low<=high)and(j=0)3.mid=4.ifx=A[mid]thenj=mid5.elseifx

3、mid-1考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线6.elselow=mid+17.endif8.endif9.endwhile10.returnjendBISEARCH14．下面算法的基本运算是运算，该算法中第4步执行了次。算法COUNT输入：正整数n（n=）。输出：count的值。1.count=02.whilen>=13.forj=1ton4.count=count+15.endfor6.n=n/27.endwhil

4、eendCOUNT二．计算题和简答题（每小题7分，共21分）1．用表示下列各函数的阶，并按阶从低到高的顺序排列这些函数。n3/(n+5),2n+3n/2,5n2log3n+n3log2n,n!+nn,log(logn)/10002．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。算法EX2输入：正整数n，n=2k。输出：…ex2(1,n)endEX2过程ex2(low,high)iflow>=highthenpro1()elsem

5、=ex2(low,m)ex2(m+1,high)pro2(low,high)endifreturnendex23．设矩阵M1，M2，M3，M4，M5的阶如下：M1：102M2：25M3：52M4：24M5：410。下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果，考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线C[1,1]=0C[1,2]=100C[1,3]=60C[1

6、,4]=C[1,5]=C[2,2]=0C[2,3]=20C[2,4]=36C[2,5]=C[3,3]=0C[3,4]=40C[3,5]=180C[4,4]=0C[4,5]=80C[5,5]=0表1S[1,1]=0S[1,2]=2S[1,3]=2S[1,4]=S[1,5]=S[2,2]=0S[2,3]=3S[2,4]=4S[2,5]=S[3,3]=0S[3,4]=4S[3,5]=4S[4,4]=0S[4,5]=5S[5,5]=0表2其中，C[i,j]表示求MiMi+1…Mj所需的最少数量乘法次数，S[i,j]表示相应的最优解信息。填充表1和表2中

7、空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。三．算法填空题（共34分）1．（10分）下面是快速排序算法。算法QUICKSORT输入：正整数n，n个元素的数组A[1..n]。输出：按非降序排列的数组A中的元素。quicksort(A,1,n)endQUICKSORT过程quicksort(A,low,high)//将A[low..high]中的元素按非降序快速排序。iflow

8、sort过程SPLIT(A,low,high)//以A[low]为主元划分A[low..high],返回主元的新位置。i=low;x=A[low]fo