算法分析与设计知到智慧树章节测试课后答案2024年秋山东财经大学

算法分析与设计知到智慧树章节测试课后答案2024年秋山东财经大学第一章单元测试

一个问题的同一实例可以有不同的表示形式

A:对B:错

答案:对同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

A:错B:对

答案:对问题的两个要素是输入和实例。

A:错B:对

答案:错算法与程序的区别是（）

A:输入B:确定性C:有穷性D:输出

答案:有穷性解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明

A:(3)(4)(1)(5)(2)B:(3)(1)(5)(4)(2)C:(3)(1)(4)(5)(2)D:(1)(2)(3)(4)(5)

答案:(3)(1)(5)(4)(2)下面说法关于算法与问题的说法错误的是（）。

A:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。B:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。C:证明算法不正确，需要证明对任意实例算法都不能正确处理。D:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。

答案:证明算法不正确，需要证明对任意实例算法都不能正确处理。下面关于程序和算法的说法正确的是（）。

A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。B:算法是一个过程，计算机每次求解是针对问题的一个实例求解。C:程序是算法用某种程序设计语言的具体实现。D:程序总是在有穷步的运算后终止。

答案:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。；算法是一个过程，计算机每次求解是针对问题的一个实例求解。；程序是算法用某种程序设计语言的具体实现。最大独立集问题和（）问题等价。

A:最大团B:稳定匹配问题C:最小顶点覆盖D:区间调度问题

答案:最大团；最小顶点覆盖给定两张喜欢列表，稳定匹配问题的输出是（

）

。

A:最大匹配B:没有不稳定配对C:完美匹配D:稳定匹配

答案:最大匹配；没有不稳定配对；完美匹配；稳定匹配问题变换的目的有（）。(1)复杂变简单(2)未知变已知(3)隐式变显式(4)难解变易解（5）以上都是。

A:（3）

B:（2）

C:（1）

D:（5）E:（4）

答案:（5）按照霍纳法则，计算p(x)=anxn

+an-1xn-1+…+a1x1+a0

的数量级为____。

A:nlogn

B:n

C:n^2

D:logn

答案:n

第二章单元测试

时间复杂度是指算法最坏情况下的运行时间。

A:对B:错

答案:对f(n)=3n3+7n2+4nlogn=O（n2）

A:对B:错

答案:错如果一个算法是多项式时间算法，该算法是有效的,是好算法。

A:错B:对

答案:对算法复杂度分析的两种基本方法为（

）和（

）。

A:结构化方法

面向对象方法B:几何复杂度

平均复杂度C:平摊复杂度

平滑复杂度D:事后统计

事前分析

答案:事后统计

事前分析下面程序的时间复杂度为（）

x=1fori=1ton

doforj=1toido

fork=1tojdo

x++

A:O(n^3)B:O(n^2)C:O(nlogn)D:O(n)

答案:O(n^3)对近似递增序列的线性表从小到大排序，使用哪种方法好？

A:归并排序B:快速排序C:堆排序D:插入排序

答案:插入排序顺序查找适合的数据结构是（）

A:压缩存储B:链式存储C:顺序存储D:散列存储

答案:链式存储；顺序存储给定n个元素的数组A，n=10^3,使用折半查找比使用顺序查找大约快___倍。

A:10^(3/2)

B:1000

C:10

D:100

答案:100

则f(n)的渐进性态f(n)=Ω(

)

A:100

B:n^2

C:n

D:1

答案:1

f=O(g)当且仅当g=Ω(f)

A:错B:对

答案:对

第三章单元测试

0-1背包问题的枚举算法的时间复杂度为O（2n）

A:对B:错

答案:错增量构造法生成子集前需要对集合中元素从小到大排列。

A:错B:对

答案:对分块查找一般设分块的长度是n/2.

A:对B:错

答案:错枚举法适用于问题的小规模实例。

A:错B:对

答案:对便于实现集合操作的子集生成算法是（）

A:二进制法B:位向量法C:增量构造法

答案:二进制法从所有候选答案中去搜索正确的解，这是

（）算法。

A:蛮力B:递推C:枚举

答案:枚举logn2=(

)(logn+5)

A:wB:oC:O

D:θ

答案:θ0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？

A:50B:60C:30D:40

答案:40分数拆分问题的枚举算法通过（）方法进行了优化。

A:减少枚举变量的值域B:优化数据结构C:优化数学模型D:减少枚举变量

答案:减少枚举变量的值域；优化数学模型；减少枚举变量下面那些算法的时间复杂度为O（）?

A:插入排序B:折半查找C:顺序查找D:冒泡排序E:折半插入排序

答案:插入排序；冒泡排序；折半插入排序A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是（）

A:n

B:100n

C:10n

