【答案】《算法设计与分析》(信息工程大学网络空间安全学院)章节期末慕课答案

【答案】《算法设计与分析》(信息工程大学网络空间安全学院)章节期末慕课答案有些题目顺序不一致，下载后按键盘ctrl+F进行搜索1.算法概述算法基础单元测试1.单选题：

选项：

A、正确

B、错误

C、

D、

E、

F、

答案：【正确】2.单选题：算法分析中，记号O表示（）。

选项：

A、渐进下界

B、渐进上界

C、渐进同阶

D、渐进紧上界

E、渐进紧下界

答案：【渐进上界】3.单选题：

选项：

A、

B、

C、

D、

答案：【】4.单选题：函数，按照渐进时间复杂度从小到大的顺序是（）。

选项：

A、①②③④⑤

B、②④①③⑤

C、⑤③①④②

D、①②④③⑤

答案：【②④①③⑤】5.多选题：以下哪些是算法的特征。

选项：

A、确定性

B、有穷性

C、可行性

D、0个或1个以上的输入

E、1个以上的输出

答案：【确定性;有穷性;可行性;0个或1个以上的输入;1个以上的输出】6.多选题：关于下面示例算法的基本操作及时间复杂度，下列说法正确的有：

选项：

A、i＜=n,O(n)

B、k++,O(n)

C、i+=2,O(n)

D、k=1000,O(1)

E、i+=2,O(1)

F、k++,O(1)

答案：【i＜=n,O(n);k++,O(n);i+=2,O(n)】7.多选题：评价算法好坏的准则有（）。

选项：

A、正确性

B、简单性

C、最优性

D、空间复杂度

E、时间复杂度

答案：【正确性;简单性;最优性;空间复杂度;时间复杂度】8.多选题：关于算法分析的说法中，不正确的是（）。

选项：

A、算法分析包括对算法的数据结构的复杂度的分析

B、算法分析包括对算法的时间效率进行分析

C、算法分析包括对算法的空间效率进行分析

D、算法分析包括对算法的代码存储空间的分析

答案：【算法分析包括对算法的数据结构的复杂度的分析;算法分析包括对算法的代码存储空间的分析】9.单选题：算法和程序都必须是有穷的

选项：

A、正确

B、错误

答案：【错误】10.单选题：设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间，p(I)表示输入I出现的概率，则算法的平均情况下时间复杂度A(n)=∑I∈Dnt(I)p(I)。

选项：

A、正确

B、错误

答案：【正确】2.递归算法递归算法单元测试1.单选题：一个递归算法必须包括（）。

选项：

A、递归部分

B、递归部分和结束条件

C、迭代部分

D、结束条件和迭代部分

答案：【递归部分和结束条件】2.单选题：将递归算法转换成对应的非递归算法时，通常需要使用（）。

选项：

A、栈

B、队列

C、链表

D、树

答案：【栈】3.单选题：下列与递归有关的数据结构是（）。

选项：

A、栈

B、队列

C、二叉树

D、图

答案：【栈】4.单选题：递归法求解斐波那契数列F(n)=F(n-1)+F(n-2)，时间复杂度是（）。

选项：

A、O(n)

B、O(2^n)

C、O(n2^n)

D、以上都不对

答案：【O(2^n)】5.单选题：关于递归函数，以下叙述错误的是（）。

选项：

A、递归函数是自己调用自己

B、递归函数的运行速度很快

C、递归函数占用较多的存储空间

D、递归函数的运行速度一般比较慢

答案：【递归函数的运行速度很快】6.单选题：下列（）算法不可以用递归实现。

选项：

A、二叉树的中序遍历

B、二叉树的层序遍历

C、全排列问题

D、求阶乘问题

答案：【二叉树的层序遍历】7.多选题：有关递归算法，以下说法正确的是（）。

选项：

A、算法简洁，容易理解

B、有边界值

C、有递归关系

D、递归算法的深度不能过大

答案：【算法简洁，容易理解;有边界值;有递归关系;递归算法的深度不能过大】8.单选题：递归函数的调用次数必须是有限的。

选项：

A、正确

B、错误

答案：【正确】9.递归算法x(x(8))需要调用()次函数x(intn)?voidMain(string[]args){inti;i=x(x(8));}staticintx(intn){if(n＜=3)return1;elsereturnx(n-2)+x(n-4)+1;}

