算法设计与分析(青岛大学) 中国大学mooc慕课答案2024版 m297879

第一章 算法概论 第一章 单元测试

1、  下面列出了算法的四个性质，哪个性质是程序不一定具备的？

答案: 有穷性

2、 在算法设计与分析过程中，有算法设计，算法的正确性证明，算法的复杂性分析,程序设计等几个重要步骤，下面哪种顺序是正确的？

答案: 算法设计->算法的正确性证明->算法的复杂性分析->程序设计

3、 下面哪些内容不是算法设计之前要完成的内容?

答案: 使用何种计算机语言设计程序

4、 下面是快速幂算法求的代码，这里n≥0, a是实数。对该算法的时间复杂性描述不准确的是哪个？doule exp2(double a, int n){int i;double b, s=1.0；i=n；b=a;while（i>0）{  if(i%2) s=b；i/=2;  b=b;}return s;}

答案:

5、 下面那个算法在最坏情况下的时间复杂性最低

答案: 归并排序

6、 有时间复杂性,时间复杂性从低到高的顺序是？

答案:

7、   有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是?

答案:

8、 有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是？      

答案:

9、 有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是？

答案:

10、 有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是?

答案:

11、 解决同一个问题的算法策略可能有多个，无论使用那种算法策略，算法时间复杂性是相同的。

答案: 错误

12、 描述算法只能使用二种方法：伪代码或自然语言

答案: 错误

13、 下面哪个算法在最坏情况下的时间复杂性最低

答案: 归并排序

14、   A公司处理器速度是B公司的100倍。对于复杂性为O()的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时内能处理的问题规模是多少？

答案: 10n

15、 关于算法的正确性，下面哪些说法是正确的？

答案: 若算法是正确的， 则算法一定能结束（运行时间是有限的）;
若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。;
对于问题的一个实例， 如果算法不能获得正确的结果， 就证明算法是不正确的。

16、 解决同一个问题的算法策略可能有多个，使用不同算法策略设计的算法，其算法时间复杂性可能有显著差异。

答案: 正确

17、 学习主定理和递归树等求解递归方程方法，主要目的是解决求递归算法的时间复杂性问题

答案: 正确

18、 自然语言、伪代码都可以描述算法，而流程图不能描述算法

答案: 错误

第二章 分治法 第二章 单元测试

1、 分治法解决问题分为三步走，即分、治、合。下面列出了几种操作， 请按分、治、合顺序选择正确的表述。（1）将各个子问题的解合并为大问题的解，（2）将问题分解为子问题，（3）将各个子问题合并为大问题。（4）求各个子问题的解，（5）将问题分解为可重复的子问题。

答案: (2)(4)(1)

2、 分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程， 然后解此方程可得T(n)的结果。T(n)的递归定义如下：关于该定义中k，n/m,  f(n)的解释准确的是

答案: k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和

3、 已知斐波那契数列中第n个斐波那契数F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第n个斐波那契数，从下面选项中选取答案。

答案: 不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）

4、 快速幂算法求， 其时间复杂性为O(logn)，a是实数，n为非负整数。下面是一同学用c语言编写的求的代码double exp2(double a,int n){  if(a==0)  return 0;   if (n==0) return 1;   else        {                   if(n%2)  return a exp2(a,n/2) exp2(a,n/2);         else    return exp2(a,n/2)* exp2(a,n/2);       } }对该同学的算法评价正确的是？

答案: 运行结果正确，时间复杂性为O(n)

5、 快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？

答案: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n) 

6、 猜数游戏：随机选择一个0~100内的整数，让你猜。 猜对了，你赢了，游戏结束。如果没有猜对，会告诉你猜大了，还是猜小了。当然，越早猜对越好。 问你最多猜多少次就能保证一定能猜对？

答案: 7

7、 对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文。比如：“abcba”、“abba”是回文，“abc”则不是回文。bool isPal( char *str, int n){    if ( n == 0 ||     （1）     )        return true;    if ( str[0] !=      （2）     )        return false;    return isPal(      （3）    ,   （4）    );}算法中处缺少语句，请分析算法，从如下选项中选择语句补齐算法。