D:n^2

答案:10n

冒泡排序的时间复杂度为Ω(n^2)

A:对B:错

答案:错

第四章单元测试

贪心算法总能找到可行解，但未必是最优解。

A:错B:对

答案:对贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。

A:错B:对

答案:对问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

A:对B:错

答案:对Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。

A:对B:错

答案:对贪心算法基本要素有（

）和最优子结构性质。

A:独立子问题性质B:重叠子问题性质C:贪心选择性质D:分解合并性质

答案:贪心选择性质下面不是证明贪心算法证明方法的有（）。

A:优化B:界C:交换论证D:领先

答案:优化最小生成树问题可以使用的算法有（

）

A:KruskalB:PrimC:DijkstraD:Solim

答案:Kruskal；Prim；Solim区间问题包含()

A:区间调度B:区间选点C:区间划分D:区间覆盖

答案:区间调度；区间选点；区间划分；区间覆盖负权的单源最短路问题可以使用Dijkstra算法求解

A:对B:错

答案:错设C是一个环，f是C中的最大边，那么最小生成树中肯定包含f。

A:对B:错

答案:错

第五章单元测试

正推是从小规模的问题推解出大规模间题的一种方法。

A:错B:对

答案:对一般来说，递归的效率高于递推。

A:错B:对

答案:错从大规模问题逐步化为小规模问题的算法是（）

A:递归B:正推C:倒推D:迭代

答案:递归求解高阶递推方程一般使用（）迭代方法

A:直接迭代B:换元迭代C:差消迭代

答案:差消迭代递归函数的要素是（）

A:边界条件B:输入C:迭代D:递归方程

答案:边界条件；递归方程递归变为非递归的方法有（）

A:尾递归B:模拟栈C:循环D:递推

答案:尾递归；模拟栈；递推T(n)=T(n-1)+n，T(1)=1，则T(n)=（）

A:θ(n^2)B:n(n+1)/2C:Ω(n^2)D:O(n^2)

答案:θ(n^2)；n(n+1)/2；Ω(n^2)；O(n^2)

递归一般用于解决问题有（）

A:数据的定义是按递归定义的B:数据的结构形式是按递归定义的C:迭代问题D:问题解法按递归实现

答案:数据的定义是按递归定义的；数据的结构形式是按递归定义的；问题解法按递归实现主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方程，则下列关于方程中的约束中不准确的是？设

A:若f(n)=O(x)，则T(n)=Θ(xlogn)B:若对于常数e>0，f(n)=O(y)，则T(n)=Θ(x)C:对于系数a，必须满足a>=1D:对于系数b，必须满足b>1

答案:若f(n)=O(x)，则T(n)=Θ(xlogn)，则T(n)=（）

A:Ω(n^3)B:O(nlogn)C:O(n)D:Θ(n^2)

答案:Θ(n^2)循环用于重复性的工作。循环体的特点是：“以不变应万变”。

A:对B:错

答案:对

第六章单元测试

分治法分解的子问题与原问题形式相同。

A:对B:错

答案:对N个元素排序的时间复杂度不可能是线性时间。

A:错B:对

答案:错三分法的判定树是三叉树。

A:对B:错

答案:对减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)

A:错B:对

答案:错设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(

)法。

A:合并排序B:基数排序C:快速排序D:冒泡排序

答案:冒泡排序堆排序的时间复杂度是O（）。

A:O（n）B:O（2n）C:O（nlogn）D:O（n2）

答案:O（nlogn）改进分治算法的方法有（

）和改进划分的对称性。

A:拟阵原理B:减少子问题数C:备忘录D:加速原理

答案:减少子问题数通过减少子问题个数，降低分治算法时间复杂度的有（）

A:最接近点对B:大整数乘法C:Strassen矩阵乘法D:线性时间选择

答案:大整数乘法；Strassen矩阵乘法分治法在每一层递归上有三个步骤（）

A:选择B:分解C:合并D:解决

答案:分解；合并；解决

使用分治法求解不需要满足的条件是（）。

A:原问题和子问题使用相同的方法求解B:子问题的解可以合并C:子问题必须是一样的D:子问题不能够重复

答案:子问题必须是一样的最小堆中每个元素调整的次数不超过树高。

A:对B:错

答案:对分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。

A:对B:错

答案:对任何排序算法至少需要O(nlogn)次比较。

A:错B:对

答案:错找n个元素的中位数的分治算法的时间复杂度为O().

A:n^2B:n

C:lognD:nlogn

答案:n

第七章单元测试

动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。

A:对B:错

答案:对0/1背包问题的动态规划算法是多项式时间算法。

A:对B:错

答案:错对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。

A:对B:错

答案:错Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。

A:错B:对

答案:对含负权的最短路问题一般使用（）求解。