答案：【18】3.分治法分治法单元测试1.单选题：使用分治法求解不需要满足的条件是（）。

选项：

A、子问题的规模相同

B、子问题在规模较小时容易求解

C、子问题的解可以合并

D、原问题和子问题使用相同的方法求解

答案：【子问题的规模相同】2.单选题：分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。该过程中要求原问题和子问题规模_____，问题性质______。

选项：

A、相同相同

B、相同不同

C、不同相同

D、不同不同

答案：【不同相同】3.单选题：用分治法解决一个规模为N的问题。下列（）方法是最慢的。

选项：

A、每步将问题分成规模均为N/3的2个子问题，且分解与合并的步骤耗时O(N)

B、每步将问题分成规模均为N/3的2个子问题，且分解与合并的步骤耗时O(NlogN)

C、每步将问题分成规模均为N/2的3个子问题，且分解与合并的步骤耗时O(N)

D、每步将问题分成规模均为N/3的3个子问题，且分解与合并的步骤耗时O(NlogN)

答案：【每步将问题分成规模均为N/2的3个子问题，且分解与合并的步骤耗时O(N)】4.单选题：在堆排序、直接插入排序、归并排序、快速排序、冒泡排序、希尔排序、基数排序这7种排序算法中，有（）种是基于分治法的。

选项：

A、2

B、3

C、4

D、7

答案：【2】5.单选题：用分治法解决一个规模为N的问题。若每步将问题分成规模均为N/5的4个子问题，且分解与合并解的步骤耗时O(logN)，则整个算法的时间复杂度为（）。

选项：

A、O(N)

B、O(logN)

C、O(log2N)

D、O(N^(log4/log5))

答案：【O(N^(log4/log5))】6.单选题：有关分治法的描述，不正确的是（）。

选项：

A、有些问题重点在分解步骤，有些问题重点在合并步骤。

B、分治法的第二个步骤，通常采用递归方法求解。

C、分治法在分解步骤中，只有把问题分解为规模均衡的子问题，效率才会更高。

D、大整数乘法直接使用分治法，效率不能提升。

答案：【分治法在分解步骤中，只有把问题分解为规模均衡的子问题，效率才会更高。】7.多选题：以下关于分治法的描述，正确的是（）。

选项：

A、通过降低子问题的规模，可以提高分治法的效率

B、通过减少子问题的个数，可以提高分治法的效率

C、分治与递归密不可分

D、分治法是一种分而治之的算法，通过把大问题分解为若干规模较小的问题进行求解

答案：【通过降低子问题的规模，可以提高分治法的效率;通过减少子问题的个数，可以提高分治法的效率;分治与递归密不可分;分治法是一种分而治之的算法，通过把大问题分解为若干规模较小的问题进行求解】8.多选题：可以从哪些方面降低分治法的时间复杂度?

选项：

A、减少子问题个数

B、增加子问题个数

C、减少子问题规模

D、增加子问题规模

答案：【减少子问题个数;减少子问题规模】5.贪心法贪心法单元测试1.单选题：任何一个无向连通图的最小生成树（）。

选项：

A、正确

B、错误

C、有一棵或多棵

D、只有一棵

E、一定有多棵

F、可能不存在

答案：【错误】2.单选题：贪心法求解最优装载问题的贪心选择策略是（）。

选项：

A、重量大的物品先装

B、单位重量价值大的物品先装

C、重量小的物品先装

D、价值大的物品先装

答案：【重量小的物品先装】3.单选题：贪心算法是一种只顾眼前最优，而难以顾及全局最优的算法，对于贪心算法，下面说法错误的是（）。

选项：

A、不能保证最后求得的解是最优的

B、贪心法的正确性需要证明

C、贪心选择策略单一，结果也单一

D、算法实现过程中，通常用到辅助算法：排序

答案：【贪心选择策略单一，结果也单一】4.单选题：一棵哈夫曼树共有213个结点，对其进行哈夫曼编码，共能得到（）个不同的编码。

选项：

A、107

B、108

C、214

D、215

答案：【107】5.单选题：一个问题可用动态规划算法或贪心算法求解的关键特征是问题具有（）。

选项：

A、重叠子问题

B、构造最优解

C、贪心选择性质

D、最优子结构性质

