MOOC 算法设计与分析-青岛大学 中国大学慕课答案

MOOC算法设计与分析-青岛大学中国大学慕课答案第一章单元测试1、问题：下面列出了算法的四个性质，哪个性质是程序不一定具备的？选项：A、有输入B、有输出C、确定性D、有穷性正确答案:【有穷性】2、问题：在算法设计与分析过程中，有算法设计，算法的正确性证明，算法的复杂性分析,程序设计等几个重要步骤，下面哪种顺序是正确的？选项：A、算法的正确性证明-算法设计-算法的复杂性分析-程序设计B、算法的正确性证明-算法的复杂性分析-算法设计-程序设计C、算法设计-算法的正确性证明-算法的复杂性分析-程序设计D、算法设计-算法的复杂性分析-算法的正确性证明-程序设计正确答案:【算法设计-算法的正确性证明-算法的复杂性分析-程序设计】3、问题：下面哪些内容不是算法设计之前要完成的内容?选项：A、是求精确解还是近似解B、确定合适的数据结构C、确定合适的算法策略D、使用何种计算机语言设计程序正确答案:【使用何种计算机语言设计程序】4、问题：下面是快速幂算法求的代码，这里n≥0,a是实数。对该算法的时间复杂性描述不准确的是哪个？douleexp2(doublea,intn){inti;doubleb,s=1.0；i=n；b=a;while（i0）{if(i%2)s*=b；i/=2;b*=b;}returns;}选项：A、B、C、D、正确答案:【】5、问题：下面哪个算法在最坏情况下的时间复杂性最低选项：A、归并排序B、插入排序C、快速排序D、冒泡排序正确答案:【归并排序】6、问题：有时间复杂性选项：,时间复杂性从低到高的顺序是？A、B、C、D、正确答案:【】7、问题：有一个算法，它的时间复杂性T(n)的递归定义如下，问T（n）是?选项：A、B、C、D、正确答案:【】8、问题：有一个算法，它的时间复杂性T(n)的递归定义如下，问T（n）是？选项：A、B、C、D、正确答案:【】9、问题：有一个算法，它的时间复杂性T(n)的递归定义如下，问T（n）是？选项：A、B、C、D、正确答案:【】10、问题：有一个算法，它的时间复杂性T(n)的递归定义如下，问T（n）是?选项：A、B、C、D、正确答案:【】11、问题：A公司处理器速度是B公司的100倍。对于复杂性为O()的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时内能处理的问题规模是多少？选项：A、nB、10nC、100nD、正确答案:【10n】12、问题：关于算法的正确性，下面哪些说法是正确的？选项：A、若算法是正确的，则算法一定能结束（运行时间是有限的）B、若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。C、对于问题的一个实例，如果算法能够获得正确的结果，就证明算法是正确的。D、对于问题的一个实例，如果算法不能获得正确的结果，就证明算法是不正确的。正确答案:【若算法是正确的，则算法一定能结束（运行时间是有限的）#若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。#对于问题的一个实例，如果算法不能获得正确的结果，就证明算法是不正确的。】13、问题：解决同一个问题的算法策略可能有多个，使用不同算法策略设计的算法，其算法时间复杂性可能有显著差异。选项：A、正确B、错误正确答案:【正确】14、问题：学习主定理和递归树等求解递归方程方法，主要目的是解决求递归算法的时间复杂性问题选项：A、正确B、错误正确答案:【正确】15、问题：自然语言、伪代码都可以描述算法，而流程图不能描述算法选项：A、正确B、错误正确答案:【错误】第二章单元测试1、问题：分治法解决问题分为三步走，即分、治、合。下面列出了几种操作，请按分、治、合顺序选择正确的表述。（1）将各个子问题的解合并为原问题的解，（2）将问题分解为各自独立的多个子问题，（3）将多个子问题合并为原问题。（4）求各个子问题的解，（5）将问题分解为可重复的多个子问题。选项：A、(5)(4)(1)B、(2)(4)(1)C、(2)(1)(3)D、(5)(1)(3)正确答案:【(2)(4)(1)】2、问题：分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程，然后解此方程可得T(n)的结果。T(n)的递归定义如下：关于该定义中k，n/m,f(n)的解释准确的是选项：A、k是常系数；n/m是规模为n的问题分为m个子问题；f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和。B、k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和C、k是子问题个数，n/m是子问题的规模，f(n)是规模为n的问题分解为子问题的时间复杂性D、k是常系数，n/m是规模为n的问题分为m个子问题，f(n)是将子问题的解合并为问题的解的时间复杂性。正确答案:【k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和】3、问题：已知斐波那契数列中第n个斐波那契数F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第n个斐波那契数，从下面选项中选取答案。选项：A、能，因为它满足分治法的四个适应条件B、能，因为它可以用分、治、合三个步骤完成计算C、不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）D、不能，因为它不可以用分、治、合三个步骤完成计算正确答案:【不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）】4、问题：快速幂算法求，其时间复杂性为O(logn)，a是实数，n为非负整数。下面是一同学用c语言编写的求的代码doubleexp2(doublea,intn){if(a==0)return0;if(n==0)return1;else{if(n%2)returna*exp2(a,n/2)*exp2(a,n/2);elsereturnexp2(a,n/2)*exp2(a,n/2);}}对该同学的算法评价正确的是？选项：A、运行结果正确，时间复杂性为O(logn)B、运行结果错误，时间复杂性为O(n)C、运行结果正确，时间复杂性为O(n)D、运行结果错误，时间复杂性为O(logn)正确答案:【运行结果正确，时间复杂性为O(n)】5、问题：快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(),而归并排序的时间复杂性为O(nlogn),究其原因，下面的解释你认为哪个正确？选项：A、这是因为归并排序把问题划分为子问题时的时间复杂性是O(1)，而快速排序划分为子问题是使用partition()函数，其时间复杂性是O（n）。B、因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)C、归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和D、因为快速排序将问题划分为子问题的个数比归并排序要多正确答案:【因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)】6、问题：猜数游戏：随机选择一个0~100内的整数，让你猜。猜对了，你赢了，游戏结束。如果没有猜对，会告诉你猜大了，还是猜小了。当然，越早猜对越好。问最少需要猜多少次，就能保证一定能猜对？选项：A、6B、7C、51D、101正确答案:【7】7、问题：对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文，如是回文，函数返回true，否则返回false。比如：“abcba”、“abba”是回文，“abc”则不是回文。boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}算法中【】处缺少语句，请分析算法，从如下选项中选择语句补齐算法。选项：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正确答案:【(1)n==1(2)str[n-1](3)str+1(4)n-2】8、问题：对于一个采用字符数组存放的长度为n的字符串str，下面是判断是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”则不是回文boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}请补齐代码后分析算法的时间复杂性，回答如下问题选项：A、该算法时间复杂性的递归定义为：T(n)=T(n-1)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)B、该算法时间复杂性的递归定义为：T(n)=T(n-1)+1,ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(n)C、该算法时间复杂性的递归定义为：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)D、该算法时间复杂性的递归定义为：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(n)正确答案:【该算法时间复杂性的递归定义为：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)】9、问题：棋盘nxn（）的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治算法。关于该算法时间复杂性描述不正确的是选项：A、T(n)=4T(n/2)+O(1),ifn1;T(n)=O(1),ifn==1。B、T(k)=4T(k-1)+O(1),ifk0;T(k)=O(1),ifk==0。这里n=2^kC、T(n)=O(n^4)D、T(k)=O(4^k)正确答案:【T(n)=O(n^4)】10、问题：棋盘8X8的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治策略。约定解决四个子问题的顺序为右下，左下,左上，右上。用数字标识法填写覆盖方案（如3个相连的整数值i构成的L块，代表是第i个被放入棋盘中的L型块）。使用分治策略的算法有三种形式：1使用递归算法实现，2使用队列存取分解出的子棋盘的非递归算法3.使用栈存取分解出的子棋盘的非递归算法。下图中有三个覆盖图案（只标出了前7块L型模块位置），问自左至右分别是哪种算法实现的覆盖方案？选项：A、栈算法，队列算法，递归算法B、队列算法，栈算法，递归算法C、递归算法，队列算法，栈算法D、递归算法，栈算法，队列算法正确答案:【递归算法，队列算法，栈算法】11、问题：下面哪些不是递归算法的特点选项：A、结构清晰B、可读性强C、容易用数学归纳法证明算法的正确性D、递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少正确答案:【递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少】12、问题：给定n个正整数组成的无序序列，要找到该序列的中位数，解决该问题的最优算法的时间复杂性是？选项：A、O（logn）B、O（n）C、O（nlogn）D、正确答案:【O（n）】13、问题：将一个递归算法改造为非递归算法，常用的数据结构是？选项：A、顺序表B、链表C、栈D、队列正确答案:【栈】14、问题：分治法解决问题时，平衡子问题思想是指：当问题划分出的子问题规模基本一致时，算法计算效率高选项：A、正确B、错误正确答案:【正确】15、问题：递归程序代码简短，结构清晰，易读性强，相比解决同一问题的非递归程序，递归程序运行时间短。选项：A、正确B、错误正确答案:【错误】第三单元测试1、问题：求第n个斐波那契数的问题，根据动态规划的二要素分析，是可以用动态规划算法去解决的，下面是用备忘录方法（递归）解决的求第n个斐波那契数f[n]的程序.这里N是一个较大的正整数常量，注意备忘录方法的设计要点（也就是，对于一个问题，首先判断是否该问题已被解决过，如果解决，不再重复。另外，解决过的问题，答案要记住）intf[N]={0,1,1};intfib(intn){if(【1】)returnf[n];elsereturn【2】;}代码中【1】和【2】位置代码缺失，请从下列选项中选出合适的语句补齐算法。选项：A、【1】n3【2】fib(n-1)+fib(n-2)B、【1】f[n]0【2】fib(n-1)+fib(n-2)C、【1】f[n]0【2】f[n]=fib(n-1)+fib(n-2)D、【1】n3【2】f[n]=fib(n-1)+fib(n-2)正确答案:【【1】f[n]0【2】f[n]=fib(n-1)+fib(n-2)】2、问题：动态规划解题的步骤分为四步（1）分析最优解的结构（2）建立递归关系（3）计算最优值（4）构造最优解。关于这四个步骤的内容描述不正确的是哪个？选项：A、分析最优解的结构：一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质B、建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。C、计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。D、构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造正确答案:【计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。】3、问题：矩阵连乘问题：下图是动态规划算法计算6个矩阵A1A2A3A4A5A6连乘所生成的信息表.（a）表描述了计算顺序，（b）表是m[i][j]的最优值表，（c）表是辅助信息表（断开位置）。分析表格，给出A2A3A4A5A6五个矩阵连乘所需要的最少数乘次数，并用加括号的方法表示出其乘法顺序。从如下选项中选择。选项：A、15125,(A2(A3A4))(A5A6)B、10500,(A2(A3A4))(A5A6)C、15125,(A2A3)((A4A5)A6)D、10500,(A2A3)((A4A5)A6)正确答案:【10500,(A2A3)((A4A5)A6)】4、问题：凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？选项：A、右图正确，9种B、左图正确，9种C、左图正确，4种D、右图正确，4种正确答案:【左图正确，4种】5、问题：游艇租赁问题：长江游艇俱乐部在长江上设置了n个游艇出租站1~n，游客可在这些游艇出租站租用游艇，并在下游的任何出租站归还游艇，限制只能从上游往下游行进，游艇出租站i到出租站j直达的租金为r(i,j)（1=ij=n），计算从游艇出租站1到出租站n的最小费用。该问题可有二种最优解的结构形式，如图所示：如下描述中错误的是哪个？选项：A、图2方案的算法设计思路：设定二重循环：循环变量i（问题的终点站编号），循环变量k（断点位置控制），去计算问题的最优值.时间复杂性为O(）B、图1是将从i站到j站最小费用问题划分为2个子问题i到k和k到j的最小费用和，且ikj，这些不同方式中的最小值还要同r(i,j)比较，最小者即为cost(i,j)C、图2是将从1站到i站的最小费用问题划分为2个子问题即从第1站到第k站的最小费用问题和从k站到i站的最小费用问题。D、图1方案的算法设计思路：设定三重循环：循环变量r（规模控制），循环遍历i（规模为r的问题个数控制，同时也是问题的首编号），循环变量k（断点位置控制），去计算问题的最优值,时间复杂性为O（）正确答案:【图2是将从1站到i站的最小费用问题划分为2个子问题即从第1站到第k站的最小费用问题和从k站到i站的最小费用问题。】6、问题：0-1背包问题：现有一背包容量c=5，n=4。4个物品分别为：(Wi,Vi)|(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i个物品装背包容量为j时的最优值。其中第四行的数据没有填写，分析问题，将第四行的数据从如下选项中找出。选项：A、03771013B、0336815C、037101315D、037101013正确答案:【037101013】7、问题：最长公共子序列问题：现有两个字符序列X和Y,下面c矩阵和b矩阵是算法填写出的信息表。c[i][j]是X序列的前i个字符和Y序列的前j个字符的最长公共子序列的长度，b[i][j]是辅助信息表。已知X=”ABC”根据表格内容，回答X和Y的最长公共子序列长度及最长公共子序列包含的符号选项：A、长度2“AB”B、长度1“C”C、长度2“AC”D、长度1“A”正确答案:【长度2“AC”】8、问题：下面是求最长公共子序列长度和构造最优解的算法。【】中的语句缺失，请从如下选项中找到正确的答案补齐算法。voidLCSLength(intm,intn,char*x,char*y,int**c,int**b){inti，j;for(i=1;i=m;i++)c[i][0]=0;for(j=1;j=n;i++)c[0][j]=0;for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){【1】;b[i][j]=2;}else{【2】;b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[i];}elseif(b[i][j]==2)【3】;else【4】;}选项：A、(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)B、(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)C、(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)D、(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)正确答案:【(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)】9、问题：操场上摆放一行共n堆石头，从左到右方向编号为1~n，石子的数目分别为p[1],……,p[n]，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过n-1次合并，最终合并为一堆。计算这n堆石子合并为一堆的最小得分。分析该问题，从如下选项中找出用动态规划解决该问题的时间复杂性和空间复杂性选项：A、T（n）=O（）S(n)=O(B、T（n）=O（）S(n)=O(C、T（n）=O（）S(n)=O(D、T（n）=O（）S(n)=O())))正确答案:【T（n）=O（）S(n)=O()】10、问题：可用动态规划算法解决的问题需要满足几个基本要素，从下面选项中找出这些基本要素选项：A、阶段性B、最优子结构性质C、无后向性D、重复子问题正确答案:【最优子结构性质#重复子问题】11、问题：0-1背包问题：给定n种物品和一背包，物品i的重量wi，价值vi，背包容量为c，如何选择装入背包中的物品，使得装入背包中的物品总价值最大。设m[i][j]是前i个物品装入背包容量为j的背包所能获得的最大价值，下面是关于最优值的递归定义，从中选出正确的关于最优值m[i][j]的递归定义。选项：A、B、C、D、正确答案:【#】12、问题：操场上摆放一行共n堆石头，从左到右方向编号为1~n，石子的数目分别为p[1],……,p[n]，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过n-1次合并，最终合并为一堆。计算这n堆石子合并为一堆的最小得分。请根据题目要求，从如下选项中找出关于从第i堆到第j堆合并为一堆的最小得分m[i][j]的递归定义.选项：A、m[i][j]=0,if(i==j)B、m[i][j]=p[i],if(i==j)C、if（ij）m[i][j]=min(m[i][k]+m[k+1][j])+sum(i,j)这里i=kj，sum（i，j）是i堆到j堆石子的累加和。D、if（ij）m[i][j]=min(m[i][k]+m[k][j])+sum(i,j)这里i=kj，sum（i，j）是i堆到j堆石子的累加和。正确答案:【m[i][j]=0,if(i==j)#if（ij）m[i][j]=min(m[i][k]+m[k+1][j])+sum(i,j)这里i=kj，sum（i，j）是i堆到j堆石子的累加和。】13、填空题：操场上摆放一行共4堆石头，从左到右方向编号为1~4，各堆石子的数目分别为7,10,3,5，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过5次合并，最终合并为一堆。计算这6堆石子合并为一堆的最小得分正确答案:【50】14、填空题：现有一楼梯共8级台阶，有一小朋友一步可以迈出1、2或3级台阶，问小朋友有多少种不同的爬楼梯的方法正确答案:【81】第四单元测试1、问题：一个问题，针对某个贪心策略，可通过找反例的方法快速判断出其使用贪心算法不能构造出最优解。下面是关于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）对正确答案:【（1）错（2）对】2、问题：一个n位的10进制正整数，使得删除k位（kn）后剩余数字组成的正整数最小，用贪心算法实现该算法，问该问题的贪心策略是什么？也就是每次要删除哪个数字？选项：A、每次从整数中删去数字最大者B、每次从整数中找包含最高位的从左至右的一个最长的非递减序列，将该序列的最后一位删除C、每次删除该整数的最高位数字D、贪心算法不能有效解决该问题正确答案:【每次从整数中找包含最高位的从左至右的一个最长的非递减序列，将该序列的最后一位删除】3、问题：某中学有一个开水房，只有一个供热水龙头，课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案，也就是同学们按照他给出的排队方法，可以使同学们的平均等待时间最短。你分析一下，给出这个排队的方法，假定有n个人，第i个同学打水所需要的时间为ti，并给出平均等待时间的计算公式。（注意：第i个同学的等待时间包含前i-1个的打水时间和+自己打水的时间ti）选项：A、按照打水时间从大到小排队，平均等待时间T=∑ti/n1=i=nB、按照打水时间从小到大排队，平均等待时间T=∑ti/n1=i=nC、按照打水时间从大到小排队，假定排队后第i个人的打水时间是ti,平均等待时间T=∑(n-i+1)ti/n1=i=nD、按照打水时间从小到大排队，假定排队后第i个人的打水时间是ti,平均等待时间T=∑(n-i+1)ti/n1=i=n正确答案:【按照打水时间从小到大排队，假定排队后第i个人的打水时间是ti,平均等待时间T=∑(n-i+1)ti/n1=i=n】4、问题：哈夫曼编码树是用贪心算法解决的典型问题，分析该算法，回答如下问题，假定有n个字符生成的编码树，问编码树中的结点总数是多少？可能的最长的字符编码是多少位？选项：A、2n个结点，n位编码B、2n-1个结点n-1位编码C、2n-1个结点n位编码D、2n个结点n-1编码正确答案:【2n-1个结点n-1位编码】5、问题：下图中A~F顶点分别代表6个村庄，图中的边代表村庄之间的距离，为了满足这六个村庄相互通信的需要（任意两个村庄有线路可达），需要架设通信线路，这里要求代价最小化（即线路总长度最小），请你分析问题找到代价最小的方案，并计算出线路总长度，从如下选项中找出答案。选项：A、线路总长度20B、线路总长度21C、线路总长度22D、线路总长度23正确答案:【线路总长度21】6、问题：一个问题，确定了某个贪心策略，如果用贪心算法能够构造出问题的最优解，需要该问题具备哪两个条件？选项：A、没有重复子问题B、最优子结构性质C、无后向性D、贪心选择性质正确答案:【最优子结构性质#贪心选择性质】7、问题：给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，给定V中的一个顶点A，称为源，求从源顶点A出发到其他各顶点的最短路径长度称为单源最短路径长度问题。关于单源最短路径问题的Dijkstra算法，下面哪些描述是正确的？选项：A、设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S，直到全部加入，算法结束。B、每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[]数组记录各顶点的最短特殊路径长度。C、每次从V-S集合选择加入S集合的顶点是V-S集合中的顶点同S集合的顶点连接边最短的，通常算法中用dist[]数组记录S集合中各顶点与V-S集合中各顶点的最短连接边。D、每次选择一个顶点加入S集合后，都要检查是否需要更新dist[]数组元素的值正确答案:【设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S，直到全部加入，算法结束。#每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[]数组记录各顶点的最短特殊路径长度。#每次选择一个顶点加入S集合后，都要检查是否需要更新dist[]数组元素的值】8、问题：一个问题，可能有多个最优解，但是使用贪心算法最多只能找到一个最优解。选项：A、正确B、错误正确答案:【正确】9、问题：教材例题：多机调度问题，是用贪心算法求最优解的一个例子，贪心策略是每次从剩余任务中选择一个花费时间最长的任务，安排在占用时间最少的机器上。选项：A、正确B、错误正确答案:【错误】10、问题：贪心算法中常包含排序算法，也就是排序是贪心算法的伴随算法，有人这样解释其原因：贪心算法是根据贪心策略一步一步地选择去构造问题的解，排序就是按照要选择的顺序排列好，选择时只需按照排好的顺序选择就可以了。主要目的就是方便选择。该说法是否正确？选项：A、正确B、错误正确答案:【正确】11、问题：贪心算法是以自底向上的方式构造问题的最优解选项：A、正确B、错误正确答案:【错误】12、填空题：我国的货币单位是100元，50元，20元、10元、5元、2元、1元。有人到超市买了32元的商品，交给收银员100元，问收银员最少需要几张货币就能完成找零钱？正确答案:【5】13、填空题：最优分解问题：一个正整数分解为若干互不相同的自然数的和，使其乘积最大。使用贪心算法求将22这个数最优分解后，取得的最大乘积是多少？正确答案:【1008】第五章单元测试1、问题：下面关于回溯法的描述中，不正确的是哪个?选项：A、回溯法可使用递归算法实现B、回溯法是以深度优先的状态生成树法去搜索问题的解，并且能够避免不必要搜索。C、回溯法解决的问题，其解通常可以表达为n元组的形式D、回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。正确答案:【回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。】2、问题：下面描述不正确的是？选项：A、解空间树的分类中，尽管子集树的每个非叶子结点都有二个分支，但是不能把它称为n叉树。B、剪枝函数有二种，分别是约束函数和限界函数C、当解空间树是子集树时，约束函数对0分支剪枝，限界函数对1分支剪枝。D、对解空间树是n叉树（或排列树）来说，回溯法搜索时对每个分支使用的的剪枝条件（函数）是完全相同的。正确答案:【当解空间树是子集树时，约束函数对0分支剪枝，限界函数对1分支剪枝。】3、问题：n皇后问题是可用回溯法解决的问题。下面描述不正确的是？选项：A、当其解空间树是n叉树时，剪枝函数是任一列或任一（正反）对角线只能安排一个皇后。B、当其解空间树是排列树时，剪枝函数是任一（正反）对角线只能安排一个皇后。C、算法搜索至叶子结点时，就找到了一种新的皇后安排方案，算法可找到所有可行的方案。D、两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树正确答案:【两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树】4、问题：0-1背包问题的回溯算法，下面的解释不正确的是选项：A、解空间树是子集树B、左(1)分支的剪枝：当选择装入背包的物品重量之和超过背包容量时就剪枝。C、右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）当前最优值bestp,就剪枝.D、当搜索至叶子结点时，一定是发现了到目前为止最好的解正确答案:【右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）当前最优值bestp,就剪枝.】5、问题：n个城市的旅行售货商问题的回溯法中，r[i][j]是邻接矩阵，表示i城市到j城市的距离，x[]是路径信息,有A、B两段描述A.该问题的解空间树，第一层只有一个分支，也就是指定第一个城市作为出发城市，因为是环路的原因，指定哪个城市出发结果是一样的，这样做相当于在树的第一层剪掉了其他的n-1个分支，主要目的是提高搜索效率。自第二层开始往下是一颗排列树。B.该算法将第n-1层的结点看做是叶子结点，当搜索至该叶子结点时，整个环路(如果存在的话)长度就是路径x[1..n-1]的长度cc+r[n-1][n]+r[n][1]。根据A,B描述的正确与否，从如下选项中找到正确答案选项：A、A对，B对B、A对，B错C、A错，B对D、A错、B错正确答案:【A对，B错】6、问题：符号三角形问题的回溯算法如下half=（n+1）*n/4;//(n+1)*n/2是偶数voidbacktrack(intt){if((counthalf)||(t*(t-1)/2-counthalf))return;if(tn)sum++;elsefor(inti=0;i2;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((counthalf)||(t*(t-1)/2-counthalf))B、if((count=half)(t*(t-1)/2-count=half))C、if((count=half)(t*(t+1)/2-count=half))D、if((counthalf)||(t*(t+1)/2-counthalf))正确答案:【if((count=half)(t*(t+1)/2-count=half))】7、问题：子集和问题：给定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、sum-=a[i];B、sum-=a[i];backtrack(i+1);C、backtrack(i+1);D、backtrack(i+1);sum-=a[i];正确答案:【sum-=a[i];backtrack(i+1);】8、问题：给定n个可能含有重复的元素存放于x[1:n]，输出去掉重复的全排列，这里swap是实现两个变量值的交换，下面是算法描述注意：红色代码部分【1】【2】【3】位置有代码缺失。voidbacktrack(intt){if(tn){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】i，【2】t，【3】ok=1B、【1】i，【2】t，【3】ok=0C、【1】t，【2】i，【3】ok=1D、【1】t，【2】i，【3】ok=0正确答案:【【1】t，【2】i，【3】ok=0】9、问题：符号三角形问题，其解空间树是哪种？选项：A、排列树B、子集树C、n叉树（这里n=2）D、不规则树正确答案:【n叉树（这里n=2）】10、问题：子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题，从如下选项中找到关于该算法设计的正确的描述。选项：A、当解空间树是排列树时，搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。B、剪枝条件:当路径上的数之和c时剪枝C、该算法搜索至排列树的叶子结点（即第n层结点）时，就找到了一个解。D、数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率。正确答案:【当解空间树是排列树时，搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。#剪枝条件:当路径上的数之和c时剪枝】11、问题：回溯法的算法效率跟哪些因素有关？这里x【k】是分支上的取值。选项：A、满足隐约束函数和限界函数约束的所有x【k】的个数B、计算隐约束函数值的时间C、计算限界函数值的时间D、满足显约束的x【k】的个数。正确答案:【满足隐约束函数和限界函数约束的所有x【k】的个数#计算隐约束函数值的时间#计算限界函数值的时间#满足显约束的x【k】的个数。】12、问题：回溯法是在一颗已经建立起来的解空间树中实现深度优先搜索的算法。选项：A、正确B、错误正确答案:【错误】13、问题：回溯法中，剪枝函数能够剪掉的分支越多，算法效率就越高。因此，我们在设计回溯法时，就要设计剪枝函数能够剪掉尽量多的分支。选项：A、正确B、错误正确答案:【错误】第六单元测试1、问题：分支限界法与回溯法的不同点体现在哪些方面？（1）求解目标不同，分支限界法可求最优解或满足条件的一个解，而回溯法可求最优解或满足条件的所有解（2）搜索方式不同，回溯法是以深度优先状态生成树法搜索解空间树，分支限界法则以广度优先或最小耗费（最大效益）优先的状态生成树法搜索解空间树。（3）同一个问题在使用回溯法或分支限界法时，该问题的解空间树的结构不同（4）回溯法与分支限界法，构造最优解的方式不同。从上述选项中找出答案。选项：A、（1）（3）（4）B、（1）（2）（3）C、（1）（2）（4）D、（2）（3）（4）正确答案:【（1）（2）（4）】2、问题：分支限界法中，扩展出的孩子结点在入队时，存储该孩子结点的父结点的地址和左孩子标志。其目的是什么？选项：A、为了计算最优值B、为了确定其孩子结点在队列中的位置C、为了构造最优解D、为了方便判定是否已搜索到达叶子层正确答案:【为了构造最优解】3、问题：在队列式分支限界法解决装载问题时，为什么在其改进算法中，每次进入左分支都要检查更新bestw，而不是等搜索到达叶子结点时才去更新bestw，其目的是什么？选项：A、为了及早使右（0）分支剪枝函数生效。B、为了及早使左（1）分支剪枝函数生效C、为了计算最优值D、为了方便构造最优解正确答案:【为了及早使右（0）分支剪枝函数生效。】4、问题：在队列式分支限界法中，叶子结点不加入队列。而在优先队列式分支限界法中，叶子结点通常要加入到优先队列中。有下列2个解释：（1）队列式分支限界法，活结点在队列中的顺序是按照搜索解空间树时扩展出该结点的先后顺序存放，每次从队首取出一个活结点成为新的扩展结点。扩展结点扩展出的儿子结点是叶子结点时，会将该叶子结点的值同当前最优值比较，检查更新最优值，叶子结点并不进入队列，等队列为空时，搜索结束，记录的当前最优值就是问题最优值。（2）优先队列式分支限界法中，当优先级的定义是限界函数时，扩展出的叶子结点进入队列，这种做法主要是为了让搜索过程提前结束。也就是当从优先队列中取出一个活结点是叶子结点时，意味着现在优先队列中剩余的所有活结点其优先级都不大于该叶子结点的优先级，叶子结点的优先级等于最优值，算法结束，无论优先队列是否为空。根据其正确与否，给出答案选项：A、（1）正确，（2）错误B、（1）正确，（2）正确C、（1）错误，（2）错误D、（1）错误，（2）正确正确答案:【（1）正确，（2）正确】5、问题：下面是优先队列式分支限界算法解0-1背包问题的部分主代码，分析代码将【】内的代码补齐。TempleteclassTypew,classTypepTypepknapTypew,Typep::MaxKnapsack(){//优先队列分支限界法，返回最大价值，最优解bestxH=newMaxHeapHeapNodeTypep,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(upbestp)AddLiveNode(up,cp,cw,false,i+1);//从优先队列中取下一个扩展节点HeapNodeTypep,TypewN;H-DeleteMax(N);E=NNaNr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//构造最优解for（intj=n;j0;j--）{bestx[j]=E-lchild;E=E-parent;}returncp;}选项：A、【1】in+1,【2】besp=cp+p[i]B、【1】i!=n+1,【2】cw=cw+w[i]C、【1】i!=n,【2】cw=cw+w[i]D、【1】in,【2】besp=cp+p[i]正确答案:【【1】in+1,【2】besp=cp+p[i]】6、问题：阅读该单元测试中关于0-1背包问题的优先队列分支限界算法代码，问左分支的剪枝条件是什么？右分支的剪枝条件是什么？从代码中找到命令行，使用原代码回答问题。选项：A、左分支：wt=c,右分支：upbestpB、左分支：cp+p[i]bestp,右分支：upbestpC、左分支：cp+p[i]bestp,右分支：wt=cD、左分支：wt=c,右分支：cp+p[i]bestp正确答案:【左分支：wt=c,右分支：upbestp】7、问题：优先队列式分支限界法解决0-1背包问题时，下面描述正确的是选项：A、左孩子结点的优先级等于父结点的优先级B、左孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值C、右孩子结点的优先级等于父结点的优先级D、右孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值正确答案:【左孩子结点的优先级等于父结点的优先级#右孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值】8、问题：回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)),h(n)是解空间树的深度。选项：A、正确B、错误正确答案:【错误】9、问题：在队列式分支限界法解决装载问题时，在队列中加入一个-1标志，该标志所起的作用是表示其后的活结点在解空间树中的层数比-1之前的活结点更深一层，或者说是同层活结点的结束标志。选项：A、正确B、错误正确答案:【正确】10、填空题：下面是一个布线问题,S表示布线的起点，O表示布线的终点，假定布线只能垂直、或水平布线，从一个点按照上、下、左、右的优先顺序可往四个方向布线，“#是障碍不能通过。已知从一个位置向其上、下、左、右四个相邻位置布线的线路长度为1。使用队列式分支限界法解决该问题，问从S到O的最短布线长度？###S##o#######正确答案:【8】第七单元测试1、问题：有这样一种算法，运行一次可能找不到问题的解，运行多次就一定能找到问题的解，且运行次数有界，这种算法是？选项：A、拉斯维加斯算法B、蒙特卡洛算法C、舍伍德算法D、数值概率算法正确答案:【拉斯维加斯算法】2、问题：有这样一种算法，运行一次一定能找到问题的解，有时不知其是否正确，可以确定的是该解高概率（大于50%）是正确的。这种算法是？选项：A、拉斯维加斯算法B、蒙特卡洛算法C、舍伍德算法D、数值概率算法正确答案:【蒙特卡洛算法】3、问题：有一个问题的蒙特卡洛算法，给定一个实例，已知运行一次其答案是错误的概率是1/8,现运行k次该算法，其答案一直不变，问该答案的正确率是？选项：A、(1/8)^kB、7/8C、1-(7/8)^kD、1-(1/8)^k正确答案:【1-(1/8)^k】4、问题：一致的p正确的偏y0的蒙特卡洛算法，下面解释不正确的是?选项：A、运行蒙特卡洛算法p次，至少有一次是正确的。B、一致是指蒙特卡洛算法对于一个实例，其正确解是唯一的。C、当正确解是y0,而蒙特卡洛算法得到的解不是y0D、猜硬币的正反面问题，因为猜一次正确的概率是50%，所以不能使用蒙特卡洛算法解决。正确答案:【运行蒙特卡洛算法p次，至少有一次是正确的。】5、问题：pollard算法找到一个整数因子的时间复杂性是？选项：A、O(n)B、O(logn)C、O(D、O())正确答案:【O()】6、问题：n=12皇后问题的三种不同的解决方案：回溯法、拉斯维加斯算法、拉斯维加斯算法+回溯法。对于给定的一个实例，(1)平均耗费时间最少的是那种方案？，(2)平均耗费时间最多的是那种方案？选项：A、(1)回溯法(2)拉斯维加斯+回溯法B、(1)回溯法(2)拉斯维加斯C、(1)拉斯维加斯(2)回溯法D、(1)拉斯维加斯+回溯(2)回溯法正确答案:【(1)拉斯维加斯+回溯(2)回溯法】7、问题：在分治法中讲到快速排序，如果每次使用partion函数导致分组出现严重不平衡情况下，算法效率不高，最坏情况下的时间复杂度为O（n^2）,通过改造partition函数，也就是每次随机选择一个元素作为划分基准，这样会很好地改善算法的性能，这种算法思想是？选项：A、拉斯维加斯算法B、蒙特卡洛算法C、舍伍德算法D、数值概率算法正确答案:【舍伍德算法】8、问题：舍伍德算法思想是通过引入随机化策略将确定性算法改造为随机算法，打破原来确定性算法在某些实例情况下，其时间复杂性必然远高于平均时间复杂性的规律。下面哪些算法可以应用舍伍德算法思想？选项：A、快速排序算法B、线性时间选择算法C、归并排序D、跳跃表正确答案:【快速排序算法#线性时间选择算法#跳跃表】9、问题：计算机中的随机数是伪随机的，因为它是具有一定规律的，是按公式计算出来的。该说法正确吗？选项：A、正确B、错误正确答案:【正确】10、问题：素数测试问题的蒙特卡洛算法，n是一个待判定正整数。当n是素数时，有时会被判定为非素数。该说法正确吗?选项：A、正确B、错误正确答案:【错误】11、问题：有人说可以设计蒙特卡洛算法去猜硬币的反正面问题，该说法是否正确？选项：A、正确B、错误正确答案:【错误】12、填空题：数值概率算法求π的算法，是用半径为1的圆外接一个正方形，然后模拟向正方形中随机投放n个点，计数落在圆内的点的个数为k，则π的近似值为正确答案:【4k/n##%_YZPRLFH_%##4*k/n】第八单元测试1、问题：下面哪个问题不是NPC问题选项：A、最大团问题B、子集和问题C、旅行售货员问题D、最小生成树问题正确答案:【最小生成树问题】2、问题：请从下列选项中找出正确的P问题与NP问题的关系选项：A、B、C、D、正确答案:【】3、问题：NP问题是确定性算法不能在多项式时间复杂性解决的可判定问题选项：A、正确B、错误正确答案:【错误】4、问题：一个NPC问题，首先是NP问题，另外所有的其他NP问题都能在多项式时间复杂性规约为该问题选项：A、正确B、错误正确答案:【正确】5、问题：研究NPC问题的意义，一旦一个NPC问题找到了多项式时间复杂性的确定性算法，那么所有的NPC问题都找到了多项式时间复杂性的确定性算法。选项：A、正确B、错误正确答案:【正确】6、问题：NP难问题未必是NP问题选项：A、正确B、错误正确答案:【正确】7、问题：一个人正站在门口，让你猜他（她）是否要出门？，该问题是不可判定问题，该观点是否正确？选项：A、正确B、错误正确答案:【正确】客观题试卷1、问题：如下哪种表示不是归并排序算法时间复杂性选项：A、Ω（nlogn）B、O（nlogn）C、o(nlogn)D、θ（nlogn）正确答案:【o(nlogn)】2、问题：最优子结构性质是选项：A、问题可以分解为性质相同的子问题B、问题的最优解可通过性质相同的子问题的最优解合并而成C、问题的最优解可通过一步步局部最优的选择来获得。D、子问题可同原问题性质不同，但是原问题的最优解可通过子问题的最优解合并而成正确答案:【问题的最优解可通过性质相同的子问题的最优解合并而成】3、问题：有一算法的时间复杂性递归定义:T(n)=8T(n/2)+nlognifn1,T(1)=1;问T(n)=？选项：A、O（nlogn)B、C、D、正确答案:【】4、问题：哈夫曼编码树算法中用优先队列（堆）存储生成的结点，n个字符的哈夫曼编码树算法时间复杂性为选项：A、B、C、D、正确答案:【】5、问题：下列哪些问题不能用贪心算法求最优解选项：A、最小生成树B、单源最短路径C、最优二叉搜素树D、哈夫曼编码树正确答案:【最优二叉搜素树】6、问题：在下列算法中，可求解n皇后问题的算法是选项：A、数值概率算法B、舍伍德算法C、拉斯维加斯算法D、蒙特卡罗算法正确答案:【拉斯维加斯算法】7、问题：爬楼梯问题：有一楼梯共n级台阶，有一小朋友一次可以迈1，2或3级台阶，求共有多少不同的走法走完这n级台阶。回答该问题最适合使用哪种算法？选项：A、分治法B、回溯法C、贪心算法D、动态规划正确答案:【动态规划】8、问题：给定n个任务接受同一台机器加工,任务i有服务时间和要求截止时间(ti,di),找出最小延迟方案，即所有任务延迟时间最大值的最小化问题。如3个任务1、2、3，服务时间和截至时间为（2，4）（1，2）（7，7），如按照1-2-3顺序安排，各任务的延迟为0，1，3，延迟的最大值为3。使用贪心算法，如下哪种贪心策略可得到最优解？选项：A、以服务时间ti从小到大安排B、以di-ti从小到大安排C、以截止时间di从小到大安排D、以上都不可能正确答案:【以截止时间di从小到大安排】9、问题：有n个正整数组成的数组a，两端的数不能删除，中间每删除一个数，其得分为其本身同其两侧的数的乘积，求其中间n-2个数逐个删除后的最大得分。设m[i][j]为从a[i]到a[j]的子数组，将中间数全部删除后的最大得分。从如下公式中选择正确的m[i][j]的递归定义选项：A、m[i][j]=max(m[i][k]+m[k+1][j]+a[i]*a[k]*a[j]),ikj,if(j-i1).m[i][j]=0;if(j-i==1).B、m[i][j]=max(m[i][k]+m[k+1][j]+a[k-1]*a[k]*a[k+1]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)C、m[i][j]=max(m[i][k]+m[k][j]+a[i]*a[k]*a[j]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)D、m[i][j]=max(m[i][k]+m[k][j]+a[k-1]*a[k]*a[k+1]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)正确答案:【m[i][j]=max(m[i][k]+m[k][j]+a[i]*a[k]*a[j]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)】10、问题：下面哪些不是队列式分支限界法的特点选项：A、叶子结点要加入队列B、如果需要，队列中同层结点后可加入特殊标志与下层结点区分开C、结点没有优先级定义D、算法中循环的结束条件是当队列为空时。正确答案:【叶子结点要加入队列】11、问题：回溯法和分支限界法的主要区别是选项：A、解空间树不同B、约束条件不同C、搜素方式不同D、求解目标不同正确答案:【搜素方式不同#求解目标不同】12、问题：P问题、NP问题、NPC问题，下列哪些解释是正确的？选项：A、P问题是确定性算法多项式时间复杂性解决的可判定问题B、NP问题是确定性算法不能在多项式时间复杂性解决的可判定问题C、PíNPD、NPCìNP正确答案:【P问题是确定性算法多项式时间复杂性解决的可判定问题#PíNP】13、问题：快速排序算法，其时间复杂性是，而其平均时间复杂性是，下面哪些方法可以改善快速排序算法的性能？选项：A、拉斯维加斯算法B、蒙特卡洛算法C、洗牌算法D、舍伍德算法正确答案:【洗牌算法#舍伍德算法】14、问题：下面哪些算法是解决单源最短路径问题的有效算法？选项：A、贪心算法B、分治法C、优先队列分支限界法D、队列式分支限界法正确答案:【贪心算法#优先队列分支限界法】15、问题：一个含有n个元素的有序数组A,将其循环右移动c个位置得到新的数组B,则B为循环有序的，如有5个元素的数组：12345，每个元素循环右移3个位置得到新数组：34512，是循环有序的，B[i]=A[(i+c)%n】。现给定一个含有n个元素的循环有序序列，要找到其最小值。给定方法是分治策略，将数组一分为二，B[0..n/2-1]和B[n/2..n-1],从下列选项中找到正确的描述选项：A、将一个规模为n的问题分解为两个子问题B、将一个规模为n的问题分解为一个子问题C、该算法的时间复杂度是O（log（n）)D、该算法的时间复杂度是O（n）正确答案:【将一个规模为n的问题分解为一个子问题#该算法的时间复杂度是O（log（n）)】16、问题：现有n个字符，在一份报文中出现的次数构成斐波那契数列，即1,1,2,3,5，，，..问这n个字符的哈夫曼编码，具有如下哪些特点？选项：A、编码长度为n-1位的有二个字符B、编码长度为1到n-2的字符都只有一个C、编码长度为n-1的有一个字符D、编码长度为1到n-2的字符可能超过1个。正确答案:【编码长度为n-1位的有二个字符#编码长度为1到n-2的字符都只有一个】17、问题：1、最大团问题是指求无向图中任意两个顶点都有连接边的子图，且顶点个数最多。现有回溯法算法如下。将【】内缺失的代码补齐。这里a是邻接矩阵，a[i][j]=0表示i和j顶点没有连接关系。voidbacktrack(inti){if(in){for(intj=1;j=n;j++)bestx[j]=x[j];bestn=cn;return;}booleanok=true;for(intj=1;ji;j++)if(!a[i][j]){ok=false;break;}if(ok){x[i]=1;【1】;backtrack(i+1);cn--;}if(【2】){x[i]=0;b