A:动态规划B:贪心算法C:分治算法D:网络流算法

答案:动态规划动态规划算法的基本要素有（

）和最优子结构性质。

A:贪心选择性质B:独立子问题性质C:分解合并性质D:重叠子问题性质

答案:重叠子问题性质下面不是动态规划的基本方法有（）。

A:舍入B:多重选择C:增加变量D:区间变量

答案:舍入最短路算法中适用于稀疏图的是（）

A:Bellman算法B:Dijkstra算法C:Floyd算法D:SPFA算法

答案:Bellman算法；Dijkstra算法；SPFA算法分治算法与动态规划算法的相同点是（）

A:最优子结构B:递推关系C:子问题独立

D:子问题重叠

答案:最优子结构；递推关系DAG上最短路，固定起点和终点没有意义。

A:对B:错

答案:错DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度。

A:错B:对

答案:对树上最大权独立集不包含u，可能包含儿子结点，也可能不包含儿子结点。

A:对B:错

答案:对SPFA算法的时间复杂度为O（mn）

A:对B:错

答案:对

第八章单元测试

回溯法是按广度优先策略搜索解空间树。

A:错B:对

答案:错死结点是正在产生儿子的结点。

A:对B:错

答案:错回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。

A:对B:错

答案:对回溯法不适用于解一些组合数相当大的问题。

A:对B:错

答案:错好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。

A:对B:错

答案:对下列算法中，通常以深度优先方式系统搜索问题解的是（

）。

A:回溯法B:动态规划法C:贪心法D:备忘录法

答案:回溯法装载问题的回溯算法所需的计算时间为

A:O（n2）B:O（n）C:O（nlogn）D:O（2n）

答案:O（2n）问题的状态生成法有（）

A:深度优先生成法B:宽度优先生成法C:子集树生成法D:排列树生成法

答案:深度优先生成法；宽度优先生成法回溯法解题步骤

A:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。B:针对所给问题，定义问题的解空间C:确定易于搜索的解空间结构D:确定最优子结构的性质

答案:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。；针对所给问题，定义问题的解空间；确定易于搜索的解空间结构回溯法的效率依赖于下列哪些因素（

）

A:计算约束函数的时间

B:确定解空间的时间C:计算限界函数的时间D:满足显约束的值的个数

答案:计算约束函数的时间

；计算限界函数的时间；满足显约束的值的个数剪枝函数包括（）和约束函数

A:限界函数

B:最优函数C:估计函数D:启发式函数

答案:限界函数

回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。

A:错B:对

答案:错回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需O(n!)计算时间.

A:对B:错

答案:对回溯法的两种解空间树为（）

A:排列树

B:子集树C:递归树D:祖先树

答案:排列树

；子集树

第九章单元测试

分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。

A:错B:对

答案:错分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

A:对B:错

答案:对队列式分支限界法以最小耗费优先的方式搜索解空间树。

A:对B:错

答案:错优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。

A:对B:错

答案:错分支限界法解旅行商问题时的解空间树是

A:深度优先生成树B:排列树C:子集树D:广度优先生成树

答案:排列树优先队列式分支限界法选取扩展结点的原则是

A:先进先出B:随机C:结点的优先级D:后进先出

答案:结点的优先级用分支限界法设计算法的步骤是：

A:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索B:确定易于搜索的解空间结构（按树或图组织解）C:针对所给问题，定义问题的解空间（对解进行编码）D:定义最优子结构

答案:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索；确定易于搜索的解空间结构（按树或图组织解）；针对所给问题，定义问题的解空间（对解进行编码）分支限界法与回溯法的不同点是什么？

A:存储空间的要求不同B:求解目标不同C:对扩展结点的扩展方式不同D:搜索方式不同

答案:存储空间的要求不同；求解目标不同；对扩展结点的扩展方式不同；搜索方式不同FIFO是（

）的搜索方式。

A:贪心算法

B:动态规划C:回溯算法D:分支限界

答案:分支限界

下面说法不正确的是（）

A:使用限界函数作优先级,第一个加入队列的叶子就是最优解B:回溯和分支限界都是动态生成解空间树C:用约束函数在扩展结点处剪去不满足约束的子树D:用限界函数剪去得不到最优解的子树

答案:使用限界函数作优先级,第一个加入队列的叶子就是最优解在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（

）。

A:回溯

B:分支限界

C:回溯和分支限界

D:回溯求解子集树问题

答案:分支限界

使用限界函数作优先级,第一个扩展的叶子就是最优解

A:对B:错

答案:对分支限界法不能解决0/1背包问题

A:对B:错

答案:错

第十章单元测试

网络流满足容量约束，但一般不满足流量守恒约束。

A:错B:对

