算法设计与分析(北京航空航天大学) 中国大学mooc慕课答案2024版 m263274

01 算法绪论篇 第1章单元测验

1、 函数用记号可表示为______

答案:

2、 函数用记号可表示为______

答案:

3、 函数用记号可表示为______

答案:

4、 函数用记号可表示为______

答案:

5、 函数用记号可表示为______

答案:

6、 函数用记号可表示为______

答案:

7、 下述伪代码希望求出数组中数字出现的次数，则伪代码空白处应填入__输入：数组，数字输出：在数组中出现的次数for  to   if   then      ______  endendreturn 

答案:

8、 函数用记号可表示为______

答案: ;
;

9、 函数用记号可表示为______

答案: ;
;
;

10、 函数用记号可表示为______

答案: ;

02 分而治之篇I 第2章单元测验

1、 在归并排序算法中，若每次分解将长度为 n 的数组分为两段，长度分别为 n-1 和 1，此时归并排序算法的时间复杂度为____

答案:

2、 在归并排序算法中，若每次分解将长度为 n 的数组分为四段长度为 n/4 的子数组进行递归，此时归并排序算法的时间复杂度为____

答案:

3、 归并排序的最好情况时间复杂度为____

答案:

4、 的解为=——

答案:

5、 的解为 ____

答案:

6、 的解为____

答案:

7、 的解为____

答案:

8、 的解为____

答案:

9、 在最大子数组问题的优化枚举算法中，每次计算子数组 X[i..j] 之和的时间复杂度为____

答案:

10、 在最大子数组问题的分治算法中，若可以用 O(1) 的时间求得跨越中点的最大子数组，则该算法的时间复杂度为

答案:

03 分而治之篇II 第3章单元测验

1、 数组中的逆序对个数为____

答案: 5

2、 长度为的数组中逆序对个数最多为____

答案:

3、 快速排序算法的最坏情况时间复杂度为____

答案:

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

答案:

5、 随机化快速排序算法的最坏情况时间复杂度为____（请选择最准确的答案）

答案:

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

答案:

7、 快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____输入：数组，起始位置，终止位置输出：划分位置  while  dowhile  and  do     endif   then     endwhile  and  do     endif  then              endendreturn 

答案:

8、 下面给出了计算Fibonacci数列第项的伪代码，该算法的时间复杂度为____（请选择最准确的答案） 输入：数字输出：Fibonacci数列的第项  if  or  then      return   else      return   end

答案:

9、 随机化次序选择算法的最坏情况时间复杂度为____（请选择最准确的答案）

答案:

10、 随机化次序选择算法的期望时间复杂度为____（请选择最准确的答案）

答案:

04 动态规划篇I 第4章单元测验

小提示:本节包含奇怪的同名章节内容

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

答案: 25

2、 在商品个数为、背包容量为的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为____ 

答案:      

3、 0-1背包问题中的递推式为____  

答案:

4、 下面给出了0-1背包问题的动态规划算法伪代码，其中空白处应分别填入____输入：商品数量 ,各商品价值，各商品体积，背包容量 输出：商品价格的最大值，最优解方案创建二维数组for  do    endfor  do            endfor  do    for          do        if  then                                               end        else                                end    end end for          do    if  then        print 选择商品            end    else        print 不选择商品    endendreturn ,

答案:

5、 设计动态规划算法的一般步骤为____  

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

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

答案:

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

答案:

8、 在最大子数组问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入__   _输入：数组 ，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化//动态规划for          do  if   then                              end  else                      endend

答案:

9、 在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入__    _输入：数组 ，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化计算数组和数组//查找解        for         do    if  then                                            endendreturn 

答案:

10、 对于包含个正数元素的数组，我们希望找出数组中的一些元素，使得这些元素在数组中互不相邻并且元素之和最大。例如在数组中，应当选择和，元素之和为。给出该问题的解决算法如下，空白处应填入____输入：正数数组，元素个数输出：选择的元素，最大不相邻元素之和创建数组，表示数组中的最大不相邻元素之和创建数组记录选择方案if  then                        endelse                    endfor  do    if          then                             end    else                    endendreturn   

答案:

11、 在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入__    _

输入：数组 ，数组长度
输出：最大子数组和，子数组起止位置
新建一维数组和
对初始化
计算数组和数组
//查找解
        
for         do
    if  then
        
                
                
    end
end
return 

答案:

05 动态规划篇II 第5章单元测验

1、 给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____

答案: gorthm   thm 

2、 在最长公共子序列问题中，我们用表示序列和序列的最长公共子序列长度，则递推式应为____ 

答案:

3、 给出最长公共子序列问题的部分伪代码如下，其中空白处应分别填入____输入：两个序列输出：的最长公共子序列分别代表的序列长度//初始化新建二维数组for  do    endfor  do            endfor  do    for  do        if  then                                                end        else if          then                                end        else                                end    endend

答案:

4、 在最长公共子串问题的递推式中，表示____

答案: 和中以和结尾的最长公共子串的长度

5、 最长公共子串问题的递推式为        

答案:

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

答案:

7、 在支持插入、删除、替换三种操作的最小编辑距离问题中，我们用表示字符串变为的最小编辑距离，则递推式应为        

答案:

8、 在支持插入、删除、替换三种操作的最小编辑距离问题中，用数组来记录编辑方案。则数组中的”L”,”U”,”LU”分别代表哪种操作___    

答案: 插入          删除      替换/空操作

9、 字符串“algorithm”到字符串“altruistic”的最小编辑距离为___   

答案: 6

10、 下面给出了最长公共子序列问题中输出最长公共子序列的函数Print-LCS()伪代码，其中空白处应分别填入____输入：追踪数组，序列，当前位置和 输出：的最长公共子序列if          then    return endif  then    Print-LCS(,,        ,        )    print else if     then    Print-LCS(,,,)endelse    Print-LCS(,,,)end 

答案:

06 动态规划篇III 第6章单元测验

1、 在钢条切割问题中，若钢条长度为，且长度从到的钢条价格分别为。则切割后钢条的最大总收益为____    

答案:

2、 在矩阵链乘法问题中，矩阵链中矩阵的规模分别为。则该矩阵链所需标量乘法的最小次数为____次

答案:

3、 在钢条切割问题中，表示切割长度为的钢条可得最大总收益，表示长度为的钢条的价格，则递推式为____ 

答案:

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

答案:

5、 下面给出了钢条切割问题的动态规划算法中追踪最优方案部分的伪代码，其中空白处应分别填入____//输出最优方案while        do    print                    end

答案:

6、 在矩阵链乘法问题中，表示计算矩阵链所需标量乘法的最小次数，则该问题的递推式为____   

答案:

7、 在矩阵链乘法问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入___  输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和//初始化                  for  then           end

答案:

8、 在矩阵链乘法问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入       输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和初始化//动态规划for          do    for  do                for          do                                if  then                                            end        end    endendreturn 

答案:

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

答案:

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

答案:  

07 贪心策略篇 第7章单元测验

1、 在部分背包问题中，若背包容量为，有个物品可供选择。每个物品价格分别为，体积分别为。则该背包可容纳物品最大总价格为___    _ 

答案:

2、 下面给出了部分背包问题的贪心算法的伪代码，其中空白处应分别填入          输入：商品数量,各商品的价值,各商品的体积，背包容量输出：商品价格的最大值计算商品性价比并按降序排序// 分别表示性价比第大的商品的性价比、价格和体积//根据贪心策略求解while  do    if  then        选择商品                            end    else         选择体积的商品                            end            endreturn 

答案:

3、 给出共5个字符，其出现频数(千次)分别为。按照课程中所讲左0右1，左小右大的规则建树编码，则字符串的霍夫曼编码应为____ 

答案:

4、 下面给出了霍夫曼编码问题的算法的伪代码，其中空白处应分别填入___   输入：各字符频数，字符数 输出：霍夫曼编码树//预处理将递增排序新建结点数组for  do            endfor  do    新建结点                                         endreturn 

答案:

5、 在活动选择问题中，给出6个活动其时间分别为,则最多能安排活动数为____ 

答案:

6、 下面给出了活动选择问题的算法的伪代码，其中空白处应分别填入____   输入：活动集合 ,每个活动的起止时间输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动for  do    if          then                              endendreturn 

答案:

7、 在加权活动选择问题中，给出个活动其时间分别为  ,权重分别为,则安排权重最大和为___

答案:

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

答案:

9、 给出加权活动选择问题部分伪代码如下，空白处应填入__   _输入：活动集合,每个活动的起止时间，权重输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动for  do    二分查找求解end新建数组                  //动态规划for  do    if  then                            end    else                             endendreturn 

答案:

10、 给出加权活动选择问题输出方案部分伪代码如下，空白处应填入____ //输出方案while  do    if  then        print 选择                    end    else                   endend

答案:

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。

,

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

答案: ①;
③

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

答案: ①;
②;
④

09 图算法篇II 第9章单元测试

1、 有向图上包含个顶点的强连通分量应至少包含____条边。

答案:

2、 已知有向图有个顶点，且所有顶点入度之和与所有顶点出度之和相加为，则该图有____条边

答案:

3、 下面有向图中存在强连通分量，可以将每个强连通分量看作一个点，得到新的图。则中存在        个点   

答案:

4、 下面给出了使用深度优先搜索(DFS)求强连通分量的部分伪代码，其中空白处应分别填入____ 

答案:

5、 给出判断有向图中是否存在环的算法伪代码如下，空白处应填入____  

答案:

6、 给出深度优先搜索（DFS）进行拓扑排序的算法如下，则空白处应填入____ 

答案:            向结尾追加              向结尾追加

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

答案:

8、 上题中判断有向无环图（DAG）是否存在哈密顿路径的算法的时间复杂度是____（请选择最准确项）

答案:

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

答案: 树边     ;
前向边       ;
后向边 ;
横向边

10、 对如下所示有向图进行拓扑排序，得到一个拓扑序如下图中所示。其中空白处可以依次填入        三个字母。（多选）  

答案: ;