答案：【最优子结构性质】6.单选题：活动安排问题的最优解一定包含结束时间最早的活动。

选项：

A、正确

B、错误

答案：【错误】7.单选题：贪心法可以得到多机调度问题的最优解。

选项：

A、正确

B、错误

答案：【错误】8.单选题：用贪心法解决找零钱问题，能否得到最优解与零钱的面值有关。

选项：

A、动机

B、情绪

C、正确

D、认知

E、行为

F、错误

答案：【正确】9.单选题：贪心法只能用于求问题的最优解。

选项：

A、正确

B、错误

C、正确

D、错误

答案：【错误】10.单选题：哈夫曼树的根结点的权重值是所有叶子结点的权重值的和。

选项：

A、正确

B、错误

答案：【正确】4.动态规划动态规划单元测试1.单选题：动态规划求解最长公共子序列问题的时间复杂度是（）

选项：

A、O(mn)

B、(n*2^m)

C、O(m*2^n)

D、O(n)

答案：【O(mn)】2.单选题：在动态规划的四个解题步骤中，哪个不是必须的（）。

选项：

A、分析问题是否具有最优子结构性质

B、采用自底向上的方式求解最优值

C、利用最优值，求最优解

D、递归地定义最优值

答案：【利用最优值，求最优解】3.单选题：在动态规划中，我们要推导出一个子问题的解与其他子问题解的递推关系。要将这种关系转换为自底向上的动态规划算法，我们需要以正确的顺序填写子问题解的表格，使得在解任一子问题时，所有它需要的子问题都已经被解决了。在下列关系式中，（）是不可能被计算的。

选项：

A、A(i,j)=min(A(i?1,j),A(i,j?1),A(i?1,j?1))

B、A(i,j)=F(A(min{i,j}?1,min{i,j}?1),A(max{i,j}?1,max{i,j}?1))

C、A(i,j)=F(A(i,j?1),A(i?1,j?1),A(i?1,j+1))

D、A(i,j)=F(A(i?2,j?2),A(i+2,j+2))

答案：【A(i,j)=F(A(i?2,j?2),A(i+2,j+2))】4.单选题：使用动态规划求解0-1背包问题（背包容量为c，物品个数为n），如果只需要最优值，空间复杂度最低为（）。

选项：

A、O(cn)

B、O(n)

C、O(c)

D、O(n^2)

答案：【O(c)】5.单选题：适合用分治法求解，而不适合用动态规划求解的问题是（）。

选项：

A、棋盘覆盖问题

B、斐波那契数列问题

C、0-1背包问题

D、数字三角形问题

答案：【棋盘覆盖问题】6.多选题：以下关于动态规划的描述，正确的是（）。

选项：

A、最优子结构是指问题的最优解包含子问题的最优解

B、重叠子问题是指某些子问题需要使用多次

C、动态规划与分治既有联系也有区别

D、备忘录是动态规划的一种算法实现方式

答案：【最优子结构是指问题的最优解包含子问题的最优解;重叠子问题是指某些子问题需要使用多次;动态规划与分治既有联系也有区别;备忘录是动态规划的一种算法实现方式】7.单选题：如果一个问题可以用动态规划算法解决，则总是可以在多项式时间内解决的。

选项：

A、正确

B、错误

答案：【错误】8.单选题：最优二叉搜索树的根结点一定是搜索概率最高的那个关键字。

选项：

A、正确

B、错误

答案：【错误】6.回溯法回溯法单元测试1.单选题：关于回溯法以下叙述不正确的是（）。

选项：

A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解

B、回溯法是基于深度优先遍历的搜索算法

C、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

D、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯

答案：【回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径】2.单选题：下面（）函数是回溯法中为避免无效搜索采取的策略。

选项：

A、递归函数

B、剪枝函数

C、随机数函数

D、搜索函数

答案：【剪枝函数】3.单选题：回溯法中常见的两类典型的解空间树是子集树和排列树，遍历具有n!个叶结点的排列树需要（）的计算时间。

选项：

A、O(n!)

B、O(logn)

C、O(n^2)

D、O(2^n)

答案：【O(n!)】4.单选题：回溯法在问题解空间树上的搜索方式是（）。

选项：

A、深度优先

B、广度优先

C、最小耗费优先

D、活结点优先

