算法分析与设计智慧树知到课后章节答案2023年下湖南中医药大学

算法分析与设计智慧树知到课后章节答案2023年下湖南中医药大学湖南中医药大学

第一章测试

算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。

A:错B:对

答案:对

使用伪代码描述算法具有（）等优点。

A:易于转化为程序语言代码B:格式统一规范C:简单易懂D:容易修改

答案:易于转化为程序语言代码;简单易懂;容易修改

算法通常具有（）的性质。

A:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限B:确定性：组成算法的每条指令清晰、无歧义C:输出：至少有一个输出D:输入：有零个或多个输入

答案:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限;确定性：组成算法的每条指令清晰、无歧义;输出：至少有一个输出;输入：有零个或多个输入

程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。

A:对B:错

答案:错

常用的描述算法的形式有（）。

A:程序流程图B:机器语言C:伪代码D:自然语言

答案:程序流程图;伪代码;自然语言

函数f(n)=20log3^n的渐进表达式是（）。

A:0(log(n))B:0（n^2）C:0(1)D:O(n)

答案:O(n)

一个算法的优劣由（）决定。

A:时间复杂度B:代码长度C:空间复杂度D:使用的编程语言

答案:时间复杂度;空间复杂度

如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。

A:对B:错

答案:对

分析以下代码的时间复杂度：

intfunc(intn)

{

inti=1,k=0;

while(i<=n){

k++;

i=i*2;

}

returnk;

}

A:O(n)B:O(n^2)C:O(logn)D:O(n/2)

答案:O(logn)

对于f(n)=n，下列说法正确的是（）。

A:f(n)=O(n)B:f(n)=O(1/n)C:f(n)=O(n^2)D:f(n)=O(n^3)

答案:f(n)=O(n);f(n)=O(n^2);f(n)=O(n^3)

第二章测试

递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。

A:错B:对

答案:对

已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是()。

A:计算50个1的和。B:计算1到50的乘积。C:计算斐波拉契数列的第50个元素的值。D:计算1到50的和。

答案:计算1到50的和。

递归的优点包括()。

A:容易用数学归纳法来证明算法的正确性B:可读性强C:结构清晰D:运行效率高

答案:容易用数学归纳法来证明算法的正确性;可读性强;结构清晰

在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动()步。

A:32B:28C:31D:41

答案:31

分治法能解决的问题一般具有（）等特征。

A:分解出的子问题的解可以合并为原问题的解B:最优子结构C:该问题缩小到一定程度时可以容易地解决D:子问题相互独立

答案:分解出的子问题的解可以合并为原问题的解;最优子结构;该问题缩小到一定程度时可以容易地解决;子问题相互独立

在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。

A:错B:对

答案:对

给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=()。

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

答案:O(n^2)

已知某楼房共20层，如果采用二分查找，请问最多猜()次就能猜出任意一个楼层。

A:4B:6C:5D:3

答案:5

关于快速排序的时间复杂度，()是正确的。

A:在最好情况下时间复杂度为O(nlogn)B:在平均情况下时间复杂度为O(nlogn)C:在最坏情况下时间复杂度为O(n^2)D:在平均情况下时间复杂度为O(n^2)

答案:在最好情况下时间复杂度为O(nlogn);在平均情况下时间复杂度为O(nlogn);在最坏情况下时间复杂度为O(n^2)

快速排序是对传统排序算法()的一种改进。

A:冒泡排序B:归并排序C:插入排序D:选择排序

答案:冒泡排序

第三章测试

能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是()。

A:贪心选择性质B:重叠子问题C:最优子结构D:递归调用

答案:重叠子问题;最优子结构

关于备忘录法，以下说法正确的是()。

A:备忘录法的控制结构与直接使用递归方法的控制结构相同。B:备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。C:备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。D:备忘录法可以避免相同子问题的重复求解。

答案:备忘录法的控制结构与直接使用递归方法的控制结构相同。;备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。;备忘录法可以避免相同子问题的重复求解。

字符序列abcde与字符序列abdge的最长公共子序列长度为()，最长公共子串长度为()。

A:3,5B:4,1C:4,2D:4,6

答案:4,2

使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为()。

A:O(m^n)B:O(nlogm)C:O(n*m)D:O(n^2)

答案:O(n*m)

输入数组（-1,0,1,-2,3），它的最大子段和是()。

A:1B:2C:3D:4

答案:3

序列（1，7，3，4，9，2，3）的最长递增子序列的长度为()。

A:3B:1C:2D:4

答案:4

使用穷举法求解最长递增子序列的时间复杂度为()。

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

答案:O(n*2^n)

使用动态规划算法求最大子段和的时间复杂度为()。

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

答案:O(n)

某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目()可以使总收益最大。（不允许部分投资某个项目）

A:CB:BC:DD:A

答案:C;B;D

在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。

A:错B:对

答案:对

第四章测试

能够使用贪心算法求解的问题需具备的基本要素包括()。

A:递归调用B:贪心选择性质C:最优子结构性质D:重复子问题E:平衡子问题

