logo资料库

《算法分析与设计》期末考试试卷.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.56M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    栏 息 信 生 考 ＿ ＿ ＿ 号 学 ＿ ＿ ＿ ＿ ＿ ＿ 名 姓 级 年 ＿ ＿ ＿ ＿ ＿ ＿ 业 专 ＿ ＿ ＿ ＿ ＿ ＿ 系 ＿ ＿ ＿ ＿ ＿ ＿ 院 学 ＿ ＿ ＿ ＿ ＿ ＿ 线 订 装 福建师范大学数学与计算机科学学院 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．分治算法的时间复杂性常常满足如下形式的递归方程： 。 )n(f   f(n)    d af(n/c) g(n)  n , n ,   n n 0 0 其中，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]中的元素按非降序排序。 if low
    A[i]  A[1] w =i return w, A end SPLIT 二．计算题和简答题（每小题 7 分，共 21 分） 1．用 O、 、 表示函数 f 与 g 之间阶的关系，并分别指出下列函数中阶最低和最高 的函数： (1) (2) f (n)=100 f(n)=6n+n  log n (3) f(n)= n/logn-1 (4) (5) f(n)= 2 n  2 n f(n)= log n3 g(n)= 100 n g(n)=3n g(n)= n2 g(n)= n3 g(n)= log n2 2．下面是一个递归算法，其中，过程 pro1 和 pro2 的运算时间分别是 1 和 log 2 。给 n 出该算法的时间复杂性 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 else (2) then return 0 mid=  low(  high 2/) (3) then return mid if 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 (3) x= if x
    x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 (1) while and not flag while k[i]<8 and not flag (2) k[i]= 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]= if i=m then flag=true else (3) 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 页
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料