答案：【深度优先】5.多选题：有关问题的解空间树，下面描述正确的是（）。

选项：

A、解空间树是对问题的所有可能解的一种树型结构组织形式

B、子集树和排列树是常见的两种解空间树

C、当问题的解满足某种性质的子集时，其对应的解空间树是子集树

D、当问题的解满足某种性质的排列时，其对应的解空间树是排列树

答案：【解空间树是对问题的所有可能解的一种树型结构组织形式;子集树和排列树是常见的两种解空间树;当问题的解满足某种性质的子集时，其对应的解空间树是子集树;当问题的解满足某种性质的排列时，其对应的解空间树是排列树】6.多选题：下面是回溯法解题步骤的是（）。

选项：

A、以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索

B、针对所给问题，定义问题的解空间

C、确定最优子结构的性质

D、确定易于搜索的解空间结构

答案：【以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索;针对所给问题，定义问题的解空间;确定易于搜索的解空间结构】7.多选题：关于回溯法以下叙述不正确的是（）。

选项：

A、回溯法是一种搜索算法

B、用限界函数在扩展结点处剪去不满足可行解的子树

C、用约束函数剪去得不到最优解的子树

D、回溯法在搜索过程中，边判断边搜索

答案：【用限界函数在扩展结点处剪去不满足可行解的子树;用约束函数剪去得不到最优解的子树】7.分支限界分支限界单元测试1.单选题：在优先队列式分支限界法中，活结点表的组织形式是（）。

选项：

A、小根堆

B、大根堆

C、栈

D、优先队列

答案：【优先队列】2.单选题：采用优先队列式分支限界法解旅行售货员问题时，活结点表的组织形式是（）。

选项：

A、最小堆

B、最大堆

C、栈

D、队列

答案：【最小堆】3.单选题：分支限界法与回溯法都是在问题的解空间树上搜索问题的解，二者（）。

选项：

A、求解目标不同，搜索方式相同

B、求解目标不同，搜索方式也不同

C、求解目标相同，搜索方式不同

D、求解目标相同，搜索方式也相同

答案：【求解目标不同，搜索方式也不同】4.单选题：采用优先队列式分支限界法求解0-1背包问题时，活结点表的组织形式是（）。

选项：

A、小根堆

B、大根堆

C、栈

D、队列

答案：【大根堆】5.单选题：分支限界法在问题的解空间树中，按（）搜索策略，从根结点出发搜索解空间树。

选项：

A、广度优先

B、活结点优先

C、扩展结点优先

D、深度优先

答案：【广度优先】6.多选题：用分支限界法求解问题的步骤是（）。

选项：

A、确定易于搜索的解空间结构

B、针对所给问题，定义问题的解空间

C、以广度优先或以最小耗费（最大收益）优先的方式搜索解空间树，并在搜索过程中用剪枝函数避免无效搜索

D、定义最优子结构

答案：【确定易于搜索的解空间结构;针对所给问题，定义问题的解空间;以广度优先或以最小耗费（最大收益）优先的方式搜索解空间树，并在搜索过程中用剪枝函数避免无效搜索】7.多选题：分支限界法与回溯法的不同点是（）。

选项：

A、搜索方式不同

B、对结点的扩展方式不同

C、存储空间的要求不同

D、求解目标不同

答案：【搜索方式不同;对结点的扩展方式不同;存储空间的要求不同;求解目标不同】8.单选题：在分支限界法中，每个活结点只有一次机会成为扩展结点。

选项：

答案：【】8.概率算法概率算法单元测试1.单选题：对于拉斯维加斯算法，下面说法不正确的是（）。

选项：

A、不会得到不正确的解

B、有时找不到问题的解

C、找到正确解的概率随算法计算时间的增加而提高

D、用同一拉斯维加斯算法对同一问题求解多次，对求解失败的概率没有影响

答案：【用同一拉斯维加斯算法对同一问题求解多次，对求解失败的概率没有影响】2.单选题：拉斯维加斯算法找到的解一定是（）。

选项：

A、不确定的

B、正确的

C、不正确的

D、局部最优的

答案：【正确的】3.单选题：对于舍伍德算法，下面说法不正确的是（）。

选项：

A、总能求得问题的一个解

B、不一定能求得问题的解

C、所求得的解总是正确的

