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

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

下列关于效率的说法正确的是（）。

A:效率主要指处理机时间和存储器容量两个方面

B:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法

C:效率是一个性能要求，其目标应该在需求分析时给出

D:程序的效率与程序的长度强相关

答案:效率主要指处理机时间和存储器容量两个方面

；提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法

；效率是一个性能要求，其目标应该在需求分析时给出

算法的时间复杂度取决于（）。

A:硬盘容量

B:问题的规模

C:待处理数据的初态

D:计算机性能

答案:问题的规模

；待处理数据的初态

计算机算法指的是（）。

A:排序方法

B:解决问题的有限运算序列

C:调度方法

D:计算方法

答案:解决问题的有限运算序列

归并排序法的时间复杂度和空间复杂度分别是（）。

A:O(n)

B:O(n2)

C:O(nlog2n)

D:O(1)

答案:O(n)

；O(nlog2n)

将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。（）

A:错B:对

答案:错用渐进表示法分析算法复杂度的增长趋势。（）

A:错B:对

答案:对算法分析的两个主要方面是时间复杂度和空间复杂度的分析。（）

A:错B:对

答案:对某算法所需时间由以下方程表示，求出该算法时间复杂度（

）。

A:O(n)B:O(log2n)C:O(n2)D:O(nlog2n)

答案:O(nlog2n)下列代码的时间复杂度是（

）。

A:O(N)B:O(1)C:O(log3N)D:O(log2N)

答案:O(log2N)下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（

）。

A:3n/2B:

n-3/2C:3n/2-3/2D:

2n-1

答案:3n/2-3/2

第二章单元测试

可用Master方法求解的递归方程的形式为（）。

A:T(n)=aT(n/b)+f(n),a≥1,b＞1,为整数,f(n)＞0.

B:T(n)=T(n-a)+T(n-b)+f(n)，a≥1,b＞1

C:T(n)=T(n-a)+T(a)+f(n)，a≥1

D:T(n)=T(n/a)+T(n/b)+f(n)，a≥1,b＞1

答案:T(n)=aT(n/b)+f(n),a≥1,b＞1,为整数,f(n)＞0.

A:对B:错

答案:对假定，,递归方程的解是.()

A:对B:错

答案:对假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。针对该问题的任何算法需要的时间复杂度的下限必为。()

A:错B:对

答案:错使用Master方法求解递归方程的解为（）.

A:

B:

C:

D:

答案:

考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。若给定集合S，则可在时间内找到这条分界线L。()

A:错B:对

答案:对

A:

B:

C:

D:

答案:

从n个数中找出前k个最小的元素并对所选择的前k个最小的元素进行排序。使用归并排序算法将这n个数进行排序的时间复杂度为，从排好序的数组中提取有序的k个最小数的时间复杂度为，因此总的运行时间复杂度为.()

A:对B:错

答案:对假定问题对于规模为n的所有不同输入，存在一个分治算法其平均时间复杂度为，则算法在最坏情形下的时间复杂度可能为（）

A:错B:对

答案:对使用分治算法求解最大最小问题。假定问题的规模,每次将问题分成规模接近的两个子问题，递归地对子问题求解并将子问题的解合并得到大问题的解，该分治算法的复杂度函数可写为()

A:

B:

C:

D:,

答案:

第三章单元测试

在一个至少包含三个顶点的加权连通单向图中，假定边的权重互不相同，则权重最大的边不可能被包含在任何最小生成树中。()

A:错B:对

答案:错令是一个加权图，令T是G的最小生成树，则T中任意两个顶点和之间的路径必定是图G中该两点之间的最短路径。()

A:对B:错

答案:错对于一个加权连通无向图，在Kruskal’sMST(KrusKal’s最小生成树)算法中,若使用最大队列代替最小队列，则可生成一个最大成本树(而不是最小成本树).()

A:对B:错

答案:对贪心算法适用于求解的问题一般具备以下几个特征().