答案:  (1) n==1  (2)  str[n-1]  (3) str+1  (4) n-2

8、 对于一个采用字符数组存放的长度为n的字符串str，下面是判断是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”则不是回文bool isPal( char *str, int n){    if ( n == 0 ||     （1）     )        return true;    if ( str[0] !=      （2）     )        return false;    return isPal(      （3）    ,   （4）    );}请补齐代码后分析算法的时间复杂性，回答如下问题

答案: 该算法时间复杂性的递归定义为： T(n)=T(n-2)+1，if n>1;T(n)=O(1), if n≤1。T(n)=O(n), T(n)=Ω(1)

9、 棋盘nxn（）的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治算法。关于该算法时间复杂性描述不正确的是

答案: T(n)=O(n^4)

10、 棋盘8X8的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治策略。约定解决四个子问题的顺序为右下，左下, 左上，右上。用数字标识法填写覆盖方案（如3个相连的整数值i构成的L块，代表是第i个被放入棋盘中的L型块）。 使用分治策略的算法有三种形式 ：1使用递归算法实现， 2使用队列存取分解出的子棋盘的非递归算法 3.使用栈存取分解出的子棋盘的非递归算法。下图中有三个覆盖图案（只标出了前7块L型模块位置），问自左至右分别是哪种算法实现的覆盖方案？

答案: 递归算法，队列算法， 栈算法

11、 下面哪些不是递归算法的特点

答案: 递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少

12、 分治法解决问题时，平衡子问题思想是指：划分出的子问题规模基本一致，算法效率高

答案: 正确

13、 快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？

答案: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n) 

14、 分治法解决问题分为三步走，即分、治、合。下面列出了几种操作， 请按分、治、合顺序选择正确的表述。（1）将各个子问题的解合并为原问题的解，（2）将问题分解为各自独立的多个子问题，（3）将多个子问题合并为原问题。（4）求各个子问题的解，（5）将问题分解为可重复的多个子问题。

答案: (2)(4)(1)

15、 分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程， 然后解此方程可得T(n)的结果。T(n)的递归定义如下：关于该定义中k，n/m,  f(n)的解释准确的是

答案: k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和

16、 快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？

答案: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n) 

17、 猜数游戏：随机选择一个0~100内的整数，让你猜。 猜对了，你赢了，游戏结束。如果没有猜对，会告诉你猜大了，还是猜小了。当然，越早猜对越好。 问最少需要猜多少次，就能保证一定能猜对？

答案: 7

18、 对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文，如是回文，函数返回true，否则返回false。比如：“abcba”、“abba”是回文，“abc”则不是回文。bool isPal( char *str, int n){    if ( n == 0 ||     （1）     )        return true;    if ( str[0] !=      （2）     )        return false;    return isPal(      （3）    ,   （4）    );}算法中处缺少语句，请分析算法，从如下选项中选择语句补齐算法。

答案:  (1) n==1  (2)  str[n-1]  (3) str+1  (4) n-2

19、 给定n个正整数组成的无序序列， 要找到该序列的中位数，解决该问题的最优算法的时间复杂性是？

答案: O（n）

20、 将一个递归算法改造为非递归算法， 常用的数据结构是？

答案: 栈

21、 分治法解决问题时，平衡子问题思想是指：当问题划分出的子问题规模基本一致时，算法计算效率高

答案: 正确

22、 递归程序代码简短，结构清晰，易读性强，相比解决同一问题的非递归程序，递归程序运行时间短。

答案: 错误

第三章 动态规划 第三单元测试

1、 求第n个斐波那契数的问题，根据动态规划的二要素分析，是可以用动态规划算法去解决的，下面是用备忘录方法（递归）解决的求第n个斐波那契数f[n]的程序. int  f[N]={0,1,1};int fib(int n){ if ( 1  ) return f[n]; else return 2    ;   }代码中1 和2位置代码缺失， 请从下列选项中选出合适的语句补齐算法。

答案:                   1f[n]>0  2 f[n]=fib(n-1)+fib(n-2)

2、 动态规划解题的步骤分为四步（1）分析最优解的结构 （2）建立递归关系（3）计算最优值（4）构造最优解。关于这四个步骤的内容描述不正确的是哪个？