D、将确定性算法引入随机性改造成舍伍德算法，可消除或减少问题对于好坏实例间的差别

答案：【不一定能求得问题的解】4.单选题：（）的一个基本特征是用同一概率算法求解问题的同一实例两次，得到的结果可能完全不同。

选项：

A、贪心算法

B、回溯算法

C、概率算法

D、近似算法

答案：【概率算法】5.单选题：弗洛伊德算法采用的算法设计策略是（）。

选项：

A、穷举法

B、动态规划

C、贪心法

D、回溯法

答案：【动态规划】6.多选题：蒙特卡罗算法能够用于计算下列哪些应用（）。

选项：

A、计算pi值

B、计算定积分

C、找主元素

D、求最大子段和

答案：【计算pi值;计算定积分;找主元素】7.单选题：概率算法通常用于解决P类问题。

选项：

答案：【】9.算法综合应用综合应用单元测试1.单选题：下列哪个算法可以求解所有点对间的最短路径问题且算法更为简洁？

选项：

A、迪杰斯特拉算法

B、弗洛伊德算法

C、贝尔曼福特算法

D、SPFA算法

答案：【弗洛伊德算法】2.单选题：动态规划求解最大子段和问题（序列有n个元素）的时间复杂度为（）。

选项：

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n2)

答案：【O(n)】3.单选题：分治法求解最大子段和问题（序列有n个元素）的时间复杂度为（）。

选项：

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n2)

答案：【O(nlogn)】4.多选题：关于回溯法和分支限界算法，下列说法正确的是（）。

选项：

A、回溯与分支限界的共同点在于，都是对问题的解空间树进行搜索的算法设计策略

B、回溯是一种基于广度优先搜索的方法

C、回溯通常采用递归方式实现，也可以用迭代实现

D、分支限界通常采用递归方式实现

答案：【回溯与分支限界的共同点在于，都是对问题的解空间树进行搜索的算法设计策略;回溯通常采用递归方式实现，也可以用迭代实现】5.多选题：以下（）算法可以求解最大子段和问题。

选项：

A、贪心法

B、动态规划

C、穷举法

D、分治法

答案：【动态规划;穷举法;分治法】6.多选题：关于动态规划和贪心算法，下列说法正确的是（）。

选项：

A、都是用于求解最优化问题的算法设计策略

B、适合求解的问题都具有最优子结构性质

C、动态规划求解问题的效率更高

D、动态规划求解问题不需要把所有可能的子问题都求解出来

答案：【都是用于求解最优化问题的算法设计策略;适合求解的问题都具有最优子结构性质】7.单选题：资源分配问题既可以用动态规划求解，也可以用回溯、分支限界求解。

选项：

答案：【】期末考试期末考试1.单选题：在数字三角形问题中，假如从塔顶到塔底只有一条最优路径，为15-20-5-7-9-16，以下说法正确的是（）。

选项：

A、从20到塔底的最优路径可能不是20-5-7-9-16

B、从20到塔底的最优路径一定是20-5-7-9-16

C、从5到塔底的最优路径可能不是5-7-9-16

D、以上都不对

答案：【从20到塔底的最优路径一定是20-5-7-9-16】2.单选题：（）的一个基本特征是用同一概率算法求解问题的同一实例两次，得到的结果可能完全不同。

选项：

A、贪心算法

B、回溯算法

C、概率算法

D、近似算法

答案：【概率算法】3.单选题：下面（）函数是回溯法中为避免无效搜索采取的策略。

选项：

A、递归函数

B、剪枝函数

C、随机数函数

D、搜索函数

答案：【剪枝函数】4.单选题：二分搜索算法是利用（）实现的算法。

选项：

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

答案：【分治策略】5.单选题：采用优先队列式分支限界法求解0-1背包问题时，活结点表的组织形式是（）。

选项：

A、小根堆

B、大根堆

C、栈

D、队列

答案：【大根堆】6.单选题：哪个问题不适合用回溯法（）。

选项：

A、装载问题

B、0-1背包问题

C、图的m着色

D、快速排序问题

答案：【快速排序问题】7.单选题：以下（）可以求解单源最短路径。

选项：

A、普里姆算法

B、哈夫曼算法

C、迪杰斯特拉算法

D、克鲁斯卡尔算法

