《计算机算法方案附分析》习题解析

《计算机算法设计方案附分析》习题及答案分析《计算机算法设计方案附分析》习题及答案分析PAGEPAGE10精选文档《计算机算法设计方案附分析》习题及答案分析《计算机算法设计与分析》习题及答案一．选择题1、二分搜寻算法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法2、以下不是动向规划算法基本步骤的是（A）。A、找出最优解的性质

B、结构最优解

C、算出最优解D、定义最优解3、最大效益优先是（

A）的一搜寻方式。A、分支界线法

B、动向规划法

C、贪婪法D、回溯法4.回溯法解旅游售货员问题时的解空间树是（A）。A、子集树B、摆列树C、深度优先生成树D、广度优先生成树5．以下算法中平常以自底向上的方式求解最优解的是（

B

）。A、备忘录法B、动向规划法C、贪婪法D、回溯法6、权衡一个算法利害的标准是（C）。A运转速度快B占用空间少C时间复杂度低D代码短7、以下不可以够使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C合并排序D0/1背包问题

8.实现循环赛日程表利用的算法是（

A）。A、分治策略B、动向规划法C、贪婪法D、回溯法9．下边不是分支界线法搜寻方式的是（

D

）。A、广度优先B、最小耗资优先C、最大效益优先D、深度优先10．以下算法中平常以深度优先方式系统搜寻问题解的是（

D

）。A、备忘录法B、动向规划法C、贪婪法D、回溯法11.备忘录方法是那种算法的变形。（B）A、分治法B、动向规划法C、贪婪法D、回溯法12．哈夫曼编码的贪婪算法所需的计算时间为（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（

B

）。A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（

B

）。A、分支界线法B、动向规划法C、贪婪法D、回溯法15．实现棋盘覆盖算法利用的算法是（

A）。A、分治法B、动向规划法C、贪婪法D、回溯法16.下边是贪婪算法的基本因素的是（

C

）。A、重叠子问题B、结构最优解C、贪婪选择性质D、定义最优解17.回溯法的效率不依靠于以下哪些因素（D）A.知足显拘束的值的个数B.计算拘束函数的时间C.计算限界函数的时间D.确立解空间的时间18.下边哪一种函数是回溯法中为防范无效搜寻采纳的策略（

B

）A．递归函数B.剪枝函数C。随机数函数D.搜寻函数19.（

D

）是贪婪算法与动向规划算法的共同点。A、重叠子问题B、结构最优解C、贪婪选择性质D、最优子结构性质20.矩阵连乘问题的算法可由（B）设计实现。A、分支界线算法B、动向规划算法C、贪婪算法D、回溯算法21.分支限界法解旅游售货员问题时，活结点表的组织形式是（A）。A、最小堆B、最大堆C、栈D、数组22、Strassen矩阵乘法是利用（

A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法23、使用分治法求解不需要知足的条件是（A）。A子问题必然是相同的B子问题不可以够重复C子问题的解可以合并D原问题和子问题使用相同的方法解24、下边问题（B）不可以使用贪婪法解决。A单源最短路径问题BN皇后问题C最小生成树问题D背包问题25、以下算法中不可以解决0/1背包问题的是（A）A贪婪法B动向规划C回溯法D分支限界法26、回溯法搜寻状态空间树是依据（C）的次序。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历27．实现合并排序利用的算法是（

A

）。A、分治策略B、动向规划法C、贪婪法D、回溯法28．以下是动向规划算法基本因素的是（

D

）。A、定义最优解B、结构最优解C、算出最优解D、子问题重叠性质29．以下算法中平常以自底向下的方式求解最优解的是（B）。A、分治法B、动向规划法C、贪婪法D、回溯法30．采纳广度优先策略搜寻的算法是（

A

）。A、分支界线法B、动向规划法C、贪婪法D、回溯法31、合并排序算法是利用（

A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法32、背包问题的贪婪算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）33．实现大整数的乘法是利用的算法（

C

）。A、贪婪法B、动向规划法C、分治策略D、回溯法34．0-1背包问题的回溯算法所需的计算时间为（

A

）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）35．采纳最大效益优先搜寻方式的算法是（

A

）。A、分支界线法B、动向规划法C、贪婪法D、回溯法36．贪婪算法与动向规划算法的主要差别是（

B

）。A、最优子结构B、贪婪选择性质C、结构最优解D、定义最优解37.实现最大子段和利用的算法是（

B）。A、分治策略B、动向规划法C、贪婪法D、回溯法38.优先行列式分支限界法采纳扩展结点的原则是（C）。A、先进先出B、后进先出C、结点的优先级D、随机39.背包问题的贪婪算法所需的计算时间为（

B

）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）40、广度优先是（

A

）的一搜寻方式。A、分支界线法

B、动向规划法

C、贪婪法

D、回溯法41.一个问题可用动向规划算法或贪婪算法求解的重点特点是问题的（B）。A、重叠子问题B、最优子结构性质C、贪婪选择性质D、定义最优解42．采纳贪婪算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43.以深度优先方式系统搜寻问题解的算法称为(D)。A、分支界线算法B、概率算法C、贪婪算法D、回溯算法44.实现最长公共子序列利用的算法是（

B