答案: 计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。

3、 矩阵连乘问题：下图是动态规划算法计算6个矩阵A1A2A3A4A5A6连乘所生成的信息表.（a）表描述了计算顺序， （b）表是m[i][j]的最优值表，（c）表是辅助信息表（断开位置）。 分析表格，给出A2A3A4A5A6 五个矩阵连乘所需要的最少数乘次数，并用加括号的方法表示出其乘法顺序。从如下选项中选择。

答案:   10500,    (A2A3)((A4A5)A6)

4、 凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？ 

答案: 左图正确，4种

5、 游艇租赁问题：长江游艇俱乐部在长江上设置了n个游艇出租站1~n，游客可在这些游艇出租站租用游艇， 并在下游的任何出租站归还游艇，限制只能从上游往下游行进，游艇出租站i到出租站j直达的租金为r(i,j)（1<=i<j<=n），计算从游艇出租站1到出租站n的最小费用。该问题可有二种最优解的结构形式，如图所示：如下描述中错误的是哪个？

答案:  图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时的最优值。其中第四行的数据没有填写，分析问题， 将第四行的数据从如下选项中找出。

答案: 0  3  7   10  10  13

7、 最长公共子序列问题：现有两个字符序列X和Y, 下面c矩阵和b矩阵是算法填写出的信息表。  c[i][j]是X序列的前i个字符和Y序列的前j个字符的最长公共子序列的长度，b[i][j]是辅助信息表。已知X=”ABC”根据表格内容，回答X和Y的最长公共子序列长度及最长公共子序列包含的符号

答案: 长度2   “AC”

8、 下面是求最长公共子序列长度和构造最优解的算法。中的语句缺失， 请从如下选项中找到正确的答案补齐算法。void LCSLength(int m, int n, char x, char y, int c, int b){      int i，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;}             else if (c[i-1][j]>=c[i][j-1])  { 1;  b[i][j]=2; }             else  { 2;  b[i][j]=3; }             }} void LCS(int i, int j, char x, int *b){      if (i ==0 || j==0) return;      if (b[i][j]== 1)           { LCS(i-1,j-1,x,b); cout<<x[i]; }      else if (b[i][j]== 2)         3;      else         4;}