答案：【迪杰斯特拉算法】8.单选题：采用优先队列式分支限界法解旅行售货员问题时，活结点表的组织形式是（）。

选项：

A、最小堆

B、最大堆

C、栈

D、队列

答案：【最小堆】9.单选题：贪心法求解部分背包问题的贪心选择策略是（）。

选项：

A、单位重量价值大的物品先装

B、价值大的物品先装

C、重量小的物品先装

D、以上都不对

答案：【单位重量价值大的物品先装】10.单选题：在对问题的解空间树进行搜索的方法中，一个结点最多有一次机会成为活结点的是（）。

选项：

A、回溯法

B、分支限界法

C、回溯法和分支限界法

D、回溯法求解子集树问题

答案：【分支限界法】11.单选题：以下有关最优二叉搜索树的描述，正确的是（）。

选项：

A、最优二叉搜索树可以通过动态规划方法获得

B、最优二叉搜索树是在所有二叉搜索树中，树的高度最短的

C、最优二叉搜索树可以通过贪心法求解

D、最优二叉搜索树是唯一的

答案：【最优二叉搜索树可以通过动态规划方法获得】12.单选题：已知序列X=AACBABA，序列Y=BDCABA，则它们的最长公共子序列是（）。

选项：

A、CABA

B、ABAB

C、ABA

D、BAB

答案：【CABA】13.单选题：一个问题可用动态规划算法或贪心算法求解的关键特征是问题具有（）。

选项：

A、重叠子问题

B、构造最优解

C、贪心选择性质

D、最优子结构性质

答案：【最优子结构性质】14.单选题：贪心法求解最优装载问题的贪心选择策略是（）。

选项：

A、重量大的物品先装

B、单位重量价值大的物品先装

C、重量小的物品先装

D、价值大的物品先装

答案：【重量小的物品先装】15.单选题：分治法求解最大子段和问题（序列有n个元素）的时间复杂度为（）。

选项：

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n2)

答案：【O(nlogn)】16.单选题：矩阵A1=20*10，A2=10*15，两个矩阵相乘需要的乘法次数是（）。

选项：

A、1500

B、2000

C、300

D、3000

答案：【3000】17.单选题：归并排序的最坏时间复杂度可以表示为（）。

选项：

A、T(n)=2T(n/2)+O(n)

B、T(n)=T(n-1)+O(n)

C、T(n)=2T(n/2)+O(1)

D、以上都不对

答案：【T(n)=2T(n/2)+O(n)】18.单选题：序列{2,9,3,5,8,4,7,6}的最长不上升子序列长度为（）。

选项：

A、3

B、4

C、5

D、8

答案：【4】19.单选题：在0-1背包问题中，已知背包容量为c，有4个物品，第i个物品的重量为wi，价值为vi，最优解为（x1,x2,x3,x4），以下说法正确的是（）。

选项：

A、（x1,x2,x3)是背包容量为c-x4w4，物品为1、2、3号物品所对应的0-1背包问题的最优解

B、（x1,x2,x3)是背包容量为c，物品为1、2、3号物品所对应的0-1背包问题的最优解

C、（x1,x3)是背包容量为c，物品为1、3号物品所对应的0-1背包问题的最优解

D、以上都不对

答案：【（x1,x2,x3)是背包容量为c-x4w4，物品为1、2、3号物品所对应的0-1背包问题的最优解】20.单选题：一个递归算法必须包括（）。

选项：

A、递归部分

B、递归部分和结束条件

C、迭代部分

D、结束条件和迭代部分

答案：【递归部分和结束条件】21.单选题：有5个台阶，可以一步走1个台阶，也可以1步走2个台阶，可能的走法共有（）种。

选项：

A、5

B、3

C、8

D、13

答案：【8】22.单选题：求正整数n的划分总数时，定义函数q(n,m)表示在n的所有划分中，最大加数不大于m的划分个数，那么q(6,4)为（）。

选项：

A、2

B、7

C、8

D、9

答案：【9】23.单选题：序列（2，-5,8,9，-3,4）的最大子段和为（）。

选项：

A、17

B、18

C、19

D、20

答案：【18】24.单选题：用分治法解决一个规模为N的问题。若每步将问题分成规模均为N/5的4个子问题，且分解与合并解的步骤耗时O(logN)，则整个算法的时间复杂度为（）。