A:问题可分为相互独立的子问题

B:满足贪心选择性质

C:满足最优子结构性质

D:子问题的解相互独立

答案:满足贪心选择性质

；满足最优子结构性质

0/1背包问题是NP-hard问题，任何求解0/1背包问题的贪心算法都不能保证得到该问题的最优解。（）

A:错B:对

答案:对一个连通图中具有最小权重的边，必定被包含在图的最小生成树中。()

A:错B:对

答案:对一个问题的贪心选择性质是指问题的最优解可通过一系列具备最优(贪心)选择得到。（）

A:错B:对

答案:对贪心算法所做出的选择可能依赖于到目前为止已经做出的选择，但是不依赖于将来的选择或子问题的解。（）

A:错B:对

答案:对贪心算法是一种自顶向下的求解方法，分步做出贪心选择，逐步将问题变成规模较小的问题求解。（）

A:错B:对

答案:对下列问题可使用贪心算法求得最优解的是（）.

A:集合覆盖问题

B:0/1背包问题

C:货箱装载问题

D:偶图覆盖问题

答案:货箱装载问题

第四章单元测试

动态规划的适用条件为（）。

A:最优子结构性质

B:子问题的重叠性

C:无后效性

D:子问题相互独立

答案:最优子结构性质

；子问题的重叠性

；无后效性

（1）计算动态规划数组；（2）确定动态规划函数；（3）构造最优解；（4）定义子问题。动态规划一般可以将步骤依次划分为：（）。

A:（4）（1）（2）（3）

B:（4）（3）（1）（2）

C:（4）（2）（1）（3）

D:（3）（4）（2）（1）

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

使用动态规划方法解决0/1背包问题，设V(i,j)表示将前i(1≤i≤n)个物品装入容量为j(1≤j≤C)的背包获得的最大价值，在决策其动态规划函数为：

，。（）

A:错B:对

答案:对设有5个物品，背包承重为10，5个物品价值p=[6,3,5,4,6]，质量w=[2,2,6,5,4]，则该0/1背包问题的解向量为（）。

A:[1,0,0,1,1]

B:[1,1,0,0,1]

C:[1,0,0,0,1]

D:[0,0,1,1,0]

答案:[1,1,0,0,1]

设M1,4=M1M2M3M4表示4个矩阵相乘，矩阵维度r1=2,r2=10,r3=2,r4=10,r5=2，则链乘的最少次数是（）。

A:44

B:88

C:40

D:80

答案:88

使用动态规划方法解决矩阵乘法链问题的时间复杂度和空间复杂度分别为（）。

A:

B:

C:

D:

答案:

设有有向加权图如下图所示，每两对点之间的最短路径长度（）。

A:

B:

C:

D:

答案:

设有有向加权图如下图所示，起点0点与其他点之间的最短路径长度（）。

A:

B:

C:

D:

答案:

设有一个网(i,Ci)如下图所示，则满足i≤5且Ci≤7的最大不交叉网子集有（）个。

A:4

B:1

C:2

D:3

答案:2

有字符串a=ABCB,b=BDCA，则使用动态规划方法求解a与b的最长公共子序列时，下表X处的值为()。

A:-1

B:2

C:1

D:0

答案:2

第五章单元测试

回溯法是指具有限界函数的深度优先生成法。（）

A:对B:错

答案:对用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。（）

A:错B:对

答案:对用回溯法解批处理作业调度问题时，该问题的解空间结构为子集树结构。（）

A:对B:错

答案:错在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点的是（）。

A:分支限界法

B:回溯法

C:动态规划

D:回溯法和分支限界法

答案:回溯法

回溯法在解空间树T上的搜索方式是（）。

A:广度优先

B:活结点优先

C:最小耗费优先

D:深度优先

答案:深度优先

回溯算法和分支限界法的问题的解空间树不会是（）。

A:无序树

B:有序树

C:排列树

D:子集树

答案:无序树

