算法设计复习题

一、选择题.选出不是算法所必须具备的特征(C)。A有穷性B确切性C高效性D可行性.不属于给合问题的是(C)。AEuler的36名军官问题 B图的Hamiliton C求二项式展开系数 D集合的幕集.下列(C)不是衡量算法的标准。A时间效率B空间效率C问题的难度D适应能力.下列函数关系随着输入量增大增加量最快的是(D)。Alogn Bn3 C2n Dn!.如果某一算法的执行时间不超过输入规模的2倍，那么算法渐近时间复杂度为(B)。AO(2n)BO(n) C®(n) DQ(n).下列程序段的算法时间复杂度是(D)for(i=1;i<=n;i++)for(j=1;i<=m;m++)S;AO(n2) BO(m2) CO(m+n)DO(mn).下列程序段S执行次数为(C)。for(i=1;i<=n;i++)for(j=1;i<=m;m++)S;An2 Bn2/2 Cn(n+1)Dn(n+1)/2.使用F(n)=n*f(n-1)递归求F(4),递归调用子函数的次数为(D)。A 3次 B4次 C 5次 D 8次.递推关系M(n)=M(n-1)+1,M(0)=0的算法时间复杂度为(C)。A O(n!) BO(2n) C O(n) D O(1).与递推关系x(n)=2x(n-1)+1,x(1)=1等价的通项公式为(B)。Ax(n)=2n B x(n)=2n-1 Cx(n)=2n+1Dx(n)=n!.三个盘子的汉诺塔，至少要执行移动操作次数为(D)。A1次 B3次 C6次D7次.Fibonacci数列第10项为(D)。A3 B13 C21 D34.12个金币中有一枚是假币，至少需要称量的次数是(C)。A0 B1 C3 D4.二维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是(C)。A1个 B2个 C6个D8个.一维最近邻点问题，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是(B查的点的个数是(B)。A1个 B2个.下列图形不属于凸集的是(DA三角形 B四边形.对于凸集下列说法正确的是(BC6个D8个)。C五边形D五角星)。A凸集中的所有点都属于凸包；B凸集中任意两点的连线都在凸中；C凸集中任意两点的连线都不在凸集中；D一个点集如果不是凸集，则点集中任意两点的连线都不在凸集中.下列是动态规划算法基本要素的是(A)。A最优子结构 B构造最优解 C贪心选择因子 D界限函数.下列问题中具有多项式解法的是(C)。A背包问题 B生成排列序列问题 Cn个元素的排序问题D集合的幕集问题.如果背包的容量为100,而物体共有10件，则使用动态规划求解背包问题数组大小为(D)。A10B100C1000D10000.排列问题属于(D)。A可解问题 B不可解问题 CP问题DNP问题.(A)算法应用到广度优先遍历策略。A分支界限法B动态规划法 C分治法D回溯法.Dijstra算法属于(A)。A贪心算法 B概率算法 C回溯法D分支限界法.若f(n)=2n3+3n,g(n)=100n2+2n+100,则U£=0值)为(B)。A真 B假 C无法确定 D均不是.若f(n)=50n+logn,g(n)=10n+loglogn,则Uf=O(g)为(A)。A真 B假 C无法确定 D均不是.Prim算法求最小生成树采用的是(A)算法思想。A贪心算法 B动态规划法C回溯法D蛮力法二、简答题.给出递推公式x(n)=x(n-1)+n,x(0)=0对应的通项公式计算过程?解：X(n)-X(n-1)=nX(n-1)-X(n-2)=n-1X(1)-X(0)=1X(n)-X(0)=(n+1)n\2X(n)=(n+1)n\2.0、®、Q之间的区别与联系是什么？答：0描述增长率的上限@用来表示算法的精确阶Q描述增长率的下限只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，3种等渐近符号。.什么是数据结构，什么是算法，两者有什么关系？答：数据结构：计算机存储/族素质数据的方式。算法：一系列解决问题的指令。程序二算法+数据结构.将4n2,lo部例例n2n加箝!按渐近阶从低到高顺序排序。答：2<n2/3<logn<20n<4n2<3n<n!.举例说明分治法、动态规划法和贪心法适用范围，及三者之间的区别。答：分治法：适用于原问题可划分为子问题时如汉诺塔问题（循环赛，最近对，棋盘覆盖等）动态规划：当原问题可分解为子问题茄子问题重叠并且具有最优子结构时可用动态规划法，如TSP问题（多端最短路径问题，0/1背包问题等）贪心：当一个问题具有最优子结构性质且具有贪心选择性时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）在分治法德基础上，满足最优子结构性质才能用动态规划，在动态规划可行的基础上满足贪心选择性才能用贪心。.简述分治法、贪心法、蛮力法、回溯法、减治法的设计思想。答：分治：建一个难以直接解决的大问题划分成一些规模较小的子问题，以便各个击破，分而治之。贪心：指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优。蛮力：采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。回溯：只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完全解，则对其进一步构造，否则，就不必继续构造这个解了。减治：把一个大问题划分为若干子问题，但些子问题不需要分别求解，只需求解其中那个一个子问题。.举例说明分治法和减治法的在设计上区别与联系。答：分治法是将一个大问题分解为若干子问题分别求解，而减治法是只求解部分子问题。.简述什么是欧拉回路，TSP问题，哈密顿回路问题。答：欧拉回路：图G的一个回路，若它恰它通过G中每条边一次，则称该回路为欧拉回路。TSP：从图的一个顶点出发，每个定点只能访问一次，最后回到原点且使路径最短。哈密顿回路：从一个城市出发，紧锅盖每一个城市恰好一次，然后回到出发城市。.Strassen矩阵乘法可以利用什么算法实现.答：可用分治法实现。三.应用题.给出应用动态规划法设计算法的一般步骤，并用动态规划法求下面多段图中从顶点0到顶点15的最短路径，写出求解过程。