答案:贪心选择性质;最优子结构性质

下列关于贪心算法与动态规划算法说法正确的是()。

A:贪心算法与动态规划算法求解的问题都具备最优子结构性质B:贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质C:贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质D:贪心算法与动态规划算法求解的问题都具有重复子问题性质

答案:贪心算法与动态规划算法求解的问题都具备最优子结构性质;贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质

在解决活动安排问题时应首先对活动进行排序，排序的依据是()。

A:按照活动结束时间降序排列B:按照活动结束时间升序排列C:按照活动开始时间降序排列D:按照活动开始时间升序排列

答案:按照活动结束时间升序排列

使用贪心算法求解最优装载问题，其时间复杂度为()。

A:O(nlogn)B:O(n2n)C:O(n3n)D:O(n5n)

答案:O(nlogn)

()能够使用贪心算法求解。

A:最优装载问题B:单源最短路径问题C:部分背包问题D:0-1背包问题E:最小生成树问题F:活动安排问题

答案:最优装载问题;单源最短路径问题;部分背包问题;最小生成树问题;活动安排问题

0-1背包问题与部分背包问题的区别在于()。

A:若用贪心算法解决0-1背包问题，只能得到近似最优解B:在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分C:没有区别，它们的含义相同D:若用贪心算法解决部分背包问题，只能得到近似最优解

答案:若用贪心算法解决0-1背包问题，只能得到近似最优解;在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分

在求解部分背包问题时采用的贪心策略是()。

A:选择价值最大的物品B:选择重量最轻的物品C:选择单位重量下价值最大的物品D:选择单位价值下重量最大的物品

答案:选择单位重量下价值最大的物品

Dijkstra算法可用于求解()。

A:单源最短路径问题B:单终点最短路径问题C:单对顶点最短路径问题D:每对顶点间最短路径问题

答案:单源最短路径问题;单终点最短路径问题;单对顶点最短路径问题;每对顶点间最短路径问题

Prim算法适合稀疏图，其时间复杂度只与边的数目有关。

A:对B:错

答案:错

在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为()。

A:-1B:0C:无穷小D:无穷大

答案:无穷大

第五章测试

回溯法中的剪枝函数包括()。

A:约束函数B:限界函数C:虚函数D:随机数生成函数E:静态函数F:递归函数

答案:约束函数;限界函数

回溯法采用的搜索策略是()。

A:广度优先搜索B:深度优先搜索C:层次搜索D:启发式搜索

答案:深度优先搜索

回溯法的主要用途包括求问题的所有解、求问题的最优解和求问题的任一解。

A:对B:错

答案:对

马的遍历问题能否有可行解，与()有关。

A:棋盘大小B:马的遍历顺序C:马的初始位置D:马的遍历深度

答案:棋盘大小;马的初始位置

在N皇后问题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是()。

A:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。B:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。C:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相减的值相同。D:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相加的值相同。

答案:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。;对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。

四皇后问题一共有2个可行解，八皇后问题一共有76个可行解。

A:错B:对

答案:错

用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵()。

A:高为m的n叉树B:高为n的n叉树C:高为n的m叉树D:高为m的m叉树

答案:高为n的m叉树

任何一张地图只用()种颜色就能使具有共同边界的国家着上不同的颜色。

A:3B:4C:6D:2

答案:4

使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。

A:对B:错

答案:对

关于使用回溯法求解0-1背包问题，以下说法正确的是()。

A:使用约束函数剪去不合理的右子树（不装该物品）。B:使用约束函数剪去不合理的左子树（装该物品）。C:使用限界函数剪去得不到更优解的左子树（装该物品）。D:使用限界函数剪去得不到更优解的右子树（不装该物品）。

答案:使用约束函数剪去不合理的左子树（装该物品）。;使用限界函数剪去得不到更优解的右子树（不装该物品）。

第六章测试

分支限界法采用的搜索策略是()。

A:递归搜索B:广度优先搜索C:深度优先搜索D:启发式搜索

答案:广度优先搜索

根据活结点表的组织方式不同，分支限界法包括()等形式。

A:队列式分支限界法B:单调队列式分支限界法C:优先队列式分支限界法D:二叉树式分支限界法E:栈式分支限界法

答案:队列式分支限界法;优先队列式分支限界法

关于回溯法和分支限界法，以下说法正确的是()。

A:回溯法通常用于求满足约束条件的所有解B:分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解C:在分支限界法中，每个结点只有一次成为扩展结点的机会D:在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出

答案:回溯法通常用于求满足约束条件的所有解;分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解;在分支限界法中，每个结点只有一次成为扩展结点的机会;在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出

应用分支限界法的三个关键问题包括()。

A:如何确定最优解的解向量B:如何设计合适的剪枝函数C:如何组织活结点表D:如何限制搜索的层次

答案:如何确定最优解的解向量;如何设计合适的剪枝函数;如何组织活结点表

关于分支限界法的基本思想，下列描述正确的是()。

A:那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中B:从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程C:活结点一旦