【MOOC】《算法设计与分析》(北京航空航天大学)章节测验作业慕课答案

【MOOC】《算法设计与分析》(北京航空航天大学)章节测验作业慕课答案01算法绪论篇第1章单元测验1.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】2.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】3.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】4.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】5.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】6.单选题：下述伪代码希望求出数组中数字出现的次数，则伪代码空白处应填入______输入：数组，数字输出：在数组中出现的次数fortoifthen________endendreturn

选项：

A、

B、

C、

D、

答案：【】7.单选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【】8.多选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【;】9.多选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【;;;】10.多选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【;;】02分而治之篇I第2章单元测验1.单选题：的解为____

选项：

A、

B、

C、

D、

答案：【】2.单选题：的解为____

选项：

A、

B、

C、

D、

答案：【】3.单选题：的解为=——

选项：

A、

B、

C、

D、

答案：【】4.单选题：归并排序的最好情况时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】5.单选题：在归并排序算法中，若每次分解将长度为n的数组分为四段长度为n/4的子数组进行递归，此时归并排序算法的时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】6.单选题：在归并排序算法中，若每次分解将长度为n的数组分为两段，长度分别为n-1和1，此时归并排序算法的时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】7.单选题：在最大子数组问题的分治算法中，若可以用O(1)的时间求得跨越中点的最大子数组，则该算法的时间复杂度为

选项：

A、

B、

C、

D、

答案：【】8.单选题：在最大子数组问题的优化枚举算法中，每次计算子数组X[i..j]之和的时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】9.单选题：的解为____

选项：

A、

B、

C、

D、

答案：【】10.单选题：的解为____

选项：

A、

B、

C、

D、

答案：【】03分而治之篇II第3章单元测验1.单选题：随机化次序选择算法的期望时间复杂度为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】2.单选题：数组中的逆序对个数为____

选项：

A、4

B、5

C、6

D、7

答案：【5】3.单选题：随机化次序选择算法的最坏情况时间复杂度为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】4.单选题：下面给出了计算Fibonacci数列第项的伪代码，该算法的时间复杂度为____（请选择最准确的答案）输入：数字输出：Fibonacci数列的第项iforthenreturnelsereturnend

选项：

A、

B、

C、

D、

答案：【】5.单选题：快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____输入：数组，起始位置，终止位置输出：划分位置whiledowhileanddoendifthenendwhileanddoendifthenendendreturn

选项：

A、

B、

C、

D、

答案：【】6.单选题：随机化快速排序算法的期望时间复杂度为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】7.单选题：随机化快速排序算法的最坏情况时间复杂度为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】8.单选题：在快速排序算法中，假定存在一个神奇的黑盒可以在O(1)的时间内给出最好的主元（也就是中位数），那么使用此神奇黑盒的快速排序算法最差运行时间为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】9.单选题：快速排序算法的最坏情况时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】10.单选题：长度为的数组中逆序对个数最多为____

选项：

A、

B、

C、

D、

答案：【】04动态规划篇I第4章单元测验1.单选题：设计动态规划算法的一般步骤为____

选项：

A、递推关系建立→问题结构分析→自上向下计算→最优方案追踪

B、递推关系建立→问题结构分析→自底向上计算→最优方案追踪

C、问题结构分析→递推关系建立→自上向下计算→最优方案追踪

D、问题结构分析→递推关系建立→自底向上计算→最优方案追踪

答案：【问题结构分析→递推关系建立→自底向上计算→最优方案追踪】2.单选题：下面给出了0-1背包问题的动态规划算法伪代码，其中空白处应分别填入____输入：商品数量,各商品价值，各商品体积，背包容量输出：商品价格的最大值，最优解方案创建二维数组fordoendfordoendfordofordoifthenendelseendendendfordoifthenprint选择商品endelseprint不选择商品endendreturn,

选项：

A、

B、

C、

D、

答案：【】3.单选题：0-1背包问题中的递推式为____

选项：

A、

B、

C、

D、

答案：【】4.单选题：在商品个数为、背包容量为的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为____

选项：

A、

B、

C、

D、

答案：【】5.单选题：在0-1背包问题中，若背包容量为20,5个物品的体积分别为，价格分别为。则该背包能容纳物品的最大总价格为____

选项：

A、22

B、23

C、25

D、26