选项：

A、O(N)

B、O(logN)

C、O(log2N)

D、O(Nlog4/log5)

答案：【O(Nlog4/log5)】25.单选题：回溯法解n皇后问题，对应的解空间树是（）。

选项：

A、子集树

B、排列树

C、子集树或排列树

D、广度优先生成树

答案：【子集树或排列树】26.单选题：把两个长度为n的有序序列合并为一个长度为2n的有序序列，最坏情况下需要的比较次数为（）。

选项：

A、n

B、nlogn

C、2n-1

D、n^2

答案：【2n-1】27.单选题：使用分治法求解不需要满足的条件是（）。

选项：

A、子问题的规模相同

B、子问题在规模较小时容易求解

C、子问题的解可以合并

D、原问题和子问题使用相同的方法求解

答案：【子问题的规模相同】28.单选题：贪心算法从初始阶段开始，每一个阶段总是作一个使（）的贪心选择。

选项：

A、全局最优

B、局部最大

C、局部最小

D、局部最优

答案：【局部最优】29.单选题：拉斯维加斯算法找到的解一定是（）。

选项：

A、不确定的

B、正确的

C、不正确的

D、局部最优的

答案：【正确的】30.单选题：分支限界法在问题的解空间树中，按（）搜索策略，从根结点出发搜索解空间树。

选项：

A、广度优先

B、活结点优先

C、扩展结点优先

D、深度优先

答案：【广度优先】31.单选题：快速排序的平均时间复杂度可以表示为（）。

选项：

A、T(n)=2T(n/2)+O(n)

B、T(n)=O(n)+

C、T(n)=T(n-1)+O(n)

D、以上都不对

答案：【T(n)=O(n)+】32.单选题：在序列{3,8,12,14,23,27,30}中采用二分搜索法查找2，需要的比较次数是（）。

选项：

A、1

B、4

C、3

D、7

答案：【3】33.单选题：（）能够求得问题得解，但却无法有效地判定解的正确性。

选项：

A、数值概率算法

B、蒙特卡罗算法

C、拉斯维加斯算法

D、舍伍得算法

答案：【蒙特卡罗算法】34.单选题：回溯法解批处理作业调度问题时，对应的解空间树是（）。

选项：

A、子集树

B、排列树

C、深度优先生成树

D、广度优先生成树

答案：【排列树】35.单选题：求正整数n的划分总数时，定义函数q(n,m)表示在n的所有划分中，最大加数不大于m的划分个数，下面描述中错误的是（）。

选项：

A、当m=1时，q(n,m)=1

B、当n=1时，q(n,m)=1

C、当n=m>1时，q(n,m)=1

D、当n=m>1时，q(n,m)=1+q(n,n-1)

答案：【当n=m>1时，q(n,m)=1】36.单选题：任何一个无向连通图的最小生成树（）。

选项：

A、有一棵或多棵

B、只有一棵

C、一定有多棵

D、可能不存在

答案：【有一棵或多棵】37.单选题：在队列式分支限界法中，活结点表的组织形式是（）。

选项：

A、小根堆

B、大根堆

C、栈

D、先进先出的队列

答案：【先进先出的队列】38.单选题：动态规划求解最大子段和问题（序列有n个元素）的时间复杂度为（）。

选项：

A、O(1)

B、O(n)

C、O(nlogn)

D、O(n2)

答案：【O(n)】39.多选题：评价算法好坏的准则有（）。

选项：

A、正确性

B、简单性

C、最优性

D、空间复杂度

E、时间复杂度

答案：【正确性;简单性;最优性;空间复杂度;时间复杂度】40.多选题：关于算法的正确性描述，正确的是（）。

选项：

A、算法的正确性是指该算法对问题的所有实例都可以得到正确的结果

B、算法的正确性需要进行证明

C、如果运行若干实例，算法都可以给出正确结果，则说明算法是正确的

D、算法的正确性是评价算法的一个重要方面

答案：【算法的正确性是指该算法对问题的所有实例都可以得到正确的结果;算法的正确性需要进行证明;算法的正确性是评价算法的一个重要方面】41.多选题：以下（）算法可以求解最大子段和问题。

选项：

A、贪心法

B、动态规划

C、穷举法

D、分治法

答案：【动态规划;穷举法;分治法】42.多选题：以下关于贪心法的描述，正确的是（）