10 图算法篇III 第10章单元测试

1、 对如下所示连通无向图 ，其最小生成树的权重为         

答案: 23

2、 如下所示带权的无向连通图，存在割将图的顶点集划分为两个点集和。则该割有        条横跨边，有        条轻边。

答案:

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

答案:

4、 同上题所示带权的连通无向图 ，使用Kruskal算法求图的最小生成树时，边按选项所示次序被选中，其中次序正确的选项是        。

答案:

5、 给出求最小生成树中时间复杂度为的Kruskal算法伪代码如下，则空白处应填入____ 

答案:

6、 给出求最小生成树的Prim算法（不使用优先队列）伪代码如下，则空白处应填入____

答案:

7、 不使用优先队列和使用优先队列的Prim算法的时间复杂度分别为        （请选择最准确项）

答案:

8、 不相交集合的Create-Set操作和Find-Set操作的时间复杂度分别为        、        。Kruskal算法的时间复杂度为        。（请选择最准确项）  

答案:

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

答案:

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

答案:

11 图算法篇IV 第11章单元测试

1、 下图存在多条从源点 到顶点的最短路径，在Dijkstra算法运行过程中首先找到的最短路径是          。

答案:

2、 下图应选择        算法求最短路径，求得从a到z的最短路径边权和为____ 

答案:

3、 Dijkstra算法(使用优先队列)和Bellman-ford算法的时间复杂度分别是____（请选择最准确项）

答案:

4、 给出Dijkstra算法(使用优先队列)伪代码如下，空白处应填入____ 

答案:

5、 给出Bellman-Ford算法伪代码如下，则空白处应填入____

答案:

6、 解决所有点对最短路径问题的Floyd-Warshall算法的时间复杂度是          ，空间复杂度是           。（请选择最准确项）

答案:

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

答案:

8、 给定带权无向图实例如下图所示。使用Floyd-Warshall算法解决所有点对最短路径问题。在该实例运行过程中，计算后的数组与数组如下图所示。则继续计算后,           。 

答案:

9、 相等关系是具有传递性的，即若,则有。给定变量集合，二元组集合描述其中一些变量的相等关系，可使用Floyd算法 解决判断任意两变量间是否相等的问题。给出算法伪代码如下，则空白处应填入____。 

答案:

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

答案:

12 图算法篇Ⅴ 第12章单元测试

小提示:本节包含奇怪的同名章节内容

1、 对如下所示二分图，其最大匹配数为        

答案:

2、 给定无向图，如何判断该图是否为二分图？可以用两种颜色给图上顶点染色，若任意相邻顶点颜色均不相同，则该无向图是二分图。给出判断无向图是否为二分图的算法伪代码如下，空白处应填入        。

答案:

3、 求二分图最大匹配问题的匈牙利算法伪代码如下，则空白处应填入____

答案:

4、 二分图最大匹配问题的匈牙利算法的时间复杂度是____（请选择最准确项）

答案:

5、 给出一个矩阵，行数与列数均为,其中每个元素都是0或1。现在有两种操作分别是交换任意两行或交换任意两列。请判断是否可以通过任意次以上两种操作使得矩阵主对角线（左上角到右下角）全部为1。观察符合条件的矩阵，可以发现在此类矩阵中，总能从每一行都挑选一个为1的元素，且这些元素都分布在不同列。可将该问题转换为二分图的匹配问题，给出算法伪代码如下，则空白处应填入____  

答案:

6、 给出流网络有向图  如下所示，则该流网络的最小割为          ，该最小割的横跨边是          。 

答案:

7、 给出流网络有向图如下所示，将其转换为残存图，则边上空白处①②③④的值分别应为        ，该流网络上继续寻找增广路径，下一条增广路径最多可增加流量          。

答案:

8、 求最大流问题的Ford-Fulkerson算法伪代码如下，则空白处应填入____ 

答案:

9、 最大流问题的Ford-Fulkerson算法的时间复杂度是____（请选择最准确项）

答案:

10、 现有题库包含k种类型题目共n道，按要求从其中抽取m道题目组成试卷。已知题库表示第道题目覆盖类型。组卷要求表示卷子中第种类型题目应有道。求符合要求的组卷方案，若不存在解则输出“No Solution”。该问题可转化为最大流问题解决，将题目与题目类型分别抽象为两列点，左侧与右侧添加一源点和汇点，源点与题目连边，边权为1；题目与该题覆盖类型连边，边权为1；类型与汇点连边，边权为该类型题目所需数量。如下图实例所示。 给出算法伪代码如下，空白处应填入          

答案:

11、 给定无向图，如何判断该图是否为二分图？可以用两种颜色给图上顶点染色，若任意相邻顶点颜色均不相同，则该无向图是二分图。给出判断无向图是否为二分图的算法伪代码如下，空白处应填入        。

答案:

12、 给出流网络有向图  如下所示，则该流网络的最小割为          ，该最小割的横跨边是          。 

答案:

13、 求最大流问题的Ford-Fulkerson算法伪代码如下，则空白处应填入____ 

答案:

不知道怎么购买？点此查看购买教程！