答案:  (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、 可用动态规划算法解决的问题需要满足几个基本要素，从下面选项中找出这些基本要素

答案: 最优子结构性质;
重复子问题

10、 0-1背包问题：给定n种物品和一背包，物品i的重量wi，价值vi，背包容量为c，如何选择装入背包中的物品，使得装入背包中的物品总价值最大。设m[i][j]是前i个物品装入背包容量为j的背包所能获得的最大价值，下面是关于最优值的递归定义，从中选出正确的关于最优值m[i][j]的递归定义。

答案: ;

11、 求第n个斐波那契数的问题，根据动态规划的二要素分析，是可以用动态规划算法去解决的，下面是用备忘录方法（递归）解决的求第n个斐波那契数f[n]的程序.这里N是一个较大的正整数常量，注意备忘录方法的设计要点（也就是，对于一个问题， 首先判断是否该问题已被解决过，如果解决，不再重复。另外，解决过的问题，答案要记住） int  f[N]={0,1,1};int fib(int n){ if ( 1  ) return f[n]; else return 2    ;   }代码中1 和2位置代码缺失， 请从下列选项中选出合适的语句补齐算法。

答案:                   1f[n]>0  2 f[n]=fib(n-1)+fib(n-2)

12、 操场上摆放一行共n堆石头，从左到右方向编号为1~n，石子的数目分别为p[1],……,p[n]，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过n-1次合并，最终合并为一堆。计算这n堆石子合并为一堆的最小得分。分析该问题，从如下选项中找出用动态规划解决该问题的时间复杂性和空间复杂性

答案: T（n）=O（）     S(n)=O( )

13、 操场上摆放一行共n堆石头，从左到右方向编号为1~n，石子的数目分别为p[1],……,p[n]，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过n-1次合并，最终合并为一堆。计算这n堆石子合并为一堆的最小得分。请根据题目要求，从如下选项中找出关于从第i堆到第j堆合并为一堆的最小得分m[i][j]的递归定义.

答案: m[i][j]=0,    if (i==j);
if（i<j）    m[i][j]=min(m[i][k]+m[k+1][j])+sum(i,j)      这里i<= k<j， sum（i，j）是i堆到j堆石子的累加和。

14、 操场上摆放一行共4堆石头，从左到右方向编号为1~4，各堆石子的数目分别为7,10,3,5，现要将石子有次序的合并为一堆，规定每次只能选相邻的2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过5次合并，最终合并为一堆。计算这6堆石子合并为一堆的最小得分
答案: 50

15、 现有一楼梯共8级台阶，有一小朋友一步可以迈出1、2或3级台阶， 问小朋友有多少种不同的爬楼梯的方法
答案: 81

16、 凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？ 

答案: 左图正确，14种

第四章 贪心算法 第四单元测试

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）分析判定哪个反例是对的， 哪个反例是错的，从如下选项中找到你的答案。

答案: （1） 错（2） 对

2、 一个n位的10进制正整数，使得删除k位（k<n）后剩余数字组成的正整数最小，用贪心算法实现该算法， 问该问题的贪心策略是什么？也就是每次要删除哪个数字？

答案: 每次从整数中找包含最高位的从左至右的一个最长的非递减序列，将该序列的最后一位删除

3、 某中学有一个开水房，只有一个供热水龙头， 课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案， 也就是同学们按照他给出的排队方法， 可以使同学们的平均等待时间最短。你分析一下，给出这个排队的方法，假定有n个人，第i个同学打水所需要的时间为ti，并给出平均等待时间的计算公式。（注意：第i个同学的等待时间包含前i-1个的打水时间和+自己打水的时间ti）

答案: 按照打水时间从小到大排队，假定排队后第i个人的打水时间是ti,  平均等待时间 T=∑(n-i+1)ti/n   1<=i<=n

4、 哈夫曼编码树是用贪心算法解决的典型问题， 分析该算法，回答如下问题， 假定有n个字符生成的编码树， 问编码树中的结点总数是多少？可能的最长的字符编码是多少位？

答案: 2n-1 个结点  n-1位编码

5、 下图中A~F顶点分别代表6个村庄，图中的边代表村庄之间的距离， 为了满足这六个村庄相互通信的需要（任意两个村庄有线路可达），需要架设通信线路，这里要求代价最小化（即线路总长度最小），请你分析问题找到代价最小的方案， 并计算出线路总长度，从如下选项中找出答案。

答案: 线路总长度21

6、 一个问题，确定了某个贪心策略， 如果用贪心算法能够构造出问题的最优解， 需要该问题具备哪两个条件？

答案: 最优子结构性质;
贪心选择性质

7、 一个问题，可能有多个最优解， 但是使用贪心算法最多只能找到一个最优解。

答案: 正确

8、 教材例题：多机调度问题，是用贪心算法求最优解的一个例子，贪心策略是每次从剩余任务中选择一个花费时间最长的任务，安排在占用时间最少的机器上。

答案: 错误

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。

,

9、 贪心算法中常包含排序算法， 也就是排序是贪心算法的伴随算法， 有人这样解释其原因：贪心算法是根据贪心策略一步一步地选择去构造问题的解， 排序就是按照要选择的顺序排列好，选择时只需按照排好的顺序选择就可以了。主要目的就是方便选择。该说法是否正确？

答案: 正确

10、 我国的货币单位是100元， 50元，20元、10元、5元、2元、1元。有人到超市买了32元的商品，交给收银员100元， 问收银员最少需要几张货币就能完成找零钱？
答案: 5

11、  最优分解问题：一个正整数分解为若干互不相同的自然数的和，使其乘积最大。使用贪心算法求将22这个数最优分解后，取得的最大乘积是多少？
答案: 1008

12、 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，给定V中的一个顶点A，称为源，求从源顶点A出发到其他各顶点的最短路径长度称为单源最短路径长度问题。关于单源最短路径问题的Dijkstra 算法， 下面哪些描述是正确的？ 

答案: 设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S， 直到全部加入，算法结束。;
每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[] 数组记录各顶点的最短特殊路径长度。;
每次选择一个顶点加入S集合后， 都要检查是否需要更新dist[]数组元素的值

13、 贪心算法是以自底向上的方式构造问题的最优解

答案: 错误

14、 哈夫曼编码树是用贪心算法解决的典型问题， 分析该算法，回答如下问题， 假定有n（n>1)个字符生成的编码树， 问编码树中的结点总数是多少？可能的最长的字符编码是多少位？