答案：【25】6.单选题：对于包含个正数元素的数组，我们希望找出数组中的一些元素，使得这些元素在数组中互不相邻并且元素之和最大。例如在数组中，应当选择和，元素之和为。给出该问题的解决算法如下，空白处应填入____输入：正数数组，元素个数输出：选择的元素，最大不相邻元素之和创建数组，表示数组中的最大不相邻元素之和创建数组记录选择方案ifthenendelseendfordoifthenendelseendendreturn

选项：

A、

B、

C、

D、

答案：【】7.单选题：在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入___输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化计算数组和数组//查找解fordoifthenendendreturn

选项：

A、

B、

C、

D、

答案：【】8.单选题：在最大子数组问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入___输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化//动态规划fordoifthenendelseendend

选项：

A、

B、

C、

D、

答案：【】9.单选题：在最大子数组问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入____输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和//初始化

选项：

A、

B、

C、

D、

答案：【】10.单选题：最大子数组问题的分治算法和动态规划算法的时间复杂度分别为____（请选择最准确的答案）

选项：

A、

B、

C、

D、

答案：【】05动态规划篇II第5章单元测验1.单选题：下面给出了最长公共子序列问题中输出最长公共子序列的函数Print-LCS()伪代码，其中空白处应分别填入____输入：追踪数组，序列，当前位置和输出：的最长公共子序列ifthenreturnendifthenPrint-LCS(,,,)printelseifthenPrint-LCS(,,,)endelsePrint-LCS(,,,)end

选项：

A、

B、

C、

D、

答案：【】2.单选题：字符串“algorithm”到字符串“altruistic”的最小编辑距离为___

选项：

A、8

B、7

C、6

D、5

答案：【6】3.单选题：在支持插入、删除、替换三种操作的最小编辑距离问题中，用数组来记录编辑方案。则数组中的"L","U","LU"分别代表哪种操作___

选项：

A、删除插入替换/空操作

B、插入替换/空操作删除

C、插入删除替换/空操作

D、替换/空操作删除插入

答案：【插入删除替换/空操作】4.单选题：在支持插入、删除、替换三种操作的最小编辑距离问题中，我们用表示字符串变为的最小编辑距离，则递推式应为

选项：

A、

B、

C、

D、

答案：【】5.单选题：给定两个字符串,需要判断中有多少个子序列与相等。例如：则和两个子序列都与相等。思考该问题，可以用表示的子序列中与相等的个数，如上例。则对应的递推式为___

选项：

A、

B、

C、

D、

答案：【】6.单选题：最长公共子串问题的递推式为

选项：

A、

B、

C、

D、

答案：【】7.单选题：在最长公共子串问题的递推式中，表示____

选项：

A、和是否相等

B、和中以或结尾的最长公共子串的长度

C、和中的最长公共子串的长度

D、和中以和结尾的最长公共子串的长度

答案：【和中以和结尾的最长公共子串的长度】8.单选题：给出最长公共子序列问题的部分伪代码如下，其中空白处应分别填入____输入：两个序列输出：的最长公共子序列分别代表的序列长度//初始化新建二维数组fordoendfordoendfordofordoifthenendelseifthenendelseendendend

选项：

A、

B、

C、

D、

答案：【】9.单选题：在最长公共子序列问题中，我们用表示序列和序列的最长公共子序列长度，则递推式应为____

选项：

A、

B、

C、

D、

答案：【】10.单选题：给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____

选项：

A、gorthmthm

B、thmgorthm

C、glorhthmorthm

D、orthmglorhthm

答案：【gorthmthm】06动态规划篇III第6章单元测验1.单选题：在矩阵链乘法问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入___输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和//初始化forthenend

选项：

A、

B、

C、

D、

答案：【】2.单选题：在矩阵链乘法问题中，表示计算矩阵链所需标量乘法的最小次数，则该问题的递推式为____

选项：

A、

B、

C、

D、

答案：【】3.单选题：下面给出了钢条切割问题的动态规划算法中追踪最优方案部分的伪代码，其中空白处应分别填入____//输出最优方案whiledoprintend

选项：

A、

B、

C、

D、

答案：【】4.单选题：下面给出了钢条切割问题的动态规划算法的部分伪代码，其中空白处应分别填入____输入：钢条价格表，钢条长度输出：最大收益，钢条切割方案//初始化创建一维数组fordofordoifthenendendend输出最优方案return

