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

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

1、福建师范大学数学与计算机科学学院2006—2007学年第二学期考试A卷考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿装订线专业：计算机科学与技术年级：2005级课程名称:算法设计与分析任课教师：潘日晶试卷类别：开卷（）闭卷（√）考试用时：120分钟考试时间:2007年1月13日下午18点30分题号一二三四五总得分评卷人得分题号六七八九十得分福建师范大学试卷纸共9页，第12页一．填空题（每空2分，共30分）1．

2、算法的时间复杂性指算法中的执行次数。2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间,p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)=。4．分治算法的时间复杂性常常满足如下形式的递归方程：其中，g(n)表示。5.分治算法的基本步骤包括。6．回溯算法的基本思想是。7．动态规划和分治法在分解子问题方面的不同点是。8．贪心算法中每次做出的贪心选择都是最优选择。9．PQ式的分支限界法中，对于活结点表中的结点

3、，其下界函数值越小，优先级越。10．选择排序、插入排序和归并排序算法中，算法是分治算法。11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。算法QUICKSORT输入：n个元素的数组A[1..n]。输出：按非降序排列的数组A中的元素。福建师范大学试卷纸共9页，第12页考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿

4、＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线1.quicksort(1,n)endQUICKSORT过程quicksort(A,low,high)//对A[low..high]中的元素按非降序排序。2.iflow

5、法的基本运算是运算，该算法的时间复杂性阶为()。算法SPLIT输入：正整数n，数组A[1..n]。输出：…。i=1x=A[1]forj=2tonifA[j]<=xtheni=i+1ifijthenA[i]A[j]endifendfor福建师范大学试卷纸共9页，第12页A[i]A[1]w=ireturnw,AendSPLIT二．计算题和简答题（每小题7分，共21分）1．用O、、表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：(1)　f(n)=100g(n)=(2)f(n)=6n+ng(n)=3n(

6、3)f(n)=n/logn-1g(n)=(4)f(n)=g(n)=(5)f(n)=g(n)=2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。算法EX1输入：正整数n，n=2k。输出：…ex1(n)endEX1过程ex1(n)ifn=1thenpro1(n)else福建师范大学试卷纸共9页，第12页考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业

7、＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线pro2(n)ex1(n/2)endifreturnendex13．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i,j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。三．算法填空题（共34分）1．（10分）设n个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i的下标i。下面是求解该问题的分治算法。算法SEARCH输入：正整数n，存储n个按升序排列的不同整数的数组A[1..n]。输出

8、：A[1..n]中使得A[i]=i的一个下标i，若不存在，则输出nosolution。i=find((1))ifi>0thenoutputielseoutput“nosolution”endSEARCH过程find(low,high)//求A[low..high]中使得A[i]=i的一个下标并返回，若不存在，福建师范大学试卷纸共9页，第12页//则返回0。i