答案:错设G=<V1,V2,E>为二分图,|V1|≤|V2|,M为G中一个最大匹配,且|M|=|V1|,则称M为G的完备匹配，也是最大匹配。

A:错B:对

答案:对存在割(A,B)

使流值v(f)=割的容量cap(A,B)，则割(A,B)是最小割。

A:错B:对

答案:对给定连通图G,BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

A:对B:错

答案:对有下界的流通问题不一定有可行流。

A:错B:对

答案:对Dinic算法的时间复杂度为（）

A:m2nB:mn2C:m2logCD:mn

答案:mn2如果每条边的最大容量为1，则时间复杂度是O(nm)的网络流算法有

A:容量缩放算法B:Dinic算法C:FF算法D:EK算法

答案:FF算法改进FF网络流算法，可以通过选择（

）增广路，降低时间复杂度。

A:最短路径B:最大容量C:最大瓶颈容量D:边数最少

答案:最短路径；最大容量；最大瓶颈容量；边数最少带需求的流通必须满足供给和=需求和

A:对B:错

答案:对匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。

A:错B:对

答案:对给定二分图G=<V,E>中无孤立点，其最大流算法求得最大流f,则G的最大匹配数=f.

A:错B:对

答案:对设G=<V,E>中无孤立点。W为G的最小边覆盖,若G中存在相邻边就移去其中一条。设移去的边集为N，则W-N是G的最大匹配。

A:对B:错

答案:对设f是网络N的任意流，(A,B)是N的任意s-t割，则流值f至多等于割的容量。

A:对B:错

答案:对

第十一章单元测试

蒙特卡罗算法的结果肯定是一个正确解。

A:错B:对

答案:错Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。

A:对B:错

答案:对借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。

A:错B:对

答案:对随机算法共同点是计算时间越多或运行次数越多,正确性越高.

A:对B:错

答案:对增加拉斯维加斯算法的反复求解次数,可使求解无效的概率任意小。

A:错B:对

答案:对在下列算法中有时找不到问题解的是

A:数值随机算法B:蒙特卡罗算法C:拉斯维加斯算法D:舍伍德算法

答案:拉斯维加斯算法肯定获得可行解，但不一定是正确解的算法是

A:蒙特卡罗算法B:舍伍德算法C:拉斯维加斯算法D:数值随机算法

答案:蒙特卡罗算法在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（

）对输入进行预处理。

A:数值随机化算法B:舍伍德算法C:蒙特卡罗算法D:拉斯维加斯算法

答案:舍伍德算法下面说法正确的是

A:蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。B:舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。C:求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。D:现实计算机上无法产生真正的随机数

答案:蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。；舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。；求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。；现实计算机上无法产生真正的随机数下面说法正确的是（）

A:增加蒙特卡罗算法的求解次数,可使求解错误的概率任意小。B:随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法C:当最坏和平均情况差别较大时,舍伍德算法可以消除好坏实例的差别，达到平均实例的性能D:线性同余法是产生伪随机数的最常用的方法

答案:增加蒙特卡罗算法的求解次数,可使求解错误的概率任意小。；随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法；当最坏和平均情况差别较大时,舍伍德算法可以消除好坏实例的差别，达到平均实例的性能；线性同余法是产生伪随机数的最常用的方法确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所得结果完全相同。

A:对B:错

答案:对舍伍德算法总是有解,且解总是正确的，但最坏性能未改变。

A:对B:错

答案:错拉斯维加斯算法肯定得到一个正确解。

A:对B:错

答案:错随机抽取数组元素k次,从最接近搜索元素x的位置顺序搜索,

顺序搜索的平均比较次数为O(n/(k+1)).

A:错B:对

答案:对

第十二章单元测试

有多项式时间算法的问题是易解问题

A:错B:对

答案:对EXP类是所有指数时间可解的判定问题组成的问题类

A:错B:对

答案:对如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则X可多项式时间归约到Y。

A:错B:对

答案:对下面关于NP问题说法正确的是（

）

A:NP完全问题是P类问题的子集B:NP类问题包含在P类问题中C:NP问题都是不可能解决的问题D:P类问题包含在NP类问题中

答案:P类问题包含在NP类问题中下面属于NP完全问题的是（）

A:旅行商问题B:SATC:最小顶点覆盖D:最大独立集

答案:旅行商问题；SAT；最小顶点覆盖；最大独立集以下关于判定问题难易处理的叙述中错误的是

A:需要超过多项式时间算法求解的问题是易处理的B:可以由多项式时间算法求解的问题是易处理的C:需要超过多项式时间算法求解的问题是不能处理的D:可以由多项式时间算法求解的问题是难处理的

答案:需要超过多项式时间算法求解的问题是易处理的；需要超过多项式