回溯法求问题的所有解时，要回溯到根，且根结点的子树都要已被搜索遍才结束。（）

A:对B:错

答案:错下列问题中可以用回溯算法解决的是？（）

A:货箱装船问题

B:N皇后问题

C:旅行商问题

D:0/1背包问题

答案:货箱装船问题

；N皇后问题

；旅行商问题

；0/1背包问题

回溯法的效率不依赖于以下哪一个因素？（）

A:问题的解空间的形式

B:计算上界函数bound的时间

C:满足显约束的x[k]值的个数

D:产生x[k]的时间

答案:问题的解空间的形式

用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（）。

A:O(m)

B:O(n)

C:O(m2)

D:O(mn)

答案:O(mn)

第六章单元测试

分支限界法中，解空间组织成()结构然后进行搜索。

A:链表B:树C:堆栈

D:数组

答案:树分支限界法在问题的解空间树中，按()策略，从根节点出发搜索解空间树。

A:广度优先B:深度优先

C:扩展节点优先D:活动节点优先

答案:广度优先优先队列式分支限界法选取扩展节点的原则是()

A:随机

B:节点的优先级C:先进先出D:后进后出

答案:节点的优先级分支限界法主要有哪几种方式实现？（）

A:堆栈式分支限界法

B:FIFO队列式

C:优先队列式分支限界法

D:广度优先分支限界法

答案:FIFO队列式

；优先队列式分支限界法

比较分支限界法和回溯法，两者的不同是()

A:分支限界法与回溯法的搜索方式不同

B:分支限界法需要借助活动节点表数据结构，而回溯法则不需要

C:在一般情况下，分支限界法与回溯法的求解目标不同

D:扩展节点的扩展方式不同

答案:分支限界法与回溯法的搜索方式不同

；分支限界法需要借助活动节点表数据结构，而回溯法则不需要

；在一般情况下，分支限界法与回溯法的求解目标不同

；扩展节点的扩展方式不同

下述有关分支限界法搜索过程描述正确的是()

A:搜索过程中，保留下来的孩子节点是活动节点，被插入活动节点表中

B:必须当活动节点表为空时，算法才算结束

C:搜索过程中，扩展节点一次性生成所有的孩子节点

D:搜索过程中，保留下来的孩子节点是可能导致可行解或最优解的节点

答案:搜索过程中，保留下来的孩子节点是活动节点，被插入活动节点表中

；搜索过程中，扩展节点一次性生成所有的孩子节点

；搜索过程中，保留下来的孩子节点是可能导致可行解或最优解的节点

分支限界法保留下来的活动节点是有可能导致可行解或最优解的节点，回溯法则不是。（）

A:对B:错

答案:错分支限界法中活动节点可以多次扩展。（）

A:对B:错

答案:错分支限界法一般比回溯法使用更多内存空间。（）

A:对B:错

答案:对分支限界法一般更适合求解最优化问题。（）

A:对B:错

答案:对

第七章单元测试

快速排序问题属于()

A:NP难问题

B:难解问题C:易解问题D:不可解问题

答案:易解问题能够用动态规划算法求解的问题一定属于()

A:NP难问题

B:NP问题C:难解问题D:易解问题

答案:NP问题停机问题不属于()

A:难解问题B:决策问题C:不可计算问题D:NP难问题

答案:NP难问题

下面的问题属于NP问题的有（）

A:矩阵乘法链问题

B:找出图中所有点对的最短路径问题

C:计算两个正整数的最大公约数

D:定理识别问题

答案:矩阵乘法链问题

；找出图中所有点对的最短路径问题

；计算两个正整数的最大公约数

NP完全题可能属于()

A:P类问题

B:难解问题

C:NP类问题

D:NP难问题

答案:P类问题

；NP类问题

；NP难问题

关于多项式规约，下面叙述正确的是()

A:所有的NPC问题都可以多项式地规约到NP难问题

B:所有的P