答案: 2n-1 个结点  n-1位编码

第五章 回溯法 第五章 单元测试

1、 下面关于回溯法的描述中， 不正确的是哪个?

答案: 回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。

2、 下面描述不正确的是？

答案: 当解空间树是子集树时，约束函数对0分支剪枝，限界函数对1分支剪枝。

3、 n皇后问题是可用回溯法解决的问题。下面描述不正确的是？

答案: 两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树

4、 0-1背包问题的回溯算法，下面的解释不正确的是

答案: 右（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对，B错

6、 符号三角形问题的回溯算法如下half=（n+1）n/4;  //  (n+1)n/2是偶数void backtrack (int t)   {   if ((count>half)||(t(t-1)/2-count>half)) return;       if (t>n) sum++;       else           for (int i=0;i<2;i++) {                   p[1][t]=i;               count+=i;               for (int j=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 (int j=2;j<=t;j++)  count-=p[j][t-j+1];              count-=i;           }   }现要求将红色代码去掉， 保持算法功能不改变，需在    添加下面哪段代码？

答案: if ((count<=half)&&(t(t+1)/2-count<=half))

7、 子集和问题：给定n个不同的正整数，已知其和大于c，问有多少个不同的其和等于c的子集？下面给出的算法，解空间树是子集树，且n个数已按从小到大有序存放于a数组中。void backtrack(int i)  {      if(sum==c) count++;      else if(i<=n)      {               if(sum+a[i]<=c)               {  sum+=a[i];                 backtrack(i+1);                                                               }           }  }    请将                  位置缺失的代码补齐，从下面选项中找到答案。

答案: sum-=a[i];  backtrack(i+1);

8、  给定n个可能含有重复的元素存放于x[1:n]，输出去重复的全排列， 这里swap是实现两个变量值的交换，下面是算法描述注意：红色代码部分123位置有代码缺失。void backtrack(int t){         if(t>n) {                  for(int i=1;i<=n;i++)                          printf(“%d “,x[i]);                  printf(“”);             }         else{                  for(int i=t;i<=n;i++){                          int ok=1;                          for(int j=  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]);                          }                  }                              }}上面的算法中， 红色代码部分123位置代码缺失， 请从如下选项中找到合适的代码。

答案: 1t，2  i ，3  ok=0

9、 符号三角形问题， 其解空间树是哪种？

答案: n叉树

10、 子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。

答案: 当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。;
剪枝条件:当路径上的数之和>c时剪枝

11、 回溯法是在一颗已经建立起来的解空间树中实现深度优先搜索的算法。

答案: 错误

12、 n皇后问题是可用回溯法解决的问题。下面描述不正确的是？

答案: 两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树

13、 0-1背包问题的回溯算法，下面的解释不正确的是

答案: 右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）>当前最优值bestp, 就剪枝.

14、 子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。

答案: 当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。;
剪枝条件:当路径上的数之和>c时剪枝

15、  给定n个可能含有重复的元素存放于x[1:n]，输出去掉重复的全排列， 这里swap是实现两个变量值的交换，下面是算法描述注意：红色代码部分123位置有代码缺失。void backtrack(int t){         if(t>n) {                  for(int i=1;i<=n;i++)                          printf(“%d “,x[i]);                  printf(“”);             }         else{                  for(int i=t;i<=n;i++){                          int ok=1;                          for(int j=  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]);                          }                  }                              }}上面的算法中， 红色代码部分123位置代码缺失， 请从如下选项中找到合适的代码。

答案: 1t，2  i ，3  ok=0

16、 符号三角形问题， 其解空间树是哪种？

答案: n叉树（这里n=2）