）。A、分治策略B、动向规划法C、贪婪法D、回溯法A.voidhanoi(intn,intA,intC,intB){if(n>0)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);}}Hanoi塔Hanoi塔B.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);}}C.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.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);}}46.动向规划算法的基本因素为（C）A.最优子结构性质与贪婪选择性质B．重叠子问题性质与贪婪选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用47.能采纳贪婪算法求最优解的问题，一般拥有的重要性质为：（A）A.最优子结构性质与贪婪选择性质B．重叠子问题性质与贪婪选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用48.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜寻解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先49.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜寻解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先50.程序块（A）是回溯法中遍历摆列树的算法框架程序。voidbacktrackvoidbacktrack(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]);}}voidbacktrack(intt){if(t>n)output(x);voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}C.voidbacktrack(intt)voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}voidbacktrackvoidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}51.常有的两种分支限界法为（D）A.广度优先分支限界法与深度优先分支限界法；B.行列式（FIFO）分支限界法与货仓式分支限界法；C.摆列树法与子集树法；D.行列式（FIFO）分支限界法与优先行列式分支限界法；二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法

用某种程序设计语言的详细实现。3、算法的“确立性”指的是构成算法的每条指令是清楚的，无歧义的。4.矩阵连乘问题的算法可由动向规划设计实现。5、算法是指解决问题的一种方法或一个过程。6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。7、问题的最优子结构性质是该问题可用动向规划算法或贪婪算法求解的重点特点。8、以深度优先方式系统搜寻问题解的算法称为回溯法。9、计算一个算法时间复杂度平常可以计算循环次数、基本操作的频次或计算步。10、解决0/1背包问题可以使用动向规划、回溯法和分支限界法，此中不需要排序的是动向规划，需要排序的是回溯法，分支限界法。11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：拘束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不一样样的种类，此中同时使用拘束条件和目标函数的界进行裁剪的是0/1背包问题，只使用拘束条件进行裁剪的是N皇后问题。12、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。13、矩阵连乘问题的算法可由动向规划设计实现。14.贪婪算法的基本因素是贪婪选择性质和最优子结构性质。15.动向规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，此后从这些子问题的解获得原问题的解。16.算法是由若干条指令构成的有穷序列，且要知足输入、输出、确立性和有限性四条性质。17、大整数乘积算法是用分治法来设计的。18、以广度优先或以最小耗资方式搜寻问题解的算法称为分支限界法。19、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。20.迅速排序算法是鉴于分治策略的一种排序算法。21.动向规划算法的两个基本因素是.最优子结构性质和重叠子问题性质。22.回溯法是一种既带有系统性又带有跳跃性的搜寻算法。23.分支限界法主要有行列式（FIFO）分支限界法和优先行列式分支限界法。24.分支限界法是一种既带有系统性又带有跳跃性的搜寻算法。25.回溯法搜寻解空间树时，常用的两种剪枝函数为拘束函数和限界函数。26.任何可用计算机求解的问题所需的时间都与其规模相关。27.迅速排序算法的性能取决于区分的对称性。28.所谓贪婪选择性质是指所求问题的整体最优解可以经过一系列局部最优的选择，即贪婪选择来达到。29.所谓最优子结构性质是指问题的最优解包括了其子问题的最优解。30.回溯法是指拥有限界函数的深度优先生成法。31.用回溯法解题的一个明显特点是在搜寻过程中动向产生问题的解空间。在任何时辰，算法只保留从根结点到目前扩展结点的路径。假如解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间平常为O(h(n))）。32.回溯法的算法框架依据问题的解空间一般分为子集树算法框架与摆列树算法框架。33.用回溯法解0/1背包问题时，该问题的解空间结构为子集树结构。34.用回溯法解批办理作业调动问题时，该问题的解空间结构为摆列树结构。35.旅游售货员问题的解空间树是摆列树。三、算法填空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.贪婪算法求活动安排问题template<classType>voidGreedySelector(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.迅速排序template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}5.回溯法解迷宫问题迷宫用二维数组储蓄，用'H'表示墙,'O'表示通道intx1,y1,success=0;//出口点voidMazePath(intx,inty){//递归求解:求迷宫maze从进口(x,y)到出口(x1,y1)的一条路径maze[x][y]='*';//路径置为*if((x==x1)&&(y==y1))success=1;//到出口则成功else{if(maze[x][y+1]=='O')MazePath(x,++y);//东邻方格是通路,向东试一试if((!success)&&(maze[x+1][y]=='O'))MazePath(++x,y);//不可以功且南邻方格是通路,向南试一试if((!success)&&(maze[x][y-1]=='O'))MazePath(x,--y);//不可以功且西邻方格是通路,向西试一试if((!success)&&(maze[x-1][y]=='O'))MazePath(--x,y);//不可以功且北邻方格是通路,向北试一试}if(!success)maze[x][y]='@';//死胡同置为@}四、算法设计题1.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的地点，假如未找到返回-1。写出二分搜寻的算法，并分析其时间复杂度。template<classType>intBinarySearch(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)2.利用分治算法写出合并排序的算法，并分析其时间复杂度voidMergeSort(Typea[],intleft,intright){if(left<right){//最罕有2个元素inti=(left+right)/2;//取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合并到数组bcopy(a,b,left,right);//复制回数组a}}算法在最坏状况下的时间复杂度为O(nlogn)。3.N皇后回溯法boolQueen::Place(intk){//检查x[k]地点能否合法for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)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;j<i;j++)if(x[j]&&a[i][j]==0)//i与j不相连{OK=0;break;}if(OK){//进入左子树x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//进入右子树x[i]=0;Backtrack(