算法设计与分析知到智慧树章节测试课后答案2024年秋天津大学第一章单元测试
下列关于效率的说法正确的是（）。
B:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法
C:效率是一个性能要求，其目标应该在需求分析时给出
；提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法
；效率是一个性能要求，其目标应该在需求分析时给出
A:硬盘容量
B:问题的规模
C:待处理数据的初态
D:计算机性能
答案:问题的规模
；待处理数据的初态
计算机算法指的是（）。
A:排序方法
B:解决问题的有限运算序列
C:调度方法
D:计算方法
答案:解决问题的有限运算序列
A:O(n)
B:O(n2)
C:O(nlog2n)
D:O(1)
答案:O(n)
；O(nlog2n)
A:错B:对
答案:错用渐进表示法分析算法复杂度的增长趋势。（）
）。
A:O(n)B:O(log2n)C:O(n2)D: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:错
答案:对假定，,递归方程的解是.()
答案:错使用Master方法求解递归方程的解为（）.
A:
B:
C:
D:
答案:
答案:对
答案:对使用分治算法求解最大最小问题。假定问题的规模,每次将问题分成规模接近的两个子问题，递归地对子问题求解并将子问题的解合并得到大问题的解，该分治算法的复杂度函数可写为()
D:,
第三章单元测试
在一个至少包含三个顶点的加权连通单向图中，假定边的权重互不相同，则权重最大的边不可能被包含在任何最小生成树中。()
答案:错令是一个加权图，令T是G的最小生成树，则T中任意两个顶点和之间的路径必定是图G中该两点之间的最短路径。()
答案:错对于一个加权连通无向图，在Kruskal’sMST(KrusKal’s最小生成树)算法中,若使用最大队列代替最小队列，则可生成一个最大成本树(而不是最小成本树).()
答案:对贪心算法适用于求解的问题一般具备以下几个特征().
A:问题可分为相互独立的子问题
B:满足贪心选择性质
C:满足最优子结构性质
D:子问题的解相互独立
答案:满足贪心选择性质
；满足最优子结构性质
0/1背包问题是NP-hard问题，任何求解0/1背包问题的贪心算法都不能保证得到该问题的最优解。（）
答案:对一个连通图中具有最小权重的边，必定被包含在图的最小生成树中。()
答案:对一个问题的贪心选择性质是指问题的最优解可通过一系列具备最优(贪心)选择得到。（）
答案:对贪心算法所做出的选择可能依赖于到目前为止已经做出的选择，但是不依赖于将来的选择或子问题的解。（）
答案:对贪心算法是一种自顶向下的求解方法，分步做出贪心选择，逐步将问题变成规模较小的问题求解。（）
答案:对下列问题可使用贪心算法求得最优解的是（）.
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)的背包获得的最大价值，在决策其动态规划函数为：
，。（）
答案:对设有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
设有有向加权图如下图所示，每两对点之间的最短路径长度（）。
设有有向加权图如下图所示，起点0点与其他点之间的最短路径长度（）。
设有一个网(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
第五章单元测试
回溯法是指具有限界函数的深度优先生成法。（）
答案:对用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。（）
答案:对用回溯法解批处理作业调度问题时，该问题的解空间结构为子集树结构。（）
答案:错在对问题的解空间树进行搜索的方法中，一个结点有多次机会成为活结点的是（）。
A:分支限界法
B:回溯法
C:动态规划
D:回溯法和分支限界法
答案:回溯法
回溯法在解空间树T上的搜索方式是（）。
A:广度优先
B:活结点优先
C:最小耗费优先
D:深度优先
答案:深度优先
回溯算法和分支限界法的问题的解空间树不会是（）。
A:无序树
B:有序树
C:排列树
D:子集树
答案:无序树
回溯法求问题的所有解时，要回溯到根，且根结点的子树都要已被搜索遍才结束。（）
答案:错下列问题中可以用回溯算法解决的是？（）
A:货箱装船问题
B:N皇后问题
C:旅行商问题
D:0/1背包问题
答案:货箱装船问题
；N皇后问题
；旅行商问题
；0/1背包问题
回溯法的效率不依赖于以下哪一个因素？（）
A:问题的解空间的形式
C:满足显约束的x[k]值的个数
答案:问题的解空间的形式
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:搜索过程中，保留下来的孩子节点是可能导致可行解或最优解的节点
答案:搜索过程中，保留下来的孩子节点是活动节点，被插入活动节点表中
；搜索过程中，扩展节点一次性生成所有的孩子节点
；搜索过程中，保留下来的孩子节点是可能导致可行解或最优解的节点
分支限界法保留下来的活动节点是有可能导致可行解或最优解的节点，回溯法则不是。（）