选项：

A、贪心法简单且高效

B、贪心法不一定能得到最优解

C、选择正确的贪心选择策略很重要

D、贪心法是对当前所有选择进行判断后找出最好的

答案：【贪心法简单且高效;贪心法不一定能得到最优解;选择正确的贪心选择策略很重要】43.多选题：以下关于分治法的描述，正确的是（）。

选项：

A、通过降低子问题的规模，可以提高分治法的效率

B、通过减少子问题的个数，可以提高分治法的效率

C、分治与递归密不可分

D、分治法是一种分而治之的算法，通过把大问题分解为若干规模较小的问题进行求解

答案：【通过降低子问题的规模，可以提高分治法的效率;通过减少子问题的个数，可以提高分治法的效率;分治与递归密不可分;分治法是一种分而治之的算法，通过把大问题分解为若干规模较小的问题进行求解】44.多选题：在图中，如果v到w的最短路径是v经v1、v2、v3、…、vn到w点，以下描述正确的是（）。

选项：

A、从v到w的最短路径，可以得到v到该路径上其他任一点的最短路径

B、从v到w的最短路径，可以得到该路径上任一点到点w的最短路径

C、从v到w的最短路径，可以得到该路径上任意两点间的最短路径

D、两点间的最短路径满足最优子结构性质

答案：【从v到w的最短路径，可以得到v到该路径上其他任一点的最短路径;从v到w的最短路径，可以得到该路径上任一点到点w的最短路径;从v到w的最短路径，可以得到该路径上任意两点间的最短路径;两点间的最短路径满足最优子结构性质】45.多选题：回溯法求解n皇后问题的约束函数可能包含下列哪些选项？

选项：

A、不在同一列

B、不在同一对角线

C、不在同一行

D、任意三个棋子不共线

答案：【不在同一列;不在同一对角线;不在同一行】46.多选题：（）不能使用贪心法求解。

选项：

A、单源最短路径问题

B、n皇后问题

C、最小生成树问题

D、0-1背包问题

答案：【n皇后问题;0-1背包问题】47.多选题：以下算法中，（）是通过子问题的解得到原问题的解的。

选项：

A、贪心法

B、动态规划

C、穷举法

D、分治法

答案：【贪心法;动态规划;分治法】48.多选题：算法时间复杂度从实际计算机中抽取出来，只依赖于待解问题的（）。

选项：

A、规模

B、算法的输入

C、算法本身

D、计算机的性能

答案：【规模;算法的输入;算法本身】49.多选题：有关问题的解空间树，下面描述正确的是（）。

选项：

A、解空间树是对问题的所有可能解的一种树型结构组织形式

B、子集树和排列树是常见的两种解空间树

C、当问题的解满足某种性质的子集时，其对应的解空间树是子集树

D、当问题的解满足某种性质的排列时，其对应的解空间树是排列树

答案：【解空间树是对问题的所有可能解的一种树型结构组织形式;子集树和排列树是常见的两种解空间树;当问题的解满足某种性质的子集时，其对应的解空间树是子集树;当问题的解满足某种性质的排列时，其对应的解空间树是排列树】50.多选题：以比较操作为基本操作，对某序列求最大最小项，最坏时间复杂度最低的是（）。

选项：

A、淘汰赛法

B、分治法

C、逐一遍历法

D、先排序再找出最大和最小项

答案：【淘汰赛法;分治法】51.多选题：用分支限界法求解问题的步骤是（）。

选项：

A、确定易于搜索的解空间结构

B、针对所给问题，定义问题的解空间

C、以广度优先或以最小耗费（最大收益）优先的方式搜索解空间树，并在搜索过程中用剪枝函数避免无效搜索

D、定义最优子结构

答案：【确定易于搜索的解空间结构;针对所给问题，定义问题的解空间;以广度优先或以最小耗费（最大收益）优先的方式搜索解空间树，并在搜索过程中用剪枝函数避免无效搜索】52.多选题：最优子结构性质是（）具有的性质。

选项：

A、贪心法

B、动态规划

C、回溯法

D、分治法

答案：【贪心法;动态规划】53.多选题：在时间复杂度计算中，针对递推方程的计算方法有（）。

选项：

A、迭代法

B、递归树

C、主定理

D