2013《计算机算法设计与分析》习题及答案.doc 15页

'《计算机算法设计与分析》习题及答案2013秋15 《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质  B、构造最优解  C、算出最优解D、定义最优解3、最大效益优先是（ A）的一搜索方式。A、分支界限法     B、动态规划法   C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B）。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5.回溯法解旅行售货员问题时的解空间树是（A）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（  B ）。A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度低D代码短8、以下不可以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题9.实现循环赛日程表利用的算法是（ A）。A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C）A数值概率算法B舍伍德算法C拉斯维加斯算法D蒙特卡罗算法11．下面不是分支界限法搜索方式的是（  D ）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（  D ）。A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。（B）A、分治法B、动态规划法C、贪心法D、回溯法14．哈夫曼编码的贪心算法所需的计算时间为（  B ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（  B ）。A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（  A）。A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（  C ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解19.回溯法的效率不依赖于下列哪些因素（D）A.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间15 20.下面哪种函数是回溯法中为避免无效搜索采取的策略（  B ）A．递归函数B.剪枝函数C。随机数函数D.搜索函数21、下面关于NP问题说法正确的是（B）ANP问题都是不可能解决的问题BP类问题包含在NP类问题中CNP完全问题是P类问题的子集DNP类问题包含在P类问题中22、蒙特卡罗算法是（  B ）的一种。A、分支界限算法     B、概率算法   C、贪心算法   D、回溯算法23.下列哪一种算法不是随机化算法（  C ）A.蒙特卡罗算法B.拉斯维加斯算法C.动态规划算法D.舍伍德算法24.（  D ）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质25.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法26.分支限界法解旅行售货员问题时，活结点表的组织形式是（A）。A、最小堆B、最大堆C、栈D、数组27、Strassen矩阵乘法是利用（ A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法29、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解30、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小生成树问题D背包问题31、下列算法中不能解决0/1背包问题的是（A）A贪心法B动态规划C回溯法D分支限界法32、回溯法搜索状态空间树是按照（C）的顺序。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历33、下列随机算法中运行时有时候成功有时候失败的是（C）A数值概率算法B舍伍德算法C拉斯维加斯算法D蒙特卡罗算法34．实现合并排序利用的算法是（  A ）。A、分治策略B、动态规划法C、贪心法D、回溯法35．下列是动态规划算法基本要素的是（  D ）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质36．下列算法中通常以自底向下的方式求解最优解的是（B）。A、分治法B、动态规划法C、贪心法D、回溯法37．采用广度优先策略搜索的算法是（  A ）。A、分支界限法B、动态规划法C、贪心法D、回溯法38、合并排序算法是利用（ A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法39、在下列算法中得到的解未必正确的是（  B ）。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法40、背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）41．实现大整数的乘法是利用的算法（  C ）。15 A、贪心法B、动态规划法C、分治策略D、回溯法42．0-1背包问题的回溯算法所需的计算时间为（  A ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43．采用最大效益优先搜索方式的算法是（ A ）。A、分支界限法B、动态规划法C、贪心法D、回溯法44．贪心算法与动态规划算法的主要区别是（ B ）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解45.实现最大子段和利用的算法是（ B）。A、分治策略B、动态规划法C、贪心法D、回溯法46.优先队列式分支限界法选取扩展结点的原则是（C）。A、先进先出B、后进先出C、结点的优先级D、随机47.背包问题的贪心算法所需的计算时间为（ B ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、广度优先是（  A ）的一搜索方式。A、分支界限法     B、动态规划法   C、贪心法   D、回溯法49、舍伍德算法是（  B ）的一种。A、分支界限算法     B、概率算法   C、贪心算法   D、回溯算法50下列哪一种算法是随机化算法（    D    ）A.贪心算法B.回溯法C.动态规划算法D.舍伍德算法51.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解52．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）53.以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法54.实现最长公共子序列利用的算法是（  B ）。A、分治策略B、动态规划法C、贪心法D、回溯法A.voidhanoi(intn,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}55.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔B.voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}15 C.voidhanoi(intn,intC,intB,intA){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}D.voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}56.动态规划算法的基本要素为（C）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用57.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用58.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先59.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先60.程序块（A）是回溯法中遍历排列树的算法框架程序。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}B.15 C.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}D.61.常见的两种分支限界法为（D）A.广度优先分支限界法与深度优先分支限界法；B.队列式（FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.队列式（FIFO）分支限界法与优先队列式分支限界法；二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法     用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。5、拉斯维加斯算法找到的解一定是正确解。6、算法是指解决问题的一种方法或一个过程。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法。10、数值概率算法常用于数值问题的求解。11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。12、利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法___。14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。1515 、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。16、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。17、矩阵连乘问题的算法可由动态规划设计实现。18、拉斯维加斯算法找到的解一定是正确解。19.贪心算法的基本要素是贪心选择性质和最优子结构性质。21.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。22.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。23、大整数乘积算法是用分治法来设计的。24、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。25、舍伍德算法总能求得问题的一个解。26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。27.快速排序算法是基于分治策略的一种排序算法。28.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。31.分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。32.分支限界法是一种既带有系统性又带有跳跃性的搜索算法。33.回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。34.任何可用计算机求解的问题所需的时间都与其规模有关。35.快速排序算法的性能取决于划分的对称性。36.所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。37.所谓最优子结构性质是指问题的最优解包含了其子问题的最优解。38.回溯法是指具有限界函数的深度优先生成法。39.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))）。40.回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架。41.用回溯法解0/1背包问题时，该问题的解空间结构为子集树结构。42.用回溯法解批处理作业调度问题时，该问题的解空间结构为排列树结构。43.旅行售货员问题的解空间树是排列树。15 三、算法填空1.背包问题的贪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){//重量为w[1..n]],价值为v[1..n]的n个物品，装入容量为M的背包//用贪心算法求最优解向量x[1..n]inti;Sort(n,v,w);for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}2.最大子段和:动态规划算法intMaxSum(intn,inta[]){intsum=0,b=0；//sum存储当前最大的b[j],b存储b[j]for(intj=1；j<=n；j++){if(b>0)b+=a[j]；elseb=a[i];；//一旦某个区段和为负，则从下一个位置累和if(b>sum)sum=b;}returnsum；}3.贪心算法求活动安排问题templatevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++)if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}4.快速排序templatevoidQuickSort(Typea[],intp,intr){15 if(pvoidperm(Typelist[],intk,intm){//产生[list[k:m]的所有排列if(k==m)//只剩下一个元素{for(inti=0;i<=m;i++)cout<n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;15 if(constraint(t)&&bound(t))backtrack(t+1);}}6.分治法所能解决的问题一般具有哪些特征分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。7.分支限界法设计算法有哪些步骤用分支限界法设计算法的步骤是：(1)针对所给问题，定义问题的解空间（对解进行编码）；分(2)确定易于搜索的解空间结构（按树或图组织解）；(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。8.常见的两种分支限界法的算法框架是什么常见的两种分支限界法的算法框架（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。9.回溯法中常见哪两类典型的解空间树？分析各自的使用场合及时间复杂度。回溯法中常见的两类典型的解空间树是子集树和排列树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间。当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。10.分支限界法的搜索策略是什么？分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。11.使用动态规划法求解TSP问题。各个城市间的距离可以用代价矩阵来表示。带权图的代价矩阵假设n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。15 填表方法：自底向上，逐步求值。利用前一步求出的值计算出后一步的值填入表中，每一步结束后选择最小值作为子问题的最优值，最后一步为原问题的最优解。完成以下表格的填写ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114第1步第2步第3步第4步最短路径为：0→1→2→3→0，最短路径长度为：10填表过程如下：第1步：填写第1列，d(1,{})=c10=5(1→0)；d(2,{})=c20=6(2→0)；d(3,{})=c30=3(3→0)第2步：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)第3步：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)第4步：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)六、算法设计题1.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。templateintBinarySearch(Typea[],constType&x,intn){//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1Intleft=0;intright=n-1;While(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}Return-1;}时间复杂性为O(logn)15 2.利用分治算法写出合并排序的算法，并分析其时间复杂度voidMergeSort(Typea[],intleft,intright){if(leftn)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(约束函数)Backtrack(t+1);}}4.最大团问题voidClique::Backtrack(inti)//计算最大团{if(i>n){//到达叶结点for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}//检查顶点i与当前团的连接intOK=1;for(intj=1;jbestn){//进入右子树x[i]=0;Backtrack(i+1);}15 }5.统计数字问题：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n(1≤n≤109)，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。输入数据、输出结果示例输入数据：11输出结果：数字:0123456789用到次数:1411111111voidcount(intn,inta[10]){inti,x,y;for(i=0;i<=9;i++)a[i]=0;for(i=1;i<=n;i++){x=i;while(x){y=x%10;a[y]++;x/=10;}}}6.顺序表存储表示如下：typedefstruct{RedTyper[MAXSIZE+1];//顺序表intlength;//顺序表长度}SqList;编写对顺序表L进行快速排序的算法。intPartition(SqList&L,intlow,inthigh)//算法10.6(b){//交换顺序表L中子表L.r[low..high]的记录,枢轴记录到位,并返回其所在位置,//此时在它之前(后)的记录均不大(小)于它.intpivotkey;L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录pivotkey=L.r[low].key;//枢轴记录关键字while(low=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(low1{pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二15 QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}voidQuickSort(SqList&L){//对顺序表L作快速排序QSort(L,1,L.length);}7.顺序表存储表示如下：typedefstruct{RedTyper[MAXSIZE+1];//顺序表intlength;//顺序表长度}SqList;编写对顺序表L进行2_路归并排序的算法。voidMerge(RedTypeSR[],RedTypeTR[],inti,intm,intn){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]intl,j,k;for(j=m+1,k=i;i<=m&&j<=n;++k)//将SR中记录由小到大地并入TRif(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];elseTR[k]=SR[j++];if(i<=m)for(l=i;l<=m;l++,k++)TR[k]=SR[l];//将剩余的SR[i..m]复制到TRif(j<=n)for(l=j;l<=n;l++,k++)TR[k]=SR[l];//将剩余的SR[j..n]复制到TR}voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt){//将SR[s..t]归并排序为TR1[s..t].intm;RedTypeTR2[MAXSIZE+1];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]MSort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]}}voidMergeSort(SqList&L){//对顺序表L作归并排序MSort(L.r,L.r,1,L.length);}15'