袄偷午扰拐蚕存田睹村踌肠篇
敲航炔豌胆穷起弛辑荷蒂斡镁
第一章 单元测试
1、
算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。
A:对
B:错
答案: 对
2、
使用伪代码描述算法具有（ ）等优点。
A:易于转化为程序语言代码
B:简单易懂
C:格式统一规范
D:容易修改
答案: 易于转化为程序语言代码;简单易懂;容易修改
3、
算法通常具有（ ）的性质。
A:输入：有零个或多个输入
B:确定性：组成算法的每条指令清晰、无歧义
C:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
D:输出：至少有一个输出
答案: 输入：有零个或多个输入;确定性：组成算法的每条指令清晰、无歧义;有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限;输出：至少有一个输出
4、
程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
A:对
B:错
答案: 错
5、
常用的描述算法的形式有（ ）。
A:自然语言
B:程序流程图
C:机器语言
D:伪代码
答案: 自然语言;程序流程图;伪代码
6、
函数f(n)=20log3^n的渐进表达式是（ ）。
A:0（n^2）
B:0(log(n))
C:O(n)
D:0(1)
答案: O(n)
7、
一个算法的优劣由（ ）决定。
A:代码长度
B:空间复杂度
C:时间复杂度
D:使用的编程语言
答案: 空间复杂度;时间复杂度
8、
如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。
A:错
B:对
答案: 对
9、
分析以下代码的时间复杂度：
int func(int n)
{
int i=1, k=0;
while(i k++;
i=i*2;
}
return k;
}
A:O(n/2)
B:O(n)
C:O(logn)
D:O(n^2)
答案: O(logn)
10、
对于f(n)=n，下列说法正确的是（ ）。
A:f(n)=O(n)
B:f(n)=O(n^2)
C:f(n)=O(1/n)
D:f(n)=O(n^3)
答案: f(n)=O(n);f(n)=O(n^2);f(n)=O(n^3)
第二章 单元测试
1、
递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
A:错
B:对
答案: 对
2、
已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
A:计算1到50的乘积。
B:计算50个1的和。
C:计算1到50的和。
D:计算斐波拉契数列的第50个元素的值。
答案: 计算1到50的和。
3、
递归的优点包括( )。
A:容易用数学归纳法来证明算法的正确性
B:可读性强
C:结构清晰
D:运行效率高
答案: 容易用数学归纳法来证明算法的正确性;可读性强;结构清晰
4、
在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动( )步。
A:28
B:31
C:32
D:41
答案: 31
5、
分治法能解决的问题一般具有（ ）等特征。
A:分解出的子问题的解可以合并为原问题的解
B:最优子结构
C:子问题相互独立
D:该问题缩小到一定程度时可以容易地解决
答案: 分解出的子问题的解可以合并为原问题的解;最优子结构;子问题相互独立;该问题缩小到一定程度时可以容易地解决
6、
在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。
A:对
B:错
答案: 对
7、
给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
A:O(n)
B:O(logn)
C:O(n^2)
D:O(nlogn)
答案: O(n^2)
8、
已知某楼房共20层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
A:3
B:4
C:5
D:6
答案: 5
9、
关于快速排序的时间复杂度，( )是正确的。
A:在最坏情况下时间复杂度为O(n^2)
B:在平均情况下时间复杂度为O(nlogn)
C:在最好情况下时间复杂度为O(nlogn)
D:在平均情况下时间复杂度为O(n^2)
答案: 在最坏情况下时间复杂度为O(n^2);在平均情况下时间复杂度为O(nlogn);在最好情况下时间复杂度为O(nlogn)
10、
快速排序是对传统排序算法( )的一种改进。
A:选择排序
B:冒泡排序
C:归并排序
D:插入排序
答案: 冒泡排序
第三章 单元测试
1、
能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是( )。
A:递归调用
B:最优子结构
C:贪心选择性质
D:重叠子问题
答案: 最优子结构;重叠子问题
2、
关于备忘录法，以下说法正确的是( )。
A:备忘录法可以避免相同子问题的重复求解。
B:备忘录法的控制结构与直接使用递归方法的控制结构相同。
C:备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。
D:备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。
答案: 备忘录法可以避免相同子问题的重复求解。;备忘录法的控制结构与直接使用递归方法的控制结构相同。;备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。
3、
字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。
A:4,2
B:4,1
C:3,5
D:4,6
答案: 4,2
4、
使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。
A:O(n^2)
B:O(n*m)
C:O(nlogm)
D:O(m^n)
答案: O(n*m)
5、
输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。
A:2
B:3
C:4
D:1
答案: 3
6、
序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
A:3
B:4
C:1
D:2
答案: 4
7、
使用穷举法求解最长递增子序列的时间复杂度为( )。
A:O(n^2)
B:O(n^n)
C:O(nlogn)
D:O(n*2^n)
答案: O(n*2^n)
8、
使用动态规划算法求最大子段和的时间复杂度为( )。
A:O(nlogn)
B:O(n)
C:O(logn)
D:O(2^n)
答案: O(n)
9、
某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目( )可以使总收益最大。（不允许部分投资某个项目）
A:A
B:C
C:B
D:D
答案: C;B;D
10、
在使用动态规划算法求解0-1背包问题时，若mij=mi+1j-wi+vi，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少wi，价值增加vi。
A:错
B:对
答案: 对
第四章 单元测试
1、
能够使用贪心算法求解的问题需具备的基本要素包括( )。
A:递归调用
B:平衡子问题
C:最优子结构性质
D:贪心选择性质
E:重复子问题
答案: 最优子结构性质;贪心选择性质
2、
下列关于贪心算法与动态规划算法说法正确的是( )。
A:贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质
B:贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质
C:贪心算法与动态规划算法求解的问题都具备最优子结构性质
D:贪心算法与动态规划算法求解的问题都具有重复子问题性质
答案: 贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质;贪心算法与动态规划算法求解的问题都具备最优子结构性质
3、
在解决活动安排问题时应首先对活动进行排序，排序的依据是( )。
A:按照活动结束时间降序排列
B:按照活动开始时间升序排列
C:按照活动结束时间升序排列
D:按照活动开始时间降序排列
答案: 按照活动结束时间升序排列
4、
使用贪心算法求解最优装载问题，其时间复杂度为( )。
A:O(n3n)
B:O(n5n)
C:O(nlogn)
D:O(n2n)
答案: O(nlogn)
5、
( )能够使用贪心算法求解。
A:最优装载问题
B:0-1背包问题
C:最小生成树问题
D:单源最短路径问题
E:活动安排问题
F:部分背包问题
答案: 最优装载问题;最小生成树问题;单源最短路径问题;活动安排问题;部分背包问题
6、
0-1背包问题与部分背包问题的区别在于( )。
A:没有区别，它们的含义相同
B:若用贪心算法解决0-1背包问题，只能得到近似最优解
C:在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分
D:若用贪心算法解决部分背包问题，只能得到近似最优解
答案: 若用贪心算法解决0-1背包问题，只能得到近似最优解;在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分
7、
在求解部分背包问题时采用的贪心策略是( )。
A:选择重量最轻的物品
B:选择单位价值下重量最大的物品
C:选择价值最大的物品
D:选择单位重量下价值最大的物品
答案: 选择单位重量下价值最大的物品
8、
Dijkstra算法可用于求解( )。
A:单源最短路径问题
B:每对顶点间最短路径问题
C:单终点最短路径问题
D:单对顶点最短路径问题
答案: 单源最短路径问题;每对顶点间最短路径问题;单终点最短路径问题;单对顶点最短路径问题
9、
Prim算法适合稀疏图，其时间复杂度只与边的数目有关。
A:对
B:错
答案: 错
10、
在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为( )。
A:无穷大
B:无穷小
C:0
D:-1
答案: 无穷大
第五章 单元测试
1、
回溯法中的剪枝函数包括( )。
A:随机数生成函数
B:约束函数
C:虚函数
D:递归函数
E:静态函数
F:限界函数
答案: 约束函数;限界函数
2、
回溯法采用的搜索策略是( )。
A:启发式搜索
B:层次搜索
C:深度优先搜索
D:广度优先搜索
答案: 深度优先搜索
3、
回溯法的主要用途包括求问题的所有解、求问题的最优解和求问题的任一解。
A:对
B:错
答案: 对
4、
马的遍历问题能否有可行解，与( )有关。
A:马的遍历深度
B:马的遍历顺序
C:马的初始位置
D:棋盘大小
答案: 马的初始位置;棋盘大小
5、
在N皇后问题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是( )。
A:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
B:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
C:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
D:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
答案: 对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。;对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
6、
四皇后问题一共有2个可行解，八皇后问题一共有76个可行解。
A:错
B:对
答案: 错
7、
用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵( )。
A:高为m的m叉树
B:高为n的m叉树
C:高为m的n叉树
D:高为n的n叉树
答案: 高为n的m叉树
8、
任何一张地图只用( )种颜色就能使具有共同边界的国家着上不同的颜色。
A:4
B:6
C:3
D:2
答案: 4
9、
使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。
A:对
B:错
答案: 对
10、
关于使用回溯法求解0-1背包问题，以下说法正确的是( )。
A:使用约束函数剪去不合理的左子树（装该物品）。
B:使用限界函数剪去得不到更优解的左子树（装该物品）。
C:使用限界函数剪去得不到更优解的右子树（不装该物品）。
D:使用约束函数剪去不合理的右子树（不装该物品）。
答案: 使用约束函数剪去不合理的左子树（装该物品）。;使用限界函数剪去得不到更优解的右子树（不装该物品）。
如需购买完整答案，请点击下方红字：
获取更多网课答案，请点击这里，进入www.mengmianren.com
腐戳苗卵视茬闹靡午僧侣些谩
涤赋邯赏铆访外官钙认精豹藏