《算法分析与设计》期末复习题
选择题
算法必须具备输入、输出和（ D ）等4个特性。 A．可行性和安全性 B．确定性和易读性 C．有穷性和安全性 D．有穷性和确定性 算法分析中，记号O表示（ B ），记号Ω表示（ A ） A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界
假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题（ B ）解题方法：3*2^n*64=3*2^x A．n+8 B．n+6 C．n+7 D．n+5
设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。
A．O(logN) B．O(N) C．O(NlogN) D．O(N²logN) 直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法 C．迭代算法 D．回溯法 Fibonacci数列中，第4个和第11个数分别是（ D ）。 A．5，89 B．3，89 C．5，144 D．3，144
在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。 A．6条弦和7个三角形 C．6条弦和6个三角形 A．重叠子问题
B．5条弦和6个三角形 D．5条弦和5个三角形
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
B．最优子结构性质
C．贪心选择性质 D．定义最优解 下列哪个问题不用贪心法求解（ C ）。 A．哈夫曼编码问题 C．最大团问题 A．备忘录法 C．贪心法 A．贪心法
B．单源最短路径问题 D．最小生成树问题 B．动态规划法
D．回溯法
下列算法中通常以自底向上的方式求解最优解的是（ B ）。
下列算法中不能解决0/1背包问题的是（ A ）。
B．动态规划
C．回溯法 D．分支限界法 下列哪个问题可以用贪心算法求解（ D ）。
A．LCS问题 B．批处理作业问题
C．0-1背包问题 D．哈夫曼编码问题
用回溯法求解最优装载问题时，若待选物品为m种，则该问题的解空间树的结点个数为（ ）。 A．m!
B．2m+1
C．2m+1-1 D．2m 二分搜索算法是利用（ A ）实现的算法。
A．分治策略 B．动态规划法 C．贪心法 D．回溯法 下列不是动态规划算法基本步骤的是（ B ）。P44 A．找出最优解的性质 B．构造最优解 C．算出最优解(应该是最优值) D．定义最优解 下面问题（ B ）不能使用贪心法解决。 A．单源最短路径问题 C．最小花费生成树问题
B．N皇后问题
D．背包问题
使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为（ A ）。P17
A．O(1)，O(logn) B．O(n)，O(logn) C．O(1)，O(nlogn) D．O(n)，O(nlogn) 优先队列式分支限界法选取扩展结点的原则是（ C ）。P162 A．先进先出
B．后进先出
C．结点的优先级 D．随机 下面不是分支界限法搜索方式的是（ D ）。P161 A．广度优先
B．最小耗费优先
D．深度优先
C．最大效益优先 A．最小堆 C．栈
分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
B．最大堆
D．数组
下列关于计算机算法的描述不正确的是（ C ）。P1 A．算法是指解决问题的一种方法或一个过程 B．算法是若干指令的有穷序列 C. 算法必须要有输入和输出 D．算法是编程的思想
下列关于凸多边形最优三角剖分问题描述不正确的是（ A ）。 A．n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖分对应 B．在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦 C．该问题可以用动态规划法来求解
D．在有n个顶点的凸多边形的三角剖分中，恰有n-2个三角形 动态规划法求解问题的基本步骤不包括（ C ）。P44 A．递归地定义最优值
B．分析最优解的性质，并刻画其结构特征
C．根据计算最优值时得到的信息，构造最优解 (可以省去的) D．以自底向上的方式计算出最优值
分治法所能解决的问题应具有的关键特征是（ C ）。P16 A．该问题的规模缩小到一定的程度就可以容易地解决 B．该问题可以分解为若干个规模较小的相同问题
C．利用该问题分解出的子问题的解可以合并为该问题的解 D．该问题所分解出的各个子问题是相互独立的 下列关于回溯法的描述不正确的是（ D ）。P114 A．回溯法也称为试探法
B．回溯法有“通用解题法”之称
C．回溯法是一种能避免不必要搜索的穷举式搜索法 D．用回溯法对解空间作深度优先搜索时只能用递归方法实现 常见的两种分支限界法为（ D ）。P161 A. 广度优先分支限界法与深度优先分支限界法； B. 队列式（FIFO）分支限界法与堆栈式分支限界法； C. 排列树法与子集树法；
D. 队列式（FIFO）分支限界法与优先队列式分支限界法； 填空题
f(n)=3n2+10的渐近性态f(n)= O( n2 )， g(n)=10log3n的渐近性态g(n)= O( n )。
一个“好”的算法应具有正确性、 可读性 、 健壮性 和高效率和低存储量需求等特性。
算法的时间复杂性函数表示为 C=F(N,I,A) ，分析算法复杂性的目的在于比较 求解同意问题的两个不同算法的效率 的效率。
构成递归式的两个基本要素是 递归的边界条件 和 递归的定义 。 单源最短路径问题可用 分支限界法 和 贪心算法 求解。
用分治法实现快速排序算法时，最好情况下的时间复杂性为 O(nlogn) ，最坏情况下的时间复杂性为 O(n^2) ，该算法所需的时间与 运行时间 和 划分 两方面因素有关。P26
0-1背包问题的解空间树为 完全二叉 树；n后问题的解空间树为 排列 树； 常见的分支限界法有队列式（FIFO）分支限界法和优先队列式分支限界法。 回溯法搜索解空间树时常用的两种剪枝函数为 约束函数 和 剪枝函数 。
分支限界法解最大团问题时，活结点表的组织形式是 最大堆 ；分支限界法解单源最短路径问题时，活结点表的组织形式是 最小堆 。 算法填空题
递归求解Hanoi塔问题/阶乘问题。 例1 :阶乘函数n! P12 阶乘的非递归方式定义：
n!n(n1)(n2)21试写出阶乖的递归式及算法。
n0 递归式为： 1 边界条件
n ( n 1 )! 递归方程n0
递归算法： int factorial (int n)
{ if (n==0) return 1; 递归出口 return n * factorial (n-1); 递归调用 }
例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15
其中Hanoi (int n, int a, int c, int b)表示将塔座A上的n个盘子移至塔座C，以塔座B为辅助。
n!Move(a,c)表示将塔座a上编号为n的圆盘移至塔座c上。
void hanoi (int n, int a, int c, int b) {
if (n > 0) {
hanoi(n-1, a, b, c); move(a,c); hanoi(n-1, b, c, a); } }
用分治法求解快速排序问题。
快速排序算法 P25 、作业、课件第2章（2）42页-50页 template void QuickSort (Type a[], int p, int r) { if (p Partition函数的具体实现 template int Partition (Type a[], int p, int r) { int i = p, j = r + 1; Type x=a[p]; D=i; Q[i-1].d=*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) D]; [i]=w[Q[i-1].ID]; } =0; =0; =c; =n; =0; (1); delete[] Q; delete[] ; delete[] ; return ; } 例2：批处理作业调度 课件第5章(2)P2-5问题描述,课本P125-127 解空间：排列树 算法描述： class Flowshop { static int [][] m, 2A5A 1 A N W P 2 5 12 1 15 30 2 3 25 44 4 27 46 5 30 50 bestp=0,将物体的序号按价值体积比排序结果是（2,1,3,4,5） P/W (2). 根据排序得到部分解(1,1,1,0)，估计当前部分解的价值b,86+(50-45)*=, b >bestp. (3). 继续向下搜索生成结点F，得到可行解(1,1,1,0,0)，得到价值为86，更新bestp=86(如图第3步) 第3步 第5步 第8步 (4). 回溯：沿E回溯到左孩子D，生成相应右孩子G，得到部分解( 1,1,0,1 ),此时b= b>bestp,可以生成右子树（第4步在第5步的基础上没有H和I的图形） (5). 继续生成结点H,I，得到可行解( 1,1,0,1,0 ),价值为88，更新bestp=88(如图第5步) (6). 回溯H生成J，得到部分解( 1,1,0,0 ),估计部分解b=92>88（第6步在第8步的基础上没有K和L的图形） (7). 继续生成结点K，得到可行解( 1,1,0,0, 1 ),价值为92，更新bestp=92（第7步在第8步的基础上没有L的图形） (8). K是左孩子，生成其对应的右孩子L，得到可行解( 1,1,0,0,0) (如图第8步) (9). 回溯,沿结点L向上回溯到结点B,生成结点M,得到部分解 (1,0), 估计部分解b=90<92,回溯（第9步在第10步的基础上没有N的图形） (10). 向上继续回溯生成结点N，得到部分解(0)，此时得到的b=74+10*(46/27) =<92,回溯，此时已回到根结点，结束。最优解( 1,1,0,0, 1 ),价值为92. (如图第10步) 练习 n=8, M=110， W=( 1, 11,21,23,33,43,45,55 ) P=(11,21,31,33,43,53,55,65 ) 用回溯法求此0-1背包问题的最优解。 最优装载问题 P119 课件第P37- P54页 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = c2 =12. 试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。 要求： 列出问题的解空间。 构造解空间树。 根据递归回溯算法求出最优解和最优值。 算法设计题 使用贪心算法求解。 题型一： 开会问题： 某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。 解题算法: template void GS (int n, Type s[], Type f[], bool A[]) { A[1]=false; int j=1; int sum=0; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { A[i]=false; j=i; } else {A[i]=true; sum++;} } } 题型二： 试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n比较小的例子，看能否从中找出规律： 算法分析： 猜想一下是不是将n拆成尽量多的数乘积最大（拆出的数中最小为2）。 为了使因数个数尽可能多，我们用n减2、3…i，直到n 因此我们可以得到一个贪心策略，即将n不停地拆分开来，使得所有的数都不同且不能再拆。 解题算法: 题型三： 田忌赛马：如果3匹马变成n匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子。已知国王和田忌的所有马的奔跑速度，并且所有马奔跑的速度均不相同，现已经对两人的马分别从快到慢排好序，请设计一个算法，帮助田忌赢得最多的银子。 解题思路： 先对两组马按速度排序。 如果田忌(A)最快的马比齐王(B)最快的马快,直接赢; 如果A最快的马比B慢,用A最慢的马拼B最快的马; 如果A最慢的马比B最慢的马快,直接拼掉; 如果A最慢的马比B最慢的马慢,用A最慢的马拼B最快的马; 如果A和B最快和最慢的马都速度相同,用A最慢的马拼B最快的马 算法分析: 因篇幅问题不能全部显示，请点此查看更多更全内容