西安电子科技大学网络教育2010学年上学期期末考试模拟试题一课程名称：__ 算法分析与设计 考试形式： 闭 卷学习中心：_________ 考试时间： 90分钟姓 名：_____________ 学 号：一、填空题（每小题4分，共计40分）1. 通常只考虑三种情况下的时间复杂度，即 最坏 情况、 最好情况和 平均 情况下的时间复杂度，分别记为T max(N)、T min (N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 最坏 情况下的时间复杂度。

2. n n 1032 的渐近表达式是)(2n O ，)log(3n 的渐近表达式是 )(log n O 。

3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中的 常数因子 。

4. 递归算法是指 直接或间接地调用自身 的算法，递归函数是指用函数自身给出定义 的函数。

5. 贪心算法总是做出在当前看来___最好__的选择，也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的____局部最优选择_。

6. 如果某问题具有__贪心选择性质__和__最优子结构性质_两个重要性质，该问题可以用贪心算法求解。

7. 单源最短路径问题适合用__贪心算法__算法来求解、0-1背包问题适合用__动态规划算法__算法来求解。

8. 分治法是将一个规模为n 的问题分解为k 个规模__较小_的子问题，这些子问题_互相独立_且与原问题_相同_。

递归地求解这些子问题，然后将各个子问题的解_合并_得到原问题的解。

9. 动态规划算法的两个基本要素是__最优子结构（性质）_和__子问题重叠（性质）__。

10.__ 动态规划算法 算法可以有效地解凸多边形最优三角剖分问题，而_贪心算法_算法是求解最优装载问题的有效方法。

1. 算法是满足输入、输出、确定性和有限性的指令序列。

程序与算法不同，程序是算法用某种 程序设计语言的具体实现。

程序不满足算法的 有限性 性质。

2. 实践表明，可操作性最好且最有实际价值的是_最坏__情况下的时间复杂性。

3. 直接或间接调用自身的算法称为_递归算法_，用函数自身给出定义的函数是 __递归函数_。

4. 找硬币问题是用_贪心算法__求解的典型例子，而最长公共子序列问题则适合用_动态规划算法_求解。

5. 函数式An2+Bn+C 的复杂度是__)(2n O _，函数式Cn 复杂度是__ O(C n)__。

6. 对于表达式3n 、25n 、n log ，n 20, 按照渐近阶从低到高的顺序排列, 顺序是__n log __、__n 20_、__25n __、_3n __。

7. 二分搜索算法是应用__分治策略__的典型例子。

这个方法很好地利用n个元素__已排好序__这个条件。

可在最坏情况下用_)(log n O _时间完成搜索,而顺序搜索法在最坏情况下需要_)(n O _时间完成搜索。

8. 如果某问题具有__最优子结构（性质）__和__子问题重叠（性质）___两个重要性质_，该问题可以用动态规划算法求解。

9. 备忘录方法是动态规划算法的变形。

与动态规划算法不同的是，备忘录方法的递归方式是 自顶向下 ，而动态规划算法的递归方式则是 自底向上。

10.部分背包问题适用于__贪心算法__算法求解、而0-1背包问题适用于__动态规划算法___算法求解。

1. 算法是满足输入、输出、确定性和有限性等四个性质的指令序列。

2. 算法复杂性的高低体现在运行该算法所需的计算机资源的多少上，计算机的资源最重要的是时间和空间（即存储器），因此算法的复杂性有时间复杂性和空间复杂性之分。

3.与分治法类似，动态规划算法的基本思想是__将待求解问题分解为若干个子问题__，先求解__子问题_，然后从这些解得到原问题的解。

与分治法不同的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是__互相独立__的。

4. Java语言的类(class)体现了抽象数据类型(ADT)的思想，一般由4个部分组成：类名、数据成员、方法和访问修饰。

5. 抽象数据类型的英文简称是 ADT ，它是算法的一个 __数据模型_连同定义在该模型上并作为算法构件的一组__运算__ 。

6. O(f)+O(g)= O(f+g)__，O(f)O(g)= O(fg) 。

7. 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模__较小__的相同问题 , 以便各个击破，____分而治之___。

8. 动态规划算法的第一步通常是刻画最优解的结构。

当问题的最优解包含了其___子问题___的最优解时，称该问题具有最优子结构性质。

9. 动态规划算法与贪心算法的主要区别是__贪心选择性质__性质。

10.表示最优前缀码的二叉树总是一颗完全二叉树，即树中任一个结点都有两个儿子结点。

二、简答题（每小题10分，共计40分）1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？如果只需要求解问题的最优值，动态规划算法步骤如下：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；如果需要构造最优解，则还需要加上如下步骤：（4）根据计算最优值时得到的信息，构造最优解。

2. 请简述什么是贪心选择性质所谓贪心选择性质是指，所求问题的全局最优解可以通过一系列局部最优选择，即贪心选择来达到。

3. 请简述什么是最小生成树。

如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树上各边权的总和称为该生成树的耗费。

在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

4. 请简述贪心算法比动态规划算法效率高的原因。

动态规划算法需要知道所有子问题的解，而贪心算法不需要知道所有子问题的解，它只是在每一步迭代中选择看起来最好的解，并不从整体进行最优考虑，因此效率较高。

1. 请简述为什么部分背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

对于部分背包问题，依照贪心选择策略，可以得到最优解。

而0-1背包问题，贪心选择之所以不能得到最优解，是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。

因而我们选择的判断标准出现了误差。

2. 请写出如图语法树所对应的矩阵链相乘的最优完全加括号方式。

((A1(A2A3))(A4(A5A6)))3. 按照下表中的字母出现频率，请画出哈夫曼树，并设计相应的哈夫曼编码。

哈夫曼编码：4. 请简述动态规划算法求解最优化问题的步骤。

（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造最优解。

1. 分治算法由哪些基本步骤组成？分治算法的时间复杂性常满足什么样的递归方程，写出该方程的一般形式，并指出其中各参数的意义。

分治算法的一般步骤：分解 → 直接或递归求解子问题 → 组合递归方程分治算法的时间复杂性C(n)往往满足如下的递归方程：其中，n: 问题的规模。

n 0: 可直接解的问题规模的阈值。

a: 分解出的需要求解的子问题的个数。

n/c: 分解出的子问题的规模。

g(n): 分解规模为n 的问题以及组合相应子问题的解所需的时间。

d: 直接解规模为n 0的问题所需的时间。

2. 0-1背包问题的形式化描述是什么？∑∑==≤∈-≤≤>>>n i i i n i i i i n i i C x x x x v w C 1121x v ,x w },1,0{),,...,,(10n ,n i 1,0,0,0达到最大。

而且使得向量元要求找出给定3.请简述贪心算法的简要求解步骤。

贪心算法的简要求解步骤如下：① 将优化问题转化成这样的一个问题，即先做出选择，再解决剩下的⎩⎨⎧>+===00n n , )()()(n , )(n g c n aC n C n d n C一个子问题。

②证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全性。

③说明在做出贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解。

4.请简述归并排序的基本思想。

将待排序的序列分成长度大致相等的两个子序列，分别对2个子序列进行排序，最终将2个已排好序的子序列合并为有序的完整序列。

三、算法分析和设计题（每小题10分，共计20分）1. 请写出汉诺塔问题的简要递归算法。

public static void Hanoi(int n, int a, int b, int c){if( n>0 ){Hanoi( n-1, a,c,b );Move( a, b );Hanoi( n-1, c,b,a )；}}2. 请设计一个在有序数组a[1..n]中二分搜索元素x的递归算法，要求若x在数组中则返回其下标否则返回0.输入：正整数n和存储n个元素的数组a[1..n],被搜索的元素x输出：若x在数组中则返回其下标否则返回0i=binarysearch(1,n,a,x);return I;end BINARYSEARCH1过程 binarysearch(low,high,a,x)//在数组a 的下标为low 到high 范围内寻找x,//若找到x 则返回其下标否则返回0if low>high thenreturn 0;elsemid=[]2/)(high low +;if a[mid]=x thenreturn mid;else if a[mid]<x thenreturn binarysearch(low,mid-1,a,x);else return binarysearch(mid+1,high,a,x); end ifend if1. 请写出Fibonacci 数列的递归定义式及其简要递归算法。

Fibonacci 数列的递归定义式是：⎩⎨⎧>=-+-=11,0)2()1(1)(n n n F n F n F 当当 第n 个Fibonacci 数可以递归计算如下:public static int Fibonacci(int n){if( n<=1 ) return 1;return Fibonacci(n-1) + Fibonacci(n-2) ;}2. 请写出二分搜索算法的简单程序描述(用java 或C++语言)。

public static int BinarySearch(int[ ] a, int x, int n) {int left=0; int right=n-1;while(left<=right) {int middle = (left+right)/2;if(x==a[middle])return middle;if(x>a[middle])left = middle+1;elseright = middle-1;}return -1;}1. 请写出阶乘函数的递归定义式及其简要递归算法。