《算法分析与设计期末考试复习题纲》由会员分享，可在线阅读，更多相关《算法分析与设计期末考试复习题纲（29页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计期末复习题一、选择题1. 算法必须具备输入、输出和（ D ）等 4 个特性。A. 可行性和安全性B.确定性和易读性C.有穷性和安全性D.有穷性和确定性2.算法分析中，记号0表示（B ），记号Q表示（A ）A. 渐进下界B.渐进上界C .非紧上界D.紧渐进界3假设某算法在输入规模为n时的计算时间为T（n）=3*25。在某台 计算机上实现并完成概算法的时间为 t 秒。现有另一台计算机， 其运行速度为第一台的 64 倍，那么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题？（B ）解题方法：3*2八 n*64=3*2xA. n+8B. n+6C. n+7D. n+54.设问
2、题规模为N时，某递归算法的时间复杂度记为T（N），已知T（1）=1， T（N）=2T（N/2）+N/2 ，用 0表示的时间复杂度为 （ C ）。A. 0(logN)B. 0(N)C. 0(NlogN)D. 0(N2logN)5. 直接或间接调用自身的算法称为（B ）。A.贪心算法B.递归算法C.迭代算法D.回溯法C 0-1 背包问题D哈夫曼编码问题A 5，89B 3，89C 5，144D 3，1447. 在有 8 个顶点的凸多边形的三角剖分中，恰有（ B ）。A. 6条弦和7个三角形B. 5条弦和6个三角形C6 条弦和 6 个三角形D5 条弦和 5 个三角形8. 一个问题可用动态规划算法或贪心
3、算法求解的关键特征是问题的（ B ）。A.重叠子问题B最优子结构性质C.贪心选择性质D定义最优解9. 下列哪个问题不用贪心法求解（C）。A.哈夫曼编码问题B单源最短路径问题C.最大团问题D最小生成树问题10. 下列算法中通常以自底向上的方式求解最优解的是 （ B ）A. 备忘录法B.动态规划法C.贪心法D .回溯法11. 下列算法中不能解决 0/1 背包问题的是（ A ）A.贪心法B动态规划C.回溯法D分支限界法12. 下列哪个问题可以用贪心算法求解（D ）。A. LCS问题B批处理作业问题13. 用回溯法求解最优装载问题时，若待选物品为m种，贝卩该问题的解空间树的结点个数为()Am!B2m+
4、1D2mC2m+1-114. 二分搜索算法是利用( A )实现的算法。A. 分治策略B.动态规划法C.贪心法D.回溯法15. 下列不是动态规划算法基本步骤的是(B )。P44A. 找出最优解的性质B.构造最优解C.算出最优解(应该是最优值)D.定义最优解16. 下面问题( B )不能使用贪心法解决。A. 单源最短路径问题B . N皇后问题C.最小花费生成树问题D 背包问题17. 使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为( A )。 P17 AO(1)， O(logn)BO(n)， O(logn)CO(1)， O(nlogn)DO(n)
5、， O(nlogn)18. 优先队列式分支限界法选取扩展结点的原贝是(C )。P162A.先进先出B后进先出随机C.结点的优先级19. 下面不是分支界限法搜索方式的是（D ）。 P161A.广度优先B.最小耗费优先C.最大效益优先D.深度优先20. 分 支限界法 解 最大 团问 题 时，活结 点 表的组织形 式是（ B ）。A.最小堆B.最大堆C.栈D.数组21. 下列关于计算机算法的描述不正确的是（ C ）。 P1A. 算法是指解决问题的一种方法或一个过程B. 算法是若干指令的有穷序列C. 算法必须要有输入和输出D. 算法是编程的思想22. 下列 关于凸多边形最优三角剖分问 题 描述不正确的
6、 是 （ A ）。A. n+1 个矩阵连乘的完全加括号和 n 个点的凸多边形的三角剖 分对应B. 在有n个顶点的凸多边形的三角剖分中，恰有 n-3条弦C. 该问题可以用动态规划法来求解D. 在有n个顶点的凸多边形的三角剖分中，恰有 n-2个三角形23. 动态规划法求解问题的 基本步骤不包括（C ）。P44A. 递归地定义最优值B. 分析最优解的性质，并刻画其结构特征C. 根据计算最优值时得到的信息，构造最优解(可以省去的)D. 以自底向上的方式计算出最优值24. 分治法所能解决的问题应具有的关键特征是(C )。P16A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个
7、规模较小的相同问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的25. 下列关于回溯法的描述不正确的是( D )。P114A. 回溯法也称为试探法B. 回溯法有“通用解题法”之称C. 回溯法是一种能避免不必要搜索的穷举式搜索法D. 用回溯法对解空间作深度优先搜索时 只能用递归方法实现26. 常见的两种分支限界法为(D )。P161A. 广度优先分支限界法与深度优先分支限界法；B. 队列式(FIFO)分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式(FIFO)分支限界法与优先队列式分支限界法；二、填空题1. f(n)=3n
8、2+10 的渐近性态 f(n)= 0( n2 ),g(n)=10log3 n 的渐近性态 g(n)= 0( n)。2. 一个“好”的算法应具有正确性、可读性、 健壮性和高效率和低存储量需求等特性。3. 算法的时间复杂性函数表示为C=F(N,I,A)，分析算法复杂性的目的在于比较求解同意问题的两个不同算法的效率的效率。4. 构成递归式的两个基本要素是递归的边界条件 和 递归的定义。5. 单源最短路径问题可用 分支限界法 和贪心算法求解。6. 用分治法实现快速排序算法时，最好情况下的时间复杂性为_O(nlogn)，最坏情况下的时间复杂性为0(n2)，该算法所需的时间与 运行时间 和划分 两方面因素
9、有关。P267. 0-1背包问题的解空间树为完全二叉树;n后问题的解空间树为排树；8. 常见的分支限界法有队列式( FIFO) 分支限界法和优先队列式分支限 界法。9. 回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝函数。10. 分支限界法解最大团问题时，活结点表的组织形式是最大堆;分支限界法解单源最短路径问题时，活结点表的组织形式是 最小堆 。三、算法填空题1.递归求解Hanoi塔问题/阶乘问题例1 :阶乘函数n! P12阶乘的非递归方式定义:试写出阶乖的递归式及算法1n(n 1)!n =0n . 0边界条件递归方程递归算法:int factorial (int n)递归出口递归调用
10、 if (n=0) retur n 1;return n * factorial (n-1);例2:用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。P15其中Hanoi (int n, int a, int c, int b)表示将塔座 A上的n个盘子移至塔座C,以塔座B为辅助。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);2. 用分治法求解快速排序问题。快速排序算法 P25 、
11、作业、课件第 2章(2)42页-50 页 templatevoid QuickSort (Type a, int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1);QuickSort (a,q+1,r) ；Partition 函数的具体实现templateint Partition (Type a, int p, int r)int i = p, j = r + 1;Type x=ap;/将 x 的元素交换到左边区域/将 x 的元素交换到右边区域while (true) while (a+i x & ix);if (i =
12、j) break;Swap(ai, aj);ap = aj;aj = x;return j;3. 用贪心算法求解最优装载问题。最优装载问题 P95 课件第 4章(2) 第3-8 页 templatevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1;Sort(w, t, n);for (int i = 1; i = n; i+) xi = 0;for (int j = 1; j = n & wtj = c; j+)xti = 1; c -= wtj;4. 用回溯法求解 0-1 背包/ 批处理作业调度 / 最大团问题，要
13、会画解空间 树。例1:用回溯法求解0-1背包 P133课件第5章 第24-38页templateclass Knapprivate:Typep Bound(int i); / 计算上界void Backtrack(int i);Typew c; / 背包容量int n; / 物品数Typew *w; /物品重量数组Typep *p; /物品价值数组Typew cw; /当前重量Typep cp; /当前价值Typep bestp; /当前最优价值;void Knap:Backtrack(int i) if(in) bestp=cp; return; if(cw+wibestp) / 进入右子树Backtrack(i+1);Typep Knap:Bound(int i)Typew cleft=c-cw; / 剩余的背包容量Typep b=cp; /b为当前价值/ 依次装入单位重量价值高的整个物品while(i=n&wi=cleft)