17、 子集和问题：给定n个不同的正整数，已知其和大于c，要求找出一个子集使其和等于c。该问题除解空间树是子集树的回溯法外，还有解空间树是排列树的回溯算法，思考该问题， 从如下选项中找到关于该算法设计的正确的描述。

答案: 当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。;
剪枝条件:当路径上的数之和>c时剪枝

18、 回溯法的算法效率跟哪些因素有关？ 这里xk是分支上的取值。

答案: 满足隐约束函数和限界函数约束的所有xk的个数;
计算隐约束函数值的时间;
计算限界函数值的时间;
满足显约束的xk的个数。

19、 回溯法中，剪枝函数能够剪掉的分支越多，算法效率就越高。因此，我们在设计回溯法时，就要设计剪枝函数能够剪掉尽量多的分支。

答案: 错误

第六章 分支限界法 第六单元测试

1、 分支限界法与回溯法的不同点体现在哪些方面？（1）求解目标不同，分支限界法可求最优解或满足条件的一个解，而回溯法可求最优解或满足条件的所有解（2）搜索方式不同， 回溯法是以深度优先状态生成树法搜索解空间树，分支限界法则以广度优先或最小耗费（最大效益）优先的状态生成树法搜索解空间树。（3） 同一个问题在使用回溯法或分支限界法时，该问题的解空间树的结构不同（4）  回溯法与分支限界法，构造最优解的方式不同。从上述选项中找出答案。

答案: （1）（2）（4）

2、  分支限界法中，扩展出的孩子结点在入队时，存储该孩子结点的父结点的地址和左孩子标志。其目的是什么？

答案: 为了构造最优解

3、 在队列式分支限界法解决装载问题时， 为什么在其改进算法中，每次进入左分支都要检查更新bestw，而不是等搜索到达叶子结点时才去更新bestw， 其目的是什么？

答案:  为了及早使右（0）分支剪枝函数生效。

4、 在队列式分支限界法中， 叶子结点不加入队列。而在优先队列式分支限界法中，叶子结点通常要加入到优先队列中。有下列2个解释：（1）      队列式分支限界法，活结点在队列中的顺序是按照搜索解空间树时扩展出该结点的先后顺序存放，每次从队首取出一个活结点成为新的扩展结点。扩展结点扩展出的儿子结点是叶子结点时，会将该叶子结点的值同当前最优值比较，检查更新最优值，叶子结点并不进入队列，等队列为空时，搜索结束，记录的当前最优值就是问题最优值。（2）      优先队列式分支限界法中， 当优先级的定义是限界函数时，扩展出的叶子结点进入队列， 这种做法主要是为了让搜索过程提前结束。也就是当从优先队列中取出一个活结点是叶子结点时，意味着现在优先队列中剩余的所有活结点其优先级都不大于该叶子结点的优先级，叶子结点的优先级等于最优值，算法结束，无论优先队列是否为空。根据其正确与否，给出答案

答案: （1）正确， （2）正确

5、 下面是优先队列式分支限界算法解0-1背包问题的部分主代码，分析代码将内的代码补齐。 
Templete<class Typew,class Typep>
Typep knap<Typew,Typep>::MaxKnapsack() { //优先队列分支限界法，返回最大价值，最优解bestx
H=new MaxHeap<HeapNode<Typep,Typew>>(1000);//定义最大堆的容量为1000
bestx=new int[n+1];
int i=1;
E=0;
cw=cp=0;
Typep bestp=0;
Typep up=Bound(1）； 
while (         1            ) 
{     
  Typew wt = 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（int j=n;j>0;j–）{
bestx[j]=E->lchild;
E=E->parent;
}
return cp;
}

答案: 1i<n+1 , 2besp=cp+p[i]

6、 阅读该单元测试中关于0-1背包问题的优先队列分支限界算法代码，问左分支的剪枝条件是什么？右分支的剪枝条件是什么？从代码中找到命令行，使用原代码回答问题。

答案: 左分支： wt<=c,   右分支：up>bestp

7、 优先队列式分支限界法解决0-1背包问题时，下面描述正确的是

答案: 左孩子结点的优先级等于父结点的优先级;
右孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值

8、 回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)),  h(n)是解空间树的深度。

答案: 错误