解:解:d(0,9)=min{coi+d(1,9),c02+d(2,9),c03+d(3,9)}d(1,9)=min{c14+d(4,9),c15+d(5,9)}d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=min{c35+d(5,9),c36+d(6,9)}d(4,9)=min{c47+d(7,9),c48+d(8,9)}d(5,9)=min{c57+d(7,9),c58+d(8,9)}d(0,9)=min{c67+d(7,9),c68+d(8,9)}d(7,9)=c79=7(7-9)d(8,9)=c89=3(8-9)d(6,9)=min{6+7,5+3}=8(6-8)d(5,9)=min{8+7,6+3}=9(5-8)d(4,9)=min{5+7,6+3}=9(4-8)d(3,9)=min{4+9,7+8}=13(3-5)d(2,9)=min{6+9,7+9,8+8}=15(2-4)d(1,9)=min{9+9,8+9}=17(1-5)d(0,9)=min{4+17,2+15,3+13}=16(0-3)最后得最短路径为0-3—5—8-9长度为16。.有4个物品，其重量分别为(4,7,5,3)，物品的价值分别为(40,42,25,12)，背包容量为10。试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。解:按单位价值最大，装入物品1、3总价值65按背包容量最大，装入物品2,4总价值54.给出｛2313496311928探用快速排序思想进行排序时一次划分的过程示意图。解:191919131313解:1919191313134923666233131312349492828284.画出当4.画出当n有4个顶点的货郎担问题，其费用矩阵如图所示，求从顶点1出发，最后回到顶点1的最短路线。画出解空间树搜索过程。

888178851728625384时，0/1背包问题的状态空间树5.画出当n4时，0/1背包问题的状态空间树给定背包容量W=10,每件物体的重量以及价值为14(42),6(12),8(40),10(25)，画出解空间树搜索过程。四、算法设计题.给定数组A[n],存储n个实数，试设计一个算法，在最坏情况下用最少比较次数找出该数组中元素的最大值和最小值，并说明采用了何种算法设计思想，其最坏比较多少次。.描述贪心法的求解过程，给出基于最近邻点策略采用贪心法求解TSP问题伪代码，并分析该算法的时间性能。.设计算法实现求数组中相差最小的两个元素(称为最接近数)的差。.有n枚硬币，其中有一枚硬币是假币，且假币的重量较轻，通过一架天平找出假币，设计找出假币的方案，要求在最坏情况下用天平的比较次数最少。.一个农夫带着一条狼、一只羊和一筐菜，想从河一