《算法设计与分析试题》由会员分享，可在线阅读，更多相关《算法设计与分析试题（4页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学网络教育2010学年上学期期末考试模拟试题一一、填空题(每小题4分，共计40分)1. 通常只考虑三种情况下的时间复杂度，即 情况、情况和情况下的时间复杂度，分别记为T max(N)、T min (N)和T avg (N)，实践表明可操作性最好且最有实际价值的是 情况下的时间复杂度。2. 3n210n的渐近表达式是 ，log(n)的渐近表达式是。3. 根据符号 O的定义易知 0(1)=0(2)，用0(1)和0(2)表示同一个方法时，差别仅在于其中的。4. 递归算法是指的算法，递归函数是指 的函数。5. 贪心算法总是做岀在当前看来 的选择，也就是说，贪心算法并不从整体最优考虑它所做
2、岀的选择只是在某种意义上的 。6. 如果某问题具有 和两个重要性质，该问题可以用贪心算法求解。7. 单源最短路径问题适合用算法来求解、0-1背包问题适合用算法来求解。8. 分治法是将一个规模为 n的问题分解为k个规模的子问题，这些子问题 且与原问题。递归地求解这些子问题，然后将各个子问题的解 得到原问题的解。9. 动态规划算法的两个基本要素是 和。10. 算法可以有效地解凸多边形最优三角剖分问题，而算法是求解最优装载问题的有效方法。二、简答题(每小题10分，共计40分)1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上 什么步骤？2. 请简述什么是贪心选
3、择性质3. 请简述什么是最小生成树。4. 请简述贪心算法比动态规划算法效率高的原因。三、算法分析和设计题 （每小题10分，共计20分）1. 请写岀汉诺塔问题的简要递归算法。2. 请设计一个在有序数组 a1.n中二分搜索元素x的递归算法，要求若x在数组中则返回其下标 否则返回0.2010学年上学期期末考试模拟试题二一、填空题（每小题4分，共计40分）1. 算法是满足输入、输岀、确定性和有限性的指令序列。程序与算法不同，程序是算法用某种_的具体实现。程序不满足算法的 性质。2. 实践表明，可操作性最好且最有实际价值的是 情况下的时间复杂性。3. 直接或间接调用自身的算法称为，用函数自身给岀定义的函
4、数是4. 找硬币问题是用 求解的典型例子，而最长公共子序列问题则适合用 求解。5. 函数式 An2+Bn+C勺复杂度是，函数式Cn复杂度是。6. 对于表达式n3、5n7. 二分搜索算法是应用 的典型例子。这个方法很好地利用n个元素这个条件。可在最坏情况下用 时间完成搜索，而顺序搜索法在最坏情况下需要 时间完成搜索。8. 如果某问题具有 和两个重要性质，该问题可以用动态规划算法求解。9. 备忘录方 法是动态规划算 法的变形。与动态规 划算法 不同的是，备忘 录方法的递 归方式 是，而动态规划算法的递归方式则是 。10. 部分背包问题适用于算法求解、而0-1背包问题适用于算法求解。二、简答题（每小
5、题10分，共计40分） 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写岀该方程的一般形式，并指岀其中各参数的意义。 0-1背包问题的形式化描述是什么？ 请简述贪心算法的简要求解步骤。 请简述归并排序的基本思想。、log n， 20n,按照渐近阶从低到高的顺序排列，顺序是、 、 。三、算法分析和设计题(每小题10分，共计20分)1. 请写出Fibonacci数列的递归定义式及其简要递归算法。2请写岀二分搜索算法的简单程序描述(用java或C+语言)。2010年上学期期末考试模拟试题三一、填空题(每小题4分，共计40分)1. 算法是满足 、和 等四个性质的指令序列。2.
6、 算法复杂性的高低体现在运行该算法所需的计算机资源的多少上，计算机的资源最重要的是和，因此算法的复杂性有 和 之分。3. 与分治法类似，动态规划算法的基本思想是，先求解，然后从这些解得到原问题的解。与分治法不同的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是 的。4. Java语言的类(class) 体现了抽象数据类型(ADT)的思想，一般由4个部分组成：、和。5. 抽象数据类型的英文简称是 ，它是算法的一个 连同定义在该模型上并作为算法构件的一组。6. O(f)+O(g)=，O(f)O(g)= 。7. 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模的相同问题，以
7、便各个击破，。8. 动态规划算法的第一步通常是刻画最优解的结构。当问题的最优解包含了其的最优解时，称该问题具有最优子结构性质。9. 动态规划算法与贪心算法的主要区别是 性质。10. 表示最优前缀码的二叉树总是一颗 ，即树中任一个结点都有两个儿子结点。二、简答题(每小题10分，共计40分)1. 请简述为什么部分背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。2. 请写出如图语法树所对应的矩阵链相乘的最优完全加括号方式。3. 按照下表中的字母岀现频率，请画岀哈夫曼树，并设计相应的哈夫曼编码。字母abcdef频率（千次）4513121695哈夫曼编码4. 请简述动态规划算法求解最优化问题的步骤。三、算法分析和设计题 （每小题10分，共计20分）1.请写岀阶乘函数的递归定义式及其简要递归算法。2. 给定图G=（V,E），其中，顶点集为 V=1,2,3,4,5,6，边集和每条边的权如图所示71kjl6I?丿 用Prim算法求该图的最小生成树（画图说明算法的求解过程） 用Kruskal算法求最小生成树（画图说明算法的求解过程）。已改成word文本 最新文件 仅供参考 方便更改