9、  在队列式分支限界法解决装载问题时， 在队列中加入一个-1标志， 该标志所起的作用是表示其后的活结点在解空间树中的层数比-1之前的活结点更深一层，或者说是同层活结点的结束标志。

答案: 正确

10、 下面是一个布线问题,  S表示布线的起点，O表示布线的终点， 假定布线只能垂直、或水平布线，从一个点按照上、下、左、右的优先顺序可往四个方向布线， “#”是障碍不能通过。已知从一个位置向其上、下、左、右四个相邻位置布线的线路长度为1。 使用队列式分支限界法解决该问题， 问从S到O的最短布线长度？ ###S##o#######
答案: 8

第七章 概率算法 第七单元测试

1、 有这样一种算法，运行一次可能找不到问题的解， 运行多次就一定能找到问题的解，且运行次数有界，这种算法是？

答案: 拉斯维加斯算法

2、 有这样一种算法，运行一次一定能找到问题的解，有时不知其是否正确，可以确定的是该解高概率（大于50%）是正确的。这种算法是？

答案: 蒙特卡洛算法

3、 有一个问题的蒙特卡洛算法，给定一个实例，已知运行一次其答案是错误的概率是1/8, 现运行k次该算法，其答案一直不变， 问该答案的正确率是？

答案: 1-(1/8)^k

4、 一致的p正确的偏y0的蒙特卡洛算法， 下面解释不正确的是?

答案: 运行蒙特卡洛算法p次， 至少有一次是正确的。

5、  pollard算法找到一个整数因子的时间复杂性是？

答案: O()

6、 n=12皇后问题的三种不同的解决方案：回溯法、拉斯维加斯算法、 拉斯维加斯算法+回溯法。对于给定的一个实例，(1)平均耗费时间最少的是那种方案？，(2)平均耗费时间最多的是那种方案？

答案: (1)拉斯维加斯+回溯   (2) 回溯法

7、 舍伍德算法思想是通过引入随机化策略将确定性算法改造为随机算法，打破原来确定性算法在某些实例情况下， 其时间复杂性必然远高于平均时间复杂性的规律。下面哪些算法可以应用舍伍德算法思想？

答案: 快速排序算法;
线性时间选择算法;
跳跃表

8、 计算机中的随机数是伪随机的， 因为它是具有一定规律的，是按公式计算出来的。该说法正确吗？

答案: 正确

9、 素数测试问题的蒙特卡洛算法，n是一个待判定正整数。当 n是素数时， 有时会被判定为非素数。该说法正确吗?

答案: 错误

10、 数值概率算法求π的算法， 是用半径为1的圆外接一个正方形，然后模拟向正方形中随机投放n个点， 计数落在圆内的点的个数为k，则π的近似值为
答案: (以下答案任选其一都对)4k/n;
4*k/n

11、 在分治法中讲到快速排序，如果每次使用partion函数导致分组出现严重不平衡情况下，算法效率不高，最坏情况下的时间复杂度为O（n^2）, 通过改造partition函数， 也就是每次随机选择一个元素作为划分基准，这样会很好地改善算法的性能， 这种算法思想是？

答案: 舍伍德算法

12、 有人说可以设计蒙特卡洛算法去猜硬币的反正面问题，该说法是否正确？

答案: 错误

第八章 NP完全性理论 第八单元测试

1、 下面哪个问题不是NPC问题 

答案: 最小生成树问题

2、 请从下列选项中找出正确的P问题与NP问题的关系

答案:

3、 NP问题是确定性算法不能在多项式时间复杂性解决的可判定问题

答案: 错误

4、 一个NPC问题，首先是NP问题，另外所有的其他NP问题都能在多项式时间复杂性规约为该问题

答案: 正确

5、 研究NPC 问题的意义， 一旦一个NPC问题找到了多项式时间复杂性的确定性算法，那么所有的NPC问题都找到了多项式时间复杂性的确定性算法。

答案: 正确

6、 NP难问题未必是NP问题

答案: 正确

7、 一个人 正站在门口，让你猜他（她）是否要出门？， 该问题是不可判定问题，该观点是否正确？  

答案: 正确

不知道怎么购买？点此查看购买教程！