选项：

A、

B、

C、

D、

答案：【】5.单选题：在钢条切割问题中，表示切割长度为的钢条可得最大总收益，表示长度为的钢条的价格，则递推式为____

选项：

A、

B、

C、

D、

答案：【】6.单选题：在矩阵链乘法问题中，矩阵链中矩阵的规模分别为。则该矩阵链所需标量乘法的最小次数为____次

选项：

A、

B、

C、

D、

答案：【】7.单选题：在钢条切割问题中，若钢条长度为，且长度从到的钢条价格分别为。则切割后钢条的最大总收益为____

选项：

A、

B、

C、

D、

答案：【】8.单选题：对某仅包含左右括号的字符串而言，若其中左括号和右括号可以正确的匹配，那么称其为均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。给定一个长度为n的仅包含左右括号的字符串S，请求出字符串S的最长均衡子序列。换言之，请从S中挑选出尽量多的字符按顺序组成新字符串S'，使得S'是一个均衡字符串。例如，对字符串“())(()”而言，我们可以挑选其中第1，2，5，6个字符构成一个长度为的均衡字符串“()()”。我们用表示字符串的最长均衡子序列长度，则其递推式应为____

选项：

A、

B、

C、

D、

答案：【】9.单选题：在矩阵链乘法问题的动态规划算法中，给出追踪最优方案部分的伪代码如下，空白处应填入____Print-Matrix-Chain()输入：矩阵链,追踪数组,位置索引和输出：矩阵链加括号方式ifthenprintreturnendprint“(”Print-Matrix-Chain(,,,)print“)(”Print-Matrix-Chain(,,,)print“)”return

选项：

A、

B、

C、

D、

答案：【】10.单选题：在矩阵链乘法问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和初始化//动态规划fordofordofordoifthenendendendendreturn

选项：

A、

B、

C、

D、

答案：【】07贪心策略篇第7章单元测验1.单选题：给出加权活动选择问题输出方案部分伪代码如下，空白处应填入____//输出方案whiledoifthenprint选择endelseendend

选项：

A、

B、

C、

D、

答案：【】2.单选题：给出加权活动选择问题部分伪代码如下，空白处应填入___输入：活动集合,每个活动的起止时间，权重输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动fordo二分查找求解end新建数组//动态规划fordoifthenendelseendendreturn

选项：

A、

B、

C、

D、

答案：【】3.单选题：在加权活动选择问题中有个活动组成的集合，令表示集合中不冲突活动最大权重和，为以活动开始前最后结束的活动，为活动的权重。则递推式为____

选项：

A、

B、

C、

D、

答案：【】4.单选题：在加权活动选择问题中，给出个活动其时间分别为,权重分别为,则安排权重最大和为___

选项：

A、

B、

C、

D、

答案：【】5.单选题：下面给出了活动选择问题的算法的伪代码，其中空白处应分别填入____输入：活动集合,每个活动的起止时间输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动fordoifthenendendreturn

选项：

A、

B、

C、

D、

答案：【】6.单选题：在活动选择问题中，给出6个活动其时间分别为,则最多能安排活动数为____

选项：

A、

B、

C、

D、

答案：【】7.单选题：下面给出了霍夫曼编码问题的算法的伪代码，其中空白处应分别填入___输入：各字符频数，字符数输出：霍夫曼编码树//预处理将递增排序新建结点数组fordoendfordo新建结点endreturn

选项：

A、

B、

C、

D、

答案：【】8.单选题：给出共5个字符，其出现频数(千次)分别为。按照课程中所讲左0右1，左小右大的规则建树编码，则字符串的霍夫曼编码应为____

选项：

A、

B、

C、

D、

答案：【】9.单选题：下面给出了部分背包问题的贪心算法的伪代码，其中空白处应分别填入输入：商品数量,各商品的价值,各商品的体积，背包容量输出：商品价格的最大值计算商品性价比并按降序排序//分别表示性价比第大的商品的性价比、价格和体积//根据贪心策略求解whiledoifthen选择商品endelse选择体积的商品endendreturn

选项：

A、

B、

C、

D、

答案：【】10.单选题：在部分背包问题中，若背包容量为，有个物品可供选择。每个物品价格分别为，体积分别为。则该背包可容纳物品最大总价格为____

选项：

A、

B、

C、

D、

答案：【】08图算法篇I第8章单元测验1.单选题：无向图包含7个顶点，10条边，其邻接表和结构如下图所示。以顶点作为起点执行深度优先搜索（DFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到如下图所示搜索树。其中顶点1、2、3处应分别填入____

选项：

A、

B、

C、

D、

答案：【】2.单选题：已知图深度优先搜索（DFS）的搜索树为一棵满二叉树如下图所示，树中有个点的发现时刻和结束时刻相差。则根节点的发现时刻和结束时刻相差____

选项：

A、10

B、11

C、12

D、13

答案：【13】3.单选题：已知无向图是包含棵树的森林，且该图顶点数与边数相加之和为即。则该森林顶点数为____

选项：

A、40

B、41

C、42

D、43

答案：【42】4.单选题：无向图的一个连通分量包含个顶点，则该连通分量应至少包含____条边

选项：

A、

B、

C、

D、

答案：【】5.单选题：图的生成子图应包含个顶点，至少条边

选项：

A、

B、

C、

D、

答案：【】6.单选题：对图深度优先搜索（DFS）遍历该图的时间复杂度为____（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】7.多选题：同上题，在扇形图(FanGraph)中，其邻接表和结构如下第一张图所示。从顶点开始进行深度优先搜索（DFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到搜索树如下第二张图所示，该搜索树并未画全，应从虚线中选择____补全。（多选）

选项：

A、①

B、②

C、③

D、④

答案：【①;②;④】8.多选题：同上题，在扇形图(FanGraph)中，其邻接表和结构如下图所示。从顶点开始进行广度优先搜索（BFS），搜索时按照邻接表顺序遍历某一节点的相邻节点得到搜索树如下，该搜索树并未画全，应从虚线中选择____补全。（多选）

选项：

A、①

B、②

C、③

D、④

答案：【①;③】9.多选题：在扇形图(FanGraph)中，其邻接表和结构如下第一张图所示。从顶点开始进行广度优先搜索（BFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到搜索树如下第二张图，该搜索树并未画全，应从虚线中选择____补全。（多选）

选项：

A、①

B、②

C、③

D、④

答案：【①;②】10.多选题：在上题中，均不在搜索树中的边有哪些____（多选）

选项：

A、

B、

C、

D、

答案：【;】09图算法篇II第9章单元测试1.单选题：上题中判断有向无环图（DAG）是否存在哈密顿路径的算法的时间复杂度是____（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】2.单选题：图上的哈密顿路径（Hamiltonianpath）是指将所有顶点恰好包含一次的路径，如下左图所示。但并非所有图中都存在哈密顿路径，如下右图所示。现在希望设计一个算法，判断有向无环图（DAG）上是否存在哈密顿路径。给出算法的伪代码如下，空白处应填入____（提示：请思考拓扑序和哈密顿路径的关系）

选项：

A、

B、

C、

D、

答案：【】3.单选题：给出深度优先搜索（DFS）进行拓扑排序的算法如下，则空白处应填入____

选项：

A、向开头添加

B、向结尾追加向结尾追加

C、向开头添加

D、向结尾追加向结尾追加

答案：【向结尾追加向结尾追加】4.单选题：给出判断有向图中是否存在环的算法伪代码如下，空白处应填入____

选项：

A、

B、

C、

D、

答案：【】5.单选题：下面给出了使用深度优先搜索(DFS)求强连通分量的部分伪代码，其中空白处应分别填入____

选项：

A、

B、

C、

D、

答案：【】6.单选题：下面有向图中存在强连通分量，可以将每个强连通分量看作一个点，得到新的图。则中存在个点

选项：

A、

B、

C、

D、

答案：【】7.单选题：已知有向图有个顶点，且所有顶点入度之和与所有顶点出度之和相加为，则该图有____条边

选项：

A、

B、

C、

D、

答案：【】8.单选题：有向图上包含个顶点的强连通分量应至少包含____条边。

选项：

A、

B、

C、

D、

答案：【】9.多选题：对如下所示有向图进行拓扑排序，得到一个拓扑序如下图中所示。其中空白处可以依次填入三个字母。（多选）

选项：

A、

B、

C、

D、

答案：【;】10.多选题：对如下所示有向图，从点开始进行深度优先搜索（DFS），搜索时按照字典序遍历某一节点的相邻节点。在得到的深度优先搜索树中，包含如下哪些类别的边（多选）

选项：

A、树边

B、前向边

C、后向边

D、横向边

答案：【树边;前向边;后向边;横向边】10图算法篇III第10章单元测试1.单选题：如下所示带权的无向连通图，存在割将图的顶点集划分为两个点集和。则该割有条横跨边，有条轻边。

选项：

A、

B、

C、

D、

答案：【】2.单选题：对如下所示连通无向图，其最小生成树的权重为

选项：

A、21

B、23

C、25

D、27

答案：【23】3.单选题：对带权的连通无向图，将所有点划分为个树，且个树的总边权之和最小,若无法划分为棵树则输出“NoAnswer”。如下图所示，若，则应按照图中颜色区分划分为棵树，边权之和为。利用Kruskal算法解决该问题的伪代码如下，则空白处应填入____。

选项：

A、

B、

C、

D、

答案：【】4.单选题：不相交集合的Find-Set操作的时间复杂度与树的高度有关。如下图所示，查询节点时，图右的树结构显然较图左的树结构更为高效。我们可以通过改写Find-Set操作函数优化树结构，该技巧也被称为“路径压缩”。该技巧主要思想是将查询点到根节点路径上的所有节点都直接连接在根节点下，如图所示将路径中的节点都直接连接在节点下。则改写后算法伪代码空白处应填入。

选项：

A、

B、

C、

D、

答案：【】5.单选题：不相交集合的Create-Set操作和Find-Set操作的时间复杂度分别为、。Kruskal算法的时间复杂度为。（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】6.单选题：不使用优先队列和使用优先队列的Prim算法的时间复杂度分别为（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】7.单选题：给出求最小生成树的Prim算法（不使用优先队列）伪代码如下，则空白处应填入____

选项：

A、

B、

C、

D、

答案：【】8.单选题：给出求最小生成树中时间复杂度为的Kruskal算法伪代码如下，则空白处应填入____

选项：

A、

B、

C、

D、

答案：【】9.单选题：同上题所示带权的连通无向图，使用Kruskal算法求图的最小生成树时，边按选项所示次序被选中，其中次序正确的选项是。

选项：

A、

B、

C、

D、

答案：【】10.单选题：同上题所示带权的连通无向图，从点开始使用Prim算法求图的最小生成树。已求得边集,则接下来应被添加进集合的安全边为。

选项：

A、

B、

C、

D、

答案：【】11图算法篇IV第11章单元测试1.单选题：给定带权无向图实例如下图所示。使用Floyd-Warshall算法解决所有点对最短路径问题。在该实例运行过程中，计算后的数组与数组如下图所示。则继续计算后,。

选项：

A、

B、

C、

D、

答案：【】2.单选题：给定带权无向图，在所有点对最短路径问题的Floyd-Warshall算法中，使用表示可从前个点中选点经过时到的最短距离。则该算法中的递推关系式是。

选项：

A、

B、

C、

D、

答案：【】3.单选题：解决所有点对最短路径问题的Floyd-Warshall算法的时间复杂度是，空间复杂度是。（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】4.单选题：给出Bellman-Ford算法伪代码如下，则空白处应填入____

选项：

A、

B、

C、

D、

答案：【】5.单选题：给出Dijkstra算法(使用优先队列)伪代码如下，空白处应填入____

选项：

A、

B、

C、

D、

答案：【】6.单选题：Dijkstra算法(使用优先队列)和Bellman-ford算法的时间复杂度分别是____（请选择最准确项）

选项：

A、

B、

C、

D、

答案：【】7.单选题：下图应选择算法求最短路径，求得从a到z的最短路径边权和为____

选项：

A、

B、

C、

D、

答案：【】8.单选题：下图存在多条从源点到顶点的最短路径，在Dijkstra算法运行过程中首先找到的最短路径是。

选项：

A、

B、

C、

D、

答案：【】9.单选题：给定带权无向图，定义无向图的最小环为：(1)环上至少包含3个点（2）环上点不重复（3）环上所有边的权值之和最小。可借鉴Floyd算法解决该问题，给出伪代码如下，空白处应填入。