《算法分析与设计》期末考试复习题库（含答案）

PAGEPAGE1《算法分析与设计》期末考试复习题库（含答案）一、单选题1.寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。A、以上皆可行。但不同方法，算法复杂度上界可能不同B、随机选择一个元素作划分基准C、用中位数作为划分基准D、取子序列的第一个元素作为划分基准答案：A2.猜数游戏:随机选择一个0~100内的整数，让你猜。猜对了，你赢了，游戏结束。如果没有猜对会告诉你猜大了，还是猜小了。当然，越早猜对越好。问最少需要猜多少次，就能保证一定能猜对?A、6B、7C、51D、101答案：B3.函数32n+10nlogn的渐进表达式是A、nlognB、32nC、10nlognD、2n答案：B4.含负权的最短路问题一般使用（）求解。A、贪心算法B、分治算法C、动态规划D、网络流算法答案：C5.下面不是动态规划算法的基本要素的是（）。A、独立子问题性质B、最优子结构性质C、重叠子问题性质D、无后效性答案：A6.求第n个斐波那契数的问题，根据动态规划的二要素分析，是可以用动态规划算法去解决的，下面是用备忘录方法(递归)解决的求第n个斐波那契数f[n的程序.这里N是一个较大的正整数常量，注意备忘录方法的设计要点(也就是，对于一个问题，首先判断是否该问题已被解决过，如果解决，不再重复。另外，解决过的问题，答案要记住)代码中【1】和【2】位置代码缺失，请从下列选项中选出合适的语句补齐算法。A、B、C、D、答案：C7.剪枝函数包括（）和约束函数A、启发式函数B、最优函数C、估计函数D、限界函数答案：D8.能采用贪心算法求最优解的问题，一般具有的重要性质为A、预排序与递归调用B、最优子结构性质与重叠子问题性质C、重叠子问题性质与贪心选择性质D、最优子结构性质与贪心选择性质答案：D9.下面哪些内容不是算法设计之前要完成的内容?()A、是求精确解还是近似解B、确定合适的数据结构C、使用何种计算机语言设计程序D、确定合适的算法策略答案：C10.1.在最长公共子序列问题中，我们用C[i,j]表示序列，X[1.i]和序列Y[1.j]的公共子序列长度。则递推式应为A、B、C、D、答案：B11.最优子结构性质是A、问题的最优解可通过性质相同的子问题的最优解合并而成B、子问题可同原问题性质不同，但是原问题的最优解可通过子问题的最优解合并而成C、问题的最优解可通过一步步局部最优的选择来获得。D、问题可以分解为性质相同的子问题答案：A12.装载问题的回溯算法所需的计算时间为O（）A、n2B、nC、n!D、2n答案：D13.符号三角形问题的回溯算法如下half=（n+1）*n/4;//(n+1)*n/2是偶数voidbacktrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}【】backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}现要求将红色代码去掉，保持算法功能不改变，需在【】添加下面哪段代码？A、if((count>half)||(t*(t+1)/2-count>half))B、if((count>half)||(t*(t-1)/2-count>half))C、if((count<=half)&&(t*(t-1)/2-count<=half))D、if((count<=half)&&(t*(t+1)/2-count<=half))答案：D14.快速排序算法在最坏情况下的时间复杂度为（）。A、O(n2)B、O(nlogn)C、O(n3)D、O(n)答案：A15.下面关于动态规划方法和备忘录方法，正确的是（）A、动态规划是自顶向下的，备忘录方法是自底向上的。B、备忘录算法需要计算所有子问题的最优解，动态规划算法不需要。C、动态规划算法和备忘录方法都需要配合记录子问题最优解的表格。D、动态规划算法和备忘录方法都可以用直接递归的方法计算。答案：C16.0-1背包向題中n=5,c=10,W［］={3,2,4,4,6｝，V［］=｛6,4,3,6,5｝，设m[i][j]是背包容量为j，可选物品为｛i,i+1.…，n}时背包问题最优值，则当可选物品只有最后三个物品时，背包的最大价值是（）A、10B、8C、9D、11答案：D17.旅行商问题的回溯算法所需的计算时间为O（）A、n！B、2^nC、nlognD、n^2答案：A18.（）肯定获得最优解A、随机算法B、回溯C、动态规划算法D、贪心算法答案：C19.背包问题的贪心算法所需的计算时间为A、O(nlogn)B、O(n)C、O(2n)D、(n2n)答案：A20.动态规划解题的步骤分为四步（1）分析最优解的结构（2）建立递归关系（3）计算最优值（4）构造最优解。关于这四个步骤的内容描述不正确的是哪个？A、构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造B、建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。C、分析最优解的结构：一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质D、计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。答案：D21.A、B、C、D、答案：C22.n=12皇后问题的三种不同的解决方案：回溯法、拉斯维加斯算法、拉斯维加斯算法+回溯法。对于给定的一个实例，(1)平均耗费时间最少的是那种方案，(2)平均耗费时间最多的是那种方案？A、(1)回溯法(2)拉斯维加斯+回溯法B、(1)拉斯维加斯+回溯(2)回溯法C、（1)回溯法(2)拉斯维加斯D、(1)拉斯维加斯(2)回溯法答案：B23.阅读该单元测试中关于0-1背包问题的优先队列分支限界算法代码，‏‎问左分支的剪枝条件是什么？右分支的剪枝条件是什么？从代码中找到命令行，使用原代码回答问题。A、左分支：wt<=c,右分支：up>bestpB、左分支：cp+p[i]>bestp,右分支：up>bestpC、左分支：cp+p[i]>bestp,右分支：wt<=cD、左分支：wt<=c,右分支：cp+p[i]>bestp答案：A24.对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文，如是回文，数返回true，否则返回false。比如:“abcba”“abba”是回文，“abc”则不是回文。算法中【】处缺少语句，请分析算法，从如下选项中选择语句补齐算法。A、(1)n==1(2)str[n](3)str+1(4)n-1B、(1)n==1(2)str[n-1](3)str+1(4)n-2C、(1)str[0]==str[n-1](2)str[n-1](3)str(4)n-1D、(1)str[0]==str[n-1](2)str[n](3)str(4)n-2答案：B25.实现循环赛日程表利用的算法是A、分治策略B、动态规划法C、回溯法D、贪心法答案：A26.分支限界法中，扩展出的孩子结点在入队时，存储该孩子结点的父结点的地址和左孩子标志。其目的是什么？A、为了计算最优值B、为了方便判定是否已搜索到达叶子层C、为了构造最优解D、为了确定其孩子结点在队列中的位置答案：C27.一致的p正确的偏y0的蒙特卡洛算法，下面解释不正确的是?A、当正确解是y0,而蒙特卡洛算法得到的解不是y0B、运行蒙特卡洛算法p次，至少有一次是正确的。C、一致是指蒙特卡洛算法对于一个实例，其正确解是唯一的。D、猜硬币的正反面问题，因为猜一次正确的概率是50%，所以不能使用蒙特卡洛算法解决。答案：B28.以下不可以使用分治法求解的是（）A、选择问题B、0/1背包问题C、棋盘覆盖问题D、归并排序答案：B29.采用最大效益优先搜索方式的算法是（）。A、贪心法B、动态规划法C、回溯法D、分支限界法答案：D30.下面关于分治策略的说法错误的是A、需要把问题划分成几个规模较小的不同子问题B、解决划分的子问题时递归使用原问题算法C、一般把问题划分成若干个规模较小的相互独立的子问题D、需要合并各子问题的解形成原问题的解答案：C31.下面哪个问题不是NPC问题A、最大团问题B、最小生成树问题C、旅行售货员问题D、子集和问题答案：B32.下面哪些不是递归算法的特点A、结构清晰B、可读性强C、容易用数学归纳法证明算法的正确性D、递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少答案：D33.一个问题，针对某个贪心策略，可通过找反例的方法快速判断出其使用贪心算法不能构造出最优解。下面是关于0-1背包问题，贪心策略是优先选择单位重量价值大的物品装入背包，有二个同学分别找到一个反例，证明贪心算法不能构造出0-1背包问题的最优解。（1）背包容量4，三个物品的重量和价值（wi，vi）:（2，4）,（2，3）,（2，2）（2）背包容量5，三个物品的重量和价值（wi，vi）:（1，2）,（2，3）,（4，4）‏分析判定哪个反例是对的，哪个反例是错的，从如下选项中找到你的答案。A、（1）对（2）错B、（1）错（2）错C、（1）错（2）对D、（1）对（2）对答案：A34.最长公共子序列算法利用的算法是A、分支界限法B、动态规划法C、贪心法D、回溯法答案：B35.有一个问题的蒙特卡洛算法，给定一个实例，已知运行一次其答案是错误的概率是1/8,现运行k次该算法，其答案一直不变，问该答案的正确率是？A、7/8B、1-(1/8)^kC、1-(7/8)^kD、(1/8)^k答案：B36.在队列式分支限界法中，叶子结点不加入队列。而在优先队列式分支限界法中，叶子结点通常要加入到优先队列中。有下列2个解释：‍（1）队列式分支限界法，活结点在队列中的顺序是按照搜索解空间树时扩展出该结点的先后顺序存放，每次从队首取出一个活结点成为新的扩展结点。扩展结点扩展出的儿子结点是叶子结点时，会将该叶子结点的值同当前最优值比较，检查更新最优值，叶子结点并不进入队列，等队列为空时，搜索结束，记录的当前最优值就是问题最优值。‍（2）优先队列式分支限界法中，当优先级的定义是限界函数时，扩展出的叶子结点进入队列，这种做法主要是为了让搜索过程提前结束。也就是当从优先队列中取出一个活结点是叶子结点时，意味着现在优先队列中剩余的所有活结点其优先级都不大于该叶子结点的优先级，叶子结点的优先级等于最优值，算法结束，无论优先队列是否为空。‍根据其正确与否，给出答案A、（1）错误，（2）错误B、（1）错误，（2）正确C、（1）正确，（2）正确D、（1）正确，（2）错误答案：C37.子集和问题：给定n个不同的正整数，已知其和大于c，问有多少个不同的其和等于c的子集？‌‎下面给出的算法，解空间树是子集树，且n个数已按从小到大有序存放于a数组中。‌‎voidbacktrack(inti)‌‎{‌‎if(sum==c)count++;‌‎elseif(i<=n)‌‎{‌‎if(sum+a[i]<=c)‌‎{sum+=a[i];‌‎backtrack(i+1);‌‎【】‌‎}‌‎}‌‎}‌‎‌‎请将【】位置缺失的代码补齐，从下面选项中找到答案。A、backtrack(i+1);sum-=a[i];B、sum-=a[i];C、sum-=a[i];backtrack(i+1);D、backtrack(i+1);答案：C38.某中学有一个开水房，只有一个供热水龙头，课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案，也就是同学们按照他给出的排队方法，可以使同学们的平均等待时间最短。你分析一下，给出这个排队的方法，假定有n个人，第i个同学打水所需要的时间为ti，并给出平均等待时间的计算公式。（注意：第i个同学的等待时间包含前i-1个的打水时间和+自己打水的时间ti）A、按照打水时间从小到大排队，假定排队后第i个人的打水时间是ti,平均等待时间T=∑(n-i+1)ti/n1<=i<=nB、按照打水时间从小到大排队，平均等待时间T=∑ti/n1<=i<=nC、按照打水时间从大到小排队，假定排队后第i个人的打水时间是ti,平均等待时间T=∑(n-i+1)ti/n1<=i<=nD、按照打水时间从大到小排队，平均等待时间T=∑ti/n1<=i<=n答案：A39.下面是优先队列式分支限界算法解0-1背包问题的部分主代码，分析代码将【】内的代码补齐。Templete<classTypew,classTypep>Typepknap<Typew,Typep>::MaxKnapsack(){//优先队列分支限界法，返回最大价值，最优解bestxH=newMaxHeap<HeapNode<Typep,Typew>>(1000);//定义最大堆的容量为1000bestx=newint[n+1];inti=1;E=0;cw=cp=0;Typepbestp=0;Typepup=Bound(1）；while(【1】){Typewwt=cw+w[i];if(wt<=c){if(cp+p[i]>bestp)【2】；AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(up>bestp)AddLiveNode(up,cp,cw,false,i+1);//从优先队列中取下一个扩展节点HeapNode<Typep,Typew>N;H->DeleteMax(N);E=NNaNr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//构造最优解for（intj=n;j>0;j--）{bestx[j]=E->lchild;E=E->parent;}returncp;}A、【1】i<n+1,【2】besp=cp+p[i]B、【1】i!=n+1,【2】cw=cw+w[i]C、【1】i<n,【2】besp=cp+p[i]D、【1】i!=n,【2】cw=cw+w[i]答案：A40.使用快速排序方法对数组a［］=｛11,34,6,2,21,7,15,9,10,13｝升序排序，partition函数被调用（）次完成排序。A、5B、6C、7D、8答案：B41.在商品个数为n、背包容量为C的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为（）A、O（n2），O（）B、O(2n)，O(n2)C、O（n2），O(n·C)D、O(2n)，O(n·C)答案：C42.游艇租赁问题：长江游艇俱乐部在长江上设置了n个游艇出租站1~n，游客可在这些游艇出租站租用游艇，并在下游的任何出租站归还游艇，限制只能从上游往下游行进，游艇出租站i到出租站j直达的租金为r(i,j)（1<=i<j<=n），计算从游艇出租站1到出租站n的最小费用。该问题可有二种最优解的结构形式，如图所示：如下描述中错误的是哪个？A、图2方案的算法设计思路：设定二重循环：循环变量i（问题的终点站编号），循环变量k（断点位置控制），去计算问题的最优值.时间复杂性为O(）B、图1是将从i站到j站最小费用问题划分为2个子问题i到k和k到j的最小费用和，且i<k<j，这些不同方式中的最小值还要同r(i,j)比较，最小者即为cost(i,j)C、图2是将从1站到i站的最小费用问题划分为2个子问题即从第1站到第k站的最小费用问题和从k站到i站的最小费用问题D、图1方案的算法设计思路：设定三重循环：循环变量r（规模控制），循环遍历i（规模为r的问题个数控制，同时也是问题的首编号），循环变量k（断点位置控制），去计算问题的最优值,时间复杂性为O（）答案：C43.下面描述不正确的是？A、当解空间树是子集树时，约束函数对0分支剪枝，限界函数对1分支剪枝。B、剪枝函数有二种，分别是约束函数和限界函数C、对解空间树是n叉树（或排列树）来说，回溯法搜索时对每个分支使用的的剪枝条件（函数）是完全相同的。D、解空间树的分类中，尽管子集树的每个非叶子结点都有二个分支，但是不能把它称为n叉树。答案：A44.在算法设计与分析过程中，有算法设计，算法的正确性证明，算法的复杂性分析,程序设计等几个重要步骤，下面哪种顺序是正确的?A、算法的正确性证明->算法设计->算法的复杂性分析->程序设计B、算法的正确性证明->算法的复杂性分析->算法设计->程序设计C、算法设计->算法的正确性证明->算法的复杂性分析->程序设计D、算法设计->算法的复杂性分析->算法的正确性证明->程序设计答案：C45.0-1背包问题：现有一背包容量c=5，n=4。4个物品分别为：(Wi,Vi)|(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i个物品装背包容量为j时的最优值。其中第四行的数据没有填写，分析问题，将第四行的数据从如下选项中找出。A、037101315B、037101013C、03771013D、0336815答案：B46.下面哪个算法在最坏情况下的时间复杂性最低A、归并排序B、插入排序C、快速排序D、冒泡排序答案：A47.最长公共子序列问题：现有两个字符序列X和Y,下面c矩阵和b矩阵是算法填写出的信息表。c[i][j]是X序列的前i个字符和Y序列的前j个字符的最长公共子序列的长度，b[i][j]是辅助信息表。已知X=”ABC”‌根据表格内容，回答X和Y的最长公共子序列长度及最长公共子序列包含的符号A、长度1“C”B、长度1“A”C、长度2“AB”D、长度2“AC”答案：D48.给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是A、thmgorthmB、glorhthmorthmC、orthmglorhthmD、gorthmthm答案：D49.5个不同元素组成二叉搜索树可以画出多少种不同形式A、140B、100C、80D、120答案：D50.回溯法的效率不依赖于以下哪一个因素（）A、产生x［KJ的时间；B、满足显约束的x［k］值的个数；C、问题的解空间的形式；D、计算上界函数bound的时间答案：C51.在队列式分支限界法解决装载问题时，为什么在其改进算法中，每次进入左分支都要检查更新bestw，而不是等搜索到达叶子结点时才去更新bestw，其目的是什么？A、为了方便构造最优解B、为了计算最优值C、为了及早使右（0）分支剪枝函数生效。D、为了及早使左（1）分支剪枝函数生效答案：C52.下面是求最长公共子序列长度和构造最优解的算法。【】中的语句缺失，请从如下选项中找到正确的答案补齐算法。A、(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)B、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)C、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)D、(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)答案：A53.将一个递归算法改造为非递归算法常用的数据结构是?A、顺序表B、链表C、栈D、队列答案：C54.下列随机算法中运行时有时候成功有时候失败的是A、蒙特卡罗算法B、数値概率算法C、舍伍德算法D、拉斯维加斯算法答案：D55.衡量一个算法好坏的标准是（）。A、时间复杂度低B、运行速度快C、代码短D、占用空间少答案：A56.n皇后问题是可用回溯法解决的问题。下面描述不正确的是？A、算法搜索至叶子结点时，就找到了一种新的皇后安排方案，算法可找到所有可行的方案。B、当其解空间树是n叉树时，剪枝函数是任一列或任一（正反）对角线只能安排一个皇后。C、两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树D、当其解空间树是排列树时，剪枝函数是任一（正反）对角线只能安排一个皇后。答案：C57.0-1背包问题的回溯算法，下面的解释不正确的是A、当搜索至叶子结点时，一定是发现了到目前为止最好的解B、左(1)分支的剪枝：当选择装入背包的物品重量之和超过背包容量时就剪枝。C、右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）>当前最优值bestp,就剪枝.D、解空间树是子集树答案：C58.分治法解决问题分为三步走，即分、治、合。下面列出了几种操作，请按分、治、合顺序选择正确的表述。(1)将各个子问题的解合并为原问题的解(2)将问题分解为各自独立的多个子问题，(3)将多个子问题合并为原问题。(4)求各个子问题的解，(5)将问题分解为可重复的多个子问题。A、(5)(4)(1)B、(2)(4)(1)C、(2)(1)(3)D、(5)(1)(3)答案：B59.下面不是分支界限法搜索方式的是A、最大效益优先B、深度优先C、最小耗费优先D、广度优先答案：B60.回溯法解旅行售货员问题时的解空间树是（）A、深度优先生成树B、广度优先生成树C、子集树D、排列树答案：D61.已知斐波那契数列中第n个斐波那契数F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第n个斐波那契数，从下面选项中选取答案。A、能，因为它满足分治法的四个适应条件B、能，因为它可以用分、治、合三个步骤完成计算C、不能，因为它不满足分治法的第四个适应条件(子问题是相互独立的，也就是没有重复子问题)D、不能，因为它不可以用分、治、合三个步骤完成计算答案：C62.动态规划算法的基本要素为（）A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用答案：C63.有5个物品，重量数组是w[]={3,5,2,6,4}，背包容量10，每个物品不可分割，背包最多装多少个物品？A、3B、5C、2D、4答案：A64.哈夫曼编码树是用贪心算法解决的典型问题，分析该算法，回答如下问题，假定有n（n>1)个字符生成的编码树，问编码树中的结点总数是多少？可能的最长的字符编码是多少位？A、2n-1个结点n-1位编码B、2n个结点n-1编码C、2n个结点，n位编码D、2n-1个结点n位编码答案：A65.实现合并排序利用的算法是（）A、回溯法B、动态规划法C、分治策略D、贪心法答案：C66.二分搜索算法是利用（）实现的算法A、贪心法B、动态规划法C、回溯法D、分支策略答案：D67.给定n个可能含有重复的元素存放于x[1:n]，输出去掉重复的全排列，这里swap是实现两个变量值的交换，下面是算法描述‏‌注意：红色代码部分【1】【2】【3】位置有代码缺失。‏‌‏‌voidbacktrack(intt)‏‌{‏‌if(t>n){‏‌for(inti=1;i<=n;i++)‏‌printf("%d",x[i]);‏‌printf("\n");‏‌}‏‌else{‏‌for(inti=t;i<=n;i++){‏‌intok=1;‏‌for(intj=【1】;j<【2】;j++)‏‌if(x[j]==x[i])｛【3】;break；｝‏‌if(ok)‏‌{‏‌swap(x[t],x[i]);‏‌backtrack(t+1);‏‌swap(x[t],x[i]);‏‌}‏‌}‏‌‏‌}‏‌}‏‏‌上面的算法中，红色代码部分【1】【2】【3】位置代码缺失，请从如下选项中找到合适的代码。A、【1】t，【2】i，【3】ok=0B、【1】t，【2】i，【3】ok=1C、【1】i，【2】t，【3】ok=1D、【1】i，【2】t，【3】ok=0答案：A68.下图中A~F顶点分别代表6个村庄，图中的边代表村庄之间的距离，为了满足这六个村庄相互通信的需要（任意两个村庄有线路可达），需要架设通信线路，这里要求代价最小化（即线路总长度最小），请你分析问题找到代价最小的方案，并计算出线路总长度，从如下选项中找出答案。A、线路总长度21B、线路总长度22C、线路总长度20D、线路总长度23答案：A69.凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？A、右图正确，9种B、左图正确，14种C、右图正确，14种D、左图正确，9种答案：B70.当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为（）A、子集树B、排列树C、二叉树D、平衡树答案：A71.符号三角形问题，其解空间树是哪种？A、不规则树B、子集树C、n叉树（这里n=2）D、排列树答案：C72.哈夫曼编码树算法中用优先队列（堆）存储生成的结点，n个字符的哈夫曼编码树算法时间复杂性为A、O(nlogn)B、O(n2)C、O(n2n)D、O(n)答案：A73.分支限界法解0/1背包问题时，优先级队列的组织形式是（）A、循环队列B、栈C、小根堆D、大根堆答案：D74.分支限界法与回溯法的不同点体现在哪些方面？（1）求解目标不同，分支限界法可求最优解或满足条件的一个解，而回溯法可求最优解或满足条件的所有解‌（2）搜索方式不同，回溯法是以深度优先状态生成树法搜索解空间树，分支限界法则以广度优先或最小耗费（最大效益）优先的状态生成树法搜索解空间树。‌（3）同一个问题在使用回溯法或分支限界法时，该问题的解空间树的结构不同‌（4）回溯法与分支限界法，构造最优解的方式不同。‌从上述选项中找出答案。A、（1）（2）（3）B、（1）（3）（4）C、（1）（2）（4）D、（2）（3）（4）答案：C75.X=1a,b.c,a,d,c,a,dy=（b.b,a,d,c,a.b的最长公类子厚列的长展是（）A、3B、4C、5D、6答案：C76.下面关于NP问题说法正确的是A、NP类问题包含在P类问题中B、P类问题包含在NP类问题中C、NP问题都是不可能解决的问题D、NP完全问题是P类问题的子集答案：B77.有这样一种算法，运行一次一定能找到问题的解，有时不知其是否正确，可以确定的是该解高概率（大于50%）是正确的。这种算法是？A、蒙特卡洛算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法答案：A78.FIFO是（）的搜索方式。A、分支限界B、动态规划C、回溯算法D、贪心算法答案：A判断题1.回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。（）A、正确B、错误答案：A2.在队列式分支限界法解决装载问题时，在队列中加入一个-1标志，该标志所起的作用是表示其后的活结点在解空间树中的层数比-1之前的活结点更深一层，或者说是同层活结点的结束标志。A、正确B、错误答案：A3.改进子问题合并的时间复杂度可以减少分治算法的时间。（）A、正确B、错误答案：A4.Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。（）A、正确B、错误答案：A5.递归程序代码简短，结构清晰，易读性强，相比解决同一问题的非递归程序，递归程序运行时间短。A、正确B、错误答案：B6.一个人正站在门口，让你猜他（她）是否要出门，该问题是不可判定问题，该观点是否正确？A、正确B、错误答案：A7.回溯法使用约束函数剪去得不到最优解的子树以避免无效搜索。（）A、正确B、错误答案：A8.优先队列式分支限界法按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。（）A、正确B、错误答案：A9.如果一个最优化问题具备贪心选绎性质和最优子结构性质，则可以用贪心算法找到问题所有最优解。（）A、正确B、错误答案：B10.研究NPC问题的意义，一旦一个NPC问题找到了多项式时间复杂性的确定性算法，那么所有的NPC问题都找到了多项式时间复杂性的确定性算法。A、正确B、错误答案：A11.回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。（）A、正确B、错误答案：B12.回溯法中，剪枝函数能够剪掉的分支越多，算法效率就越高。因此，我们在设计回溯法时，就要设计剪枝函数能够剪掉尽量多的分支。A、正确B、错误答案：B13.备忘录方法是自顶向下，动态规划方法是自底向上。（）A、正确B、错误答案：A14.把大规模的问题分解成相同子问题，目的是为了在解决子问题时递归调用原问题的算法。（）A、正确B、错误答案：A15.0-1背包问题和背包问题的区别在于物品是否能够分割，他们都可以使用动态规划方法求解。（）A、正确B、错误答案：B16.自然语言、伪代码都可以描述算法，而流程图不能描述算法A、正确B、错误答案：B17.贪心算法是以自底向上的方式构造问题的最优解A、正确B、错误答案：B18.贪心和递推算法是线性解决问题，动态规划则是全面分阶段地解决问题。（）A、正确B、错误答案：A19.回溯法不适用于解一些组合数相当大的问题。（）A、正确B、错误答案：A20.回溯法在0-1背包问题的解空间树的每个内结点都要同时检直约束函数和限界函数。（）A、正确B、错误答案：B21.分支界限法采用深度优先策略搜索。（）A、正确B、错误答案：B22.一个问题，可能有多个最优解，但是使用贪心算法最多只能找到一个最优解。A、正确B、错误答案：A23.分治法解决问题时，平衡子问题思想是指:当问题划分出的子问题规模基本一致时，算法计算效率高A、正确B、错误答案：A24.支限限界法不能解决0/1背包问题。（）A、正确B、错误答案：B25.使用动态规划算法和贪心算法的共同点是，问题都必须具备最优子结构性质。（）A、正确B、错误答案：A26.学习主定理和递归树等求解递归方程方法，主要目的是解决求递归算法的时间复杂性问题A、正确B、错误答案：A27.计算机中的随机数是伪随机的，因为它是具有一定规律的，是按公式计算出来的。该说法正确吗？A、正确B、错误答案：A28.解决旅行商问题，采用的是优先队列式分支限界法。（）A、正确B、错误答案：A29.素数测试问题的蒙特卡洛算法，n是一个待判定正整数。当n是素数时，有时会被判定为非素数。该说法正确吗?‍A、正确B、错误答案：B30.解决同一个问题的算法策略可能有多个，使用不同算法策略设计的算法，其算法时间复杂性可能有显著差异。A、正确B、错误答案：A31.队列式分支限界法按照队列中结点的优先级选取优先级最高的一个结点成为当前扩展结点。（）A、正确B、错误答案：A32.分支限界按广度优先的原则进行搜索，每一活结点只有一次机会成为扩展结点。（）A、正确B、错误答案：A33.教材例题：多机调度问题，是用贪心算法求最优解的一个例子，贪心策略是每次从剩余任务中选择一个花费时间最长的任务，安排在占用时间最少的机器上。A、正确B、错误答案：B34.剪枝函数设计的越好，剩下的结点数越少，回溯算法效率越高。（）A、正确B、错误答案：A35.回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)),h(n)是解空间树的深度。A、正确B、错误答案：B36.一个NPC问题，首先是NP问题，另外所有的其他NP问题都能在多项式时间复杂性规约为该问题A、正确B、错误答案：A37.分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。（）A、正确B、错误答案：A填空题1.操场上摆放一行共4堆石头，从左到右方向编号为1~4，各堆石子的数目分别为7,10,3,5，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过5次合并，最终合并为一堆。计算这6堆石子合并为一堆的最小得分答案：502.使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（），只使用约束条件进行裁剪的是（）。答案：0/1背包问题|N皇后问题3.回溯法的算法框架按照问题的解空间一般分为[填空1]算法框架与[填空2]算法框架。答案：子集树|排列树4.答案：n5.下面是优先队列式分支限界算法解装载问题（n个集装箱装船）的部分代码，分析下面代码答案：r[i-1]6.算法分析中，记号O表示_______，记号Ω表示_______。答案：渐进上界|渐进下界7.快速排序算法是基于的一种排序算法答案：分治策略解析：分治策略;分治;分治法;分治算法8.下面是优先队列式分支限界算法解装载问题（n个集装箱装船）的部分代码，分析下面代码答案：n+1;1+n9.答案：310.答案：A|33|1|2|3|511.答案：A|1|4|7|812.对如下所示连通无向图G=<V,E,W>，其最小生成树的权重为______________-。答案：2313.根据题中数据构造哈夫曼树如下图所示。由此可以得出相应的最优编码a___________，b___________,c___________,d___________,e___________,f___________的一组最优的编码：答案：01|0000|00010|00011|1|00114.分支限界法主要有（）分支限界法和（）分支限界法。答案：队列式|优先队列式15.下面是一个布线问题,S表示布线的起点，O表示布线的终点，假定布线只能垂直、或水平布线，从一个点按照上、下、左、右的优先顺序可往四个方向布线，“#"是障碍不能通过。已知从一个位置向其上、下、左、右四个相邻位置布线的线路长度为1。使用队列式分支限界法解决该问题，问从S到O的最短布线长度？答案：816.整数因子分解问题：大于1的正整数n可以分解为n=x1*x2*…xm。如n=12时有如下形式12=1212=6*212=4*312=3*412=3*2*212=2*612=2*3*212=2*2*38种形式求正整数n共有多少种分解形式，函数p(intn)返回值为问题的答案，代码如下：‍代码中【1】【2】处代码缺失，请补齐【1】的代码答案：n==1;1==n17.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合）：（格式：以英文输入法逗号分割，如：1,2,3,4）答案：1,4,8,1118.答案：A|A|C|B19.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是填空1，解空间树中每个内结点的孩子数是填空2。答案：m^n|m20.答案：n^2|n^221.在0-1背包问题中，若背包容量为20,5个物品的体积分别为c=[15,10,2,5,8]，价格分别为p=[16,10,6,7,9]。则该背包能容纳物品的最大总价格为___填空1____答案：2522.答案：A|V1V5V3V6V7|223.Prim算法利用策略求解最小生成树问题，其时间