05计本算法设计与分析期考试卷（A卷）

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 A 卷

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 2007 年 1 月 13 日 下 午 18 点 30 分

题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 福建师范大学试卷纸 共 9 页，第 1 页

一．填空题（每空2分，共30分） 1．算法的时间复杂性指算法中 的执行次数。 2．在忽略常数因子的情况下，O、?和?三个符号中， 提供了算法运行时间的一个上界。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： ?f(n)?d , n?n0 ? f(n)?af(n/c)?g(n) , n?n0? 其中，g(n)表示 。 5. 分治算法的基本步骤包括 。 6．回溯算法的基本思想是 。 7．动态规划和分治法在分解子问题方面的不同点是 。 8．贪心算法中每次做出的贪心选择都是 最优选择。 9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。 10．选择排序、插入排序和归并排序算法中， 算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。 12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤 ，就可得到一个随机化快速排序算法，该随机化步骤的功能是 。 算法 QUICKSORT 输入：n个元素的数组A[1..n]。 输出：按非降序排列的数组A中的元素。 福建师范大学试卷纸 共 9 页，第 2 页

＿＿＿＿＿号学 ＿ ＿栏＿ ＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿信＿ ＿ ＿ ＿ 业 专生 ＿ ＿ ＿ ＿ ＿ ＿ 考系＿＿＿＿＿＿院学＿＿＿＿＿＿1. quicksort(1, n) end QUICKSORT 过程 quicksort(A, low, high) // 对A[low..high]中的元素按非降序排序。 2. if low

A[i]?A[1] w =i return w, A end SPLIT 二．计算题和简答题（每小题7分，共21分） 1．用O、?、?表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数： (1) f (n)=100 g(n)=100n (2) f(n)=6n+n?logn? g(n)=3n (3) f(n)= n/logn-1 g(n)=2n (4) f(n)=2n?n2 g(n)=3n (5) f(n)= log3n g(n)= log2n 2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和log2n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用?表示）。 算法 EX1 输入：正整数n，n=2k。 输出：… ex1(n) end EX1 过程 ex1(n) if n=1 then pro1(n) else 福建师范大学试卷纸 共 9 页，第 4 页

＿＿＿＿＿号学 ＿栏＿ ＿ ＿ ＿ ＿ 名 姓息 级 年 ＿信＿ ＿ ＿ ＿ ＿ 业 生专 ＿ ＿ ＿ ＿ ＿ ＿考系＿＿＿＿＿＿院学＿＿＿＿＿＿pro2(n) ex1(n/2) end if return end ex1 3．用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]。 输出：A[1..n]中使得A[i]=i的一个下标i，若不存在，则输出 no 装solution。 i=find ( (1) ) if i>0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i的一个下标并返回，若不存在， 福建师范大学试卷纸 共 9 页，第 5 页

//则返回0。 if (2) then return 0 else mid=?(low?high)/2? if (3) then return mid else if A[mid]

＿＿＿＿＿号学 栏＿＿ ＿ ＿ ＿ ＿ 名 息姓 级 年线 ＿ 信 ＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ 考＿ 系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿for i=1 to n C[i, i]= （1） for d=1 to n-1 for i=1 to n-d j= (2) C[i, j]= ∞ for k=i+1 to j x= (3) if x

x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 while (1) and not flag while k[i]<8 and not flag k[i]= (2) x1= x+dx[k[i]]; y1= y+dy[k[i]] if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tag[x, y]= (3) if i=m then flag=true else i= (4) (5) end if end if end while i=i-1 (6) (7) end while if flag then outputroute(k) //输出路径 else output “no solution” end HORSETRAVEL

福建师范大学试卷纸 共 9 页，第 8 页

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿

四．算法设计题（15分） 1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=d1?d2???dn?s，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学试卷纸 共 9 页，第 9 页

本文来源：https://www.bwwdw.com/article/zn4.html