分支限界法与回溯法的不同点在于（ ）
A、搜索解空间树的实现方式不同
B、回溯法从求解可行解入手，而采用优先队列的分支限界法可直接求解最优解
C、分支限界法比回溯法时间效率高
D、回溯法比分支限界法时间效率高
重量不是整数的0/1背包问题可用下列哪些算法策略求解（ ）
A、蛮力法
B、动态规划
C、回溯法
D、分支限界法
关于单源最短路径问题，描述正确的是（ ）
A、单源最短路径问题可用动态规划法和分支限界法求解
B、该问题的分支限界法一般采用优先队列实现，且优先级可根据结点所对应的当前路长确定
C、该问题的分支限界法剪枝策略是:当出现到达同一个节点存在较短路径时，剪去长的那条路径
D、
不管采用哪种算法策略，该问题求解的时间效率与图的存储结构相关
关于装载问题，描述正确的是（ ）
A、装载问题的解空间树是子集树
B、当采用深度遍历方式遍历装载问题的解空间树时，可以采用左儿子限界右儿子
C、当采用宽度遍历方式遍历装载问题的解空间树时，可以采用左儿子限界右儿子
D、当采用优先队列求解装载问题时，其优先权重可以设置为限界的值
关于分支限界法和回溯法，下列描述正确的是（ ）
A、分支限界法和回溯法求解的问题时都需要构造问题的解空间树
B、分支限界法和回溯法的限界方式具有一致性
C、回溯法和分治限界法都可以采用迭代实现
D、回溯法和分治限界法的主要区别在于针对解空间树的搜索方式不同
第十二章 客观题练习
关于分支限界法，下列描述正确的是（ ）
A、分支限界法主要采用广度遍历（或最佳优先）方式搜索解空间树
B、分治限界法主要采用约束函数和限界函数剪枝
C、分治限界法实现的数据结构包括队列和堆
D、分支限界法比回溯法能更快找到解
下列回溯法求解时间复杂度规模达到或超过O（n！）的是（ ）
A、电路板排列问题
B、圆排列问题
C、图的m着色问题
D、最大团问题
下列回溯法求解时间复杂度规模为on2n题干 的是（ ）
A、装载问题
B、批处理作业问题
C、0/1背包问题
D、符号三角形问题
下列属于符号三角形问题的约束条件是（ ）
A、给定的 n 必须是奇数
B、给定的 n 必须是偶数
C、正符号不超过 i（i+1）/4，i 为当前第一行第 i 个符号
D、负符号不超过 i（i+1）/4，i 为当前第一行第 i 个符号
最小生成树算法有哪些（ ）
A、Dijkstra
B、Floyd
C、Prim
D、Kruskal
第九章客观题练习
下列属于贪婪法性质的是（ ）
A、最优子结构
B、重叠子问题
C、不可撤销
D、贪心性质
第八章客观题练习
关于动态规划算法策略描述正确的是（ ）
A、动态规划算法主要用于解决多阶段解决过程最优化问题
B、动态规划算法与分治法类似，都是自顶向下分析问题，自底向上求解问题
C、动态规划和线性规划一样，都是解决规划问题
D、动态规划算法可以使用递归和迭代两种方式实现
关于二叉树问题，下列描述正确的是（ ）
A. 二叉树有三种典型的遍历方式
B. 二叉树中序遍历比另外两种遍历的时间效率高
C. 求二叉树树高的分治法时间效率类型为 Θ(n)
D. 求二叉树叶子节点数的分治法时间效率类型为 Θ(n)
下列描述正确的是（ ）
A. 大整数乘法和矩阵相乘的分治法时间效率优于 Θ(n2) 和 Θ(n3)
B. 分治法解最近二维点对的最优效率可达 Θ(nlogn)
C. 分治法解凸包问题的最优效率可达 Θ(n2)
D. 棋盘覆盖问题中衡量时间效率中的 k 不代表棋盘的行数或列数
关于排序问题，平均效率为 Θ(nlogn) 的是（ ）
A. 快速排序
B. 选择排序
C. 合并排序
D. 插入排序
第五章客观题练习
关于分治法描述正确的是（ ）
A. 分治法是将大规模问题分解为规模较小的多个子问题进行求解的方法
B. 分治法的时间效率好于蛮力法
C. 快速排序的最差效率好于蛮力类型的排序算法
D. 快包算法的最差效率好于蛮力类型的凸包算法
关于斐波那契数列，下列说法正确的是（ ）
A. 斐波那契数列计算可用递归函数实现
B. 斐波那契数列计算可用迭代函数实现
C. 斐波那契数列用递归实现比迭代实现效率高
D. 斐波那契数列用递归实现比迭代实现代码行数少
算法表示渐进符号的证明方法主要有（ ）
A. 利用极限计算
B. 利用数学归纳法证明
C. 利用定义直接证明
D. 利用反证法证明
t(n)=nlogn，g(n)=logn2,则 t(n) 和 g(n) 的关系为（ ）
A、t(n)∈Ω(g(n))
B、t(n)∈O(g(n))
C、t(n)+g(n) ∈Θ (t(n))
D、t(n)+g(n) ∈Θ (g(n))
第二章客观题练习
关于算法分析描述正确的是 （ ）
A. 算法分析主要针对算法执行的时间复杂度和空间复杂度
B. 算法效率与输入规模成正比
C. 算法效率分析时需要考虑最优、最差和平均情况
D. 对大规模问题，算法效率主要关注基本操作次数的增长次数及其常数倍
算法的表示方法有（ ）
A. 机器语言
B. 自然语言
C. 伪代码
D. 程序流程图
算法的要素包括（ ）
A. 数据
B. 运算
C. 控制
D. 输出
关于算法描述正确的是（ ）
A. 算法是解决问题的一系列清晰指令
B. 欧几里得算法用来求最小公倍数
C. 操作系统程序是一类特殊的算法
D. 算法可以没有输入,但至少有一个输出
关于Kruskal算法，说法正确的是（ ）
A、可求解单点最短路径树
B、可通过构造不相交子集来避免产生回路
C、该算法与Prim算法效率一致
D、与Prim算法对同一实例构造的生成树相同
Prim算法的贪婪策略体现在（ ）
A、每一次将不在树中距离源点最近的节点加入
B、每一次将不在树中距离树最近的节点加入
C、每一次将不在树中边权值最小的节点加入
D、每一次将不在树中序号最小的节点加入
第十一章客观题练习
下列问题的解空间树既不是子集树，又不能算是排列树的是（ ）
A、旅行商问题
B、最大团问题
C、连续邮资问题
D、图的 m 着色问题
贪婪法一般采用什么方式实现（ ）
A、递归
B、迭代
C、递归+迭代
D、其他
下列算法的基本操作是（ ）
plaintext
Copy code
Calc(A[0,n-1])
tmp=A[0]
for i=1 to n-1
if(tmp>=A[i])
tmp=tmp+A[i]
return tmp
A. 赋值
B. 加法
C. 比较
D. 循环
下列增长次数最低的是（ ）
A、ln2n
B、n*log(n)
C、n？
D、n
分析算法，最重要的是衡量算法哪两个方面的效率（ ）
A. 时间效率
B. 执行效率
C. 空间效率
D. 编译效率
36．下列算法中通常以自底向下的方式求解最优解的是（ ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
35．下列是动态规划算法基本要素的是（ ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
34．实现合并排序利用的算法是（ ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
33、采用广度优先策略搜索的算法是（ ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
32、回溯法搜索状态空间树是按照（ ）的顺序。
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历
31、下列算法中不能解决0/1背包问题的是（ ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
30、下面问题（ ）不能使用贪心法解决。
A 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题
29、使用分治法求解不需要满足的条件是（ ）。
A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解
27、背包问题的贪心算法所需的计算时间为（ ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
26. 0-1背包问题的回溯算法所需的计算时间为（ ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
25. 矩阵连乘问题的算法可由（ ）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
24. （ ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
23. 采用最大效益优先搜索方式的算法是（ ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
22、贪心算法与动态规划算法的主要区别是（ ）。
A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解
21、以深度优先方式系统搜索问题解的算法称为 ( ) 。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）
A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数
19.回溯法的效率不依赖于下列哪些因素（ ）
A.满足显约束的值的个数 B. 计算约束函数的时间
C. 计算限界函数的时间 D. 确定解空间的时间
18.下面是贪心算法的基本要素的是（ ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
17．实现棋盘覆盖算法利用的算法是（ ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
16．实现最大子段和利用的算法是（ ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
15．背包问题的贪心算法所需的计算时间为（ ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
14．广度优先是（ ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
12．下列算法中通常以深度优先方式系统搜索问题解的是（ ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11．下面不是分支界限法搜索方式的是（ ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
10、实现最长公共子序列利用的算法是（ ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
8、以下不可以使用分治法求解的是（ ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题
7、衡量一个算法好坏的标准是（ ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
6．下列算法中通常以自底向上的方式求解最优解的是（ ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
5. 回溯法解TSP问题时的解空间树是（ ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
4、最长公共子序列算法利用的算法是（ ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
1、二分搜索算法是利用（ ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
0/1背包问题的动态规划算法生成表中某一列的值的序列一定是非递减的。
正确
错误
0/1背包问题的动态规划算法生成表中某一行的值的序列一定是递增的。
正确
错误
动态规划算法需要对当前问题的所有小规模问题求解，然后从中取出最优的情况。
正确
错误
评论0