《算法设计复习题》由会员分享，可在线阅读，更多相关《算法设计复习题（7页珍藏版）》请在金锄头文库上搜索。
1、1一、选择题1选出不是算法所必须具备的特征（C） 。A 有穷性 B 确切性 C 高效性 D 可行性2不属于给合问题的是（ C ） 。A Euler 的 36 名军官问题 B 图的 Hamiliton C 求二项式展开系数 D 集合的幂集3下列（ C ）不是衡量算法的标准。A 时间效率 B 空间效率 C 问题的难度 D 适应能力4下列函数关系随着输入量增大增加量最快的是（ D ） 。A logn Bn3 C2n D n!5如果某一算法的执行时间不超过输入规模的 2 倍，那么算法渐近时间复杂度为（ B ） 。A O(2n) B O(n) C (n) D (n)6下列程序段的算法时间复杂度是（ D
2、）for (i=1;i=n;i+)for (j=1;i=m;m+)S;A O(n2) B O(m2) C O(m+n) D O(mn)7下列程序段 S 执行次数为（ C ） 。for (i=1;i=n;i+)for (j=1;i=m;m+)S;A n2 B n2/2 C n(n+1) D n(n+1)/28使用 F(n)=n*f(n-1)递归求 F（4） ，递归调用子函数的次数为（D ） 。A 3 次 B 4 次 C 5 次 D 8 次9递推关系 M(n)=M(n-1)+1,M(0)=0 的算法时间复杂度为（ C ） 。A O(n!) B O(2n) C O(n) D O(1)10与递推关系
3、x(n)=2x(n-1)+1,x(1)=1 等价的通项公式为（ B ） 。A x(n)=2n B x(n)=2n-1 C x(n)=2n+1 D x(n)=n!11三个盘子的汉诺塔，至少要执行移动操作次数为（ D ） 。A1 次 B 3 次 C 6 次 D 7 次12Fibonacci 数列第 10 项为（D） 。A 3 B 13 C 21 D 341312 个金币中有一枚是假币，至少需要称量的次数是（ C ） 。A 0 B 1 C 3 D 414二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（C ） 。A 1 个 B 2 个 C 6 个 D 8 个
4、15一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（ B ） 。A 1 个 B 2 个 C 6 个 D 8 个15下列图形不属于凸集的是（ D ） 。A 三角形 B 四边形 C 五边形 D 五角星16对于凸集下列说法正确的是（ B ） 。A 凸集中的所有点都属于凸包； B 凸集中任意两点的连线都在凸中；C 凸集中任意2两点的连线都不在凸集中；D 一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中17下列是动态规划算法基本要素的是（ A ） 。A 最优子结构 B 构造最优解 C 贪心选择因子 D 界限函数18下列问题中具有多项式解法的是（C） 。
5、A 背包问题 B 生成排列序列问题 C n 个元素的排序问题 D 集合的幂集问题19如果背包的容量为 100，而物体共有 10 件，则使用动态规划求解背包问题数组大小为（D ） 。A 10 B 100 C 1000 D 1000020排列问题属于（ D ） 。A 可解问题 B 不可解问题 C P 问题 D NP 问题21 （A ）算法应用到广度优先遍历策略。A 分支界限法 B 动态规划法 C 分治法 D 回溯法22Dijstra 算法属于（ A ） 。A 贪心算法 B 概率算法 C 回溯法 D 分支限界法23若 f(n)=2n3+3n，g(n)=100n 2+2n+100，则 f=O(g)为（
6、 B ） 。A 真 B 假 C 无法确定 D 均不是24若 f(n)=50n+logn，g(n)=10n+loglogn ，则 f=O(g)为（ A ） 。A 真 B 假 C 无法确定 D 均不是25Prim 算法求最小生成树采用的是（ A ）算法思想。A 贪心算法 B 动态规划法 C 回溯法 D 蛮力法二、简答题1给出递推公式 x(n)=x(n-1)+n,x(0)=0 对应的通项公式计算过程？解：X(n)-X(n-1)=nX(n-1)-X(n-2)=n-1 X(1)-X(0)=1X(n)-X(0)=(n+1)n2X(n)= (n+1)n22、之间的区别与联系是什么？答：描述增长率的上限用来表
7、示算法的精确阶描述增长率的下限只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，3 种等渐近符号。3什么是数据结构，什么是算法，两者有什么关系？答：数据结构：计算机存储/族素质数据的方式。算法：一系列解决问题的指令。程序=算法+ 数据结构4将 4n2,logn,3n,20n,2,n2/3,n!按渐近阶从低到高顺序排序。3答：2n2/3 log n20n4n2 3nn!5举例说明分治法、动态规划法和贪心法适用范围，及三者之间的区别。答：分治法：适用于原问题可划分为子问题时如汉诺塔问题（循环赛，最近对，棋盘覆盖等）动态规划：当原问题可分解为子问题茄子问题重叠并且具有最优子结构时
8、可用动态规划法，如 TSP 问题（多端最短路径问题，0/1 背包问题等）贪心：当一个问题具有最优子结构性质且具有贪心选择性时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）在分治法德基础上，满足最优子结构性质才能用动态规划，在动态规划可行的基础上满足贪心选择性才能用贪心。6简述分治法、贪心法、蛮力法、回溯法、减治法的设计思想。答：分治：建一个难以直接解决的大问题划分成一些规模较小的子问题，以便各个击破，分而治之。贪心：指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优。蛮力：采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。回溯：只构造可能解的一部分，然后
9、评估这个部分解，如果这个部分解有可能导致一个完全解，则对其进一步构造，否则，就不必继续构造这个解了。减治：把一个大问题划分为若干子问题，但些子问题不需要分别求解，只需求解其中那个一个子问题。7举例说明分治法和减治法的在设计上区别与联系。答：分治法是将一个大问题分解为若干子问题分别求解，而减治法是只求解部分子问题。8简述什么是欧拉回路，TSP 问题，哈密顿回路问题。答：欧拉回路：图 G 的一个回路，若它恰它通过 G 中每条边一次，则称该回路为欧拉回路。TSP：从图的一个顶点出发，每个定点只能访问一次，最后回到原点且使路径最短。哈密顿回路：从一个城市出发，紧锅盖每一个城市恰好一次，然后回到出发城市
10、。9Strassen 矩阵乘法可以利用什么算法实现.答：可用分治法实现。三应用题1给出应用动态规划法设计算法的一般步骤，并用动态规划法求下面多段图中从顶点 0 到顶点 15 的最短路径，写出求解过程。2120345678949387684 7568665374解：d(0,9)=minc01 +d(1,9) , c02+d(2,9) , c03 +d(3,9) d(1,9)=minc14 +d(4,9) , c15+d(5,9) d(2,9)=minc24 +d(4,9) , c25+d(5,9) , c26 +d(6,9) d(3,9)=minc35 +d(5,9) , c36+d(6,9)
11、d(4,9)=minc47 +d(7,9) , c48+d(8,9) d(5,9)=minc57 +d(7,9) , c58+d(8,9) d(0,9)=minc67 +d(7,9) , c68+d(8,9) d(7,9)= c79 =7 (79)d(8,9)= c89 =3(89)d(6,9)=min6+7,5+3=8(68)d(5,9)= min8+7,6+3=9(58)d(4,9)= min5+7,6+3=9(48)d(3,9)= min4+9,7+8=13(35)d(2,9)= min6+9,7+9,8+8=15(24)d(1,9)= min9+9,8+9=17(15)d(0,9)=
12、min4+17,2+15,3+13=16(03)最后得最短路径为 03589 长度为 16。 2有 4 个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为 (40, 42, 25, 12)，背包容量为10。试设计 3 种贪心策略,并给出在每种贪心策略下背包问题的解。 解：按单位价值最大，装入物品 1、3 总价值 65按背包容量最大，装入物品 2，4 总价值 543给出23 13 49 6 31 19 28采用快速排序思想进行排序时一次划分的过程示意图。解：19 13 49 6 31 23 2819 13 23 6 31 49 2819 13 6 23 31 49 284画出当 时，
13、货郎担问题的状态空间树。给出4n 1 4 2 3 2 4 1 4 1 4 1 3 3 3 2 2 3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 3 1 3 2 1 4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 1 2 5有 4 个顶点的货郎担问题，其费用矩阵如图所示，求从顶点 1 出发，最后回到顶点 1 的最短路线。画出解空间树搜索过程。 1 7 8 5 1 7 2 6 2 5 3 5画出当 时，0/1 背包问题的状态空间树4n 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 给定背包容量 W=10，每件物体的重量以及价值为 14（42） ，6（12） ，8（40） ，10（25），画出解空间树搜索过程。四、算法设计题1给定数组 An，存储 n 个实数，试
