算法设计与分析-北京航空航天大学中国大学mooc课后章节答案期末考试题库2023年

算法设计与分析_北京航空航天大学中国大学mooc课后章节答案期末考试题库2023年对如下所示连通无向图【图片】，其最小生成树的权重为【图片】

参考答案:

23

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

参考答案:

树边_前向边_后向边_横向边

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

参考答案:

25

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

参考答案:

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

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

参考答案:

gorthm

thm

在最长公共子串问题的递推式中，【图片】表示____

参考答案:

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

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

参考答案:

插入

删除

替换/空操作

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

参考答案:

6

数组【图片】中的逆序对个数为____

参考答案:

5

在上题中，均不在搜索树中的边有哪些____（多选）

参考答案:

_

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

参考答案:

①_②

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

参考答案:

①_③

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

参考答案:

①_②_④

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

参考答案:

向结尾追加

向结尾追加

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

参考答案:

13

函数【图片】用【图片】记号可表示为______

参考答案:

_

已知无向图【图片】是包含【图片】棵树的森林，且该图顶点数与边数相加之和为【图片】即【图片】。则该森林顶点数【图片】为____

参