【MOOC期末】《算法设计与分析》(北京航空航天大学)期末测试慕课答案

【MOOC期末】《算法设计与分析》(北京航空航天大学)期末测试慕课答案算法设计与分析期末考试1.单选题：对某仅包含左右括号的字符串而言，若其中左括号和右括号可以正确的匹配，那么称其为均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。给定一个长度为n的仅包含左右括号的字符串S，请求出字符串S的最长均衡子序列。换言之，请从S中挑选出尽量多的字符按顺序组成新字符串S'，使得S'是一个均衡字符串。例如，对字符串“())(()”而言，我们可以挑选其中第1，2，5，6个字符构成一个长度为4的均衡字符串“()()”。我们用表示字符串的最长均衡子序列长度，则其递推式应为____

选项：

A、

B、

C、

D、

答案：【】2.单选题：有一串特殊的能量项链，上面有N颗能量珠。每颗能量珠上都有两个正整数作为头标记和尾标记。对于相邻的两颗珠子，保证前一颗珠子的尾标记一定等于后一颗珠子的头标记。两颗珠子可以聚合成一颗珠子，同时释放出能量。如果前一颗能量珠的头标记为a，尾标记为b，后一颗能量珠的头标记为b，尾标记为c，则聚合后释放的能量为，新产生的珠子的头标记为a，尾标记为c。现在我们要通过不断聚合相邻珠子直到项链上只剩1颗珠子来获取能量。显然，不同的聚合顺序能获得不同的能量。请你设计聚合顺序使得释放总能量最大。例如：N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。应先将第1颗和第4颗合并，然后再依次和第2颗、第3颗合并。可得到总能量为。则下面给出的伪代码中空白处应填入

选项：

A、

B、

C、

D、

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

选项：

A、

B、

C、

D、

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

选项：

A、

B、

C、

D、

答案：【】5.单选题：在支持插入、删除、替换三种操作的最小编辑距离问题中，字符串“algorithm”到字符串“altruistic”的最小编辑距离为____

选项：

A、8

B、7

C、6

D、5

答案：【6】6.单选题：动态规划算法中，最优子结构的性质是指

选项：

A、问题的最优解等于子问题的最优解

B、问题的最优解可以由子问题的最优解组合而成，子问题可以独立求解

C、问题的最优解影响子问题的最优解，问题的最优解可以由子问题的最优解组合而成

D、问题的最优解不影响子问题的最优解，问题的最优解等于子问题的最优解

答案：【问题的最优解可以由子问题的最优解组合而成，子问题可以独立求解】7.单选题：随机化次序选择算法的期望时间复杂度为____

选项：

A、

B、

C、

D、

答案：【】8.单选题：将一个凸多边形划分为多个三角形，且划分线不交叉，有多少种划分方法？三角形有1种划分方法，四边形有2种划分方法…该问题是典型的卡特兰数应用问题，已知卡特兰数有如下递推关系：给出计算的伪代码如下，则该算法时间复杂度为(请选择最准确项)

选项：

A、

B、

C、

D、

答案：【】9.单选题：给定至少含3个点的有向图，包含两点点与点(与无直接连边)。删去图中除两点以外的一些点，使得与不连通。则最少删去几个点？尽管该问题是通过删点操作使得图不连通，但与图问题中“割”的定义仍有相似之处。我们可以通过将点拆分为边，如下图上部分所示。通过拆点从而将该问题转化为最小割问题，如下图下部分所示。则转化后，边的容量应设置为，其余边的容量应设置为

选项：

A、

B、

C、

D、

答案：【】10.单选题：相等关系具有传递性，类似的，大于关系（小于关系）也具有传递关系：若有则。给定不等式集合包括个变量，个不等式，每个不等式形式为或。判断这个不等式是否有矛盾。给出算法伪代码如下，则空白处应填入

选项：

A、

B、

C、

D、

答案：【】11.单选题：图是有向无环图。s和t是图G上的两个顶点。现在设计一个算法来计数从s到t的不同路径个数。如下图示例，从s到t共有6条不同路径。给出算法伪代码如下，其中空白处应填入

选项：

A、

B、

C、

D、

答案：【】12.单选题：无向连通图,每条边的权值均为非负数。为图的一个最小生成树。现在向图中添加一条新的边，其权值为。现在设计一个算法测试是否仍为新得到的图的最小生成树，若仍是新图的最小生成树则返回，否则返回。算法伪代码如下所示。则空白处应填入

选项：

A、

B、

C、

D、

答案：【】13.单选题：老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。假设每个题目均需要花费一天的时间来完成，这期间无法完成其他题目。请你设计算法指定题目的完成计划，从而使总的得分最大。下面给出一个包含了7个题目及相应的分数、截止日期的实例：题目1234567截止日期（天）1133224分数6721451对该实例而言，得分最大的作业完成方案为花费4天时间依次完成题目2,6,3,7。得分为15。对该问题应选择如下哪个贪心策略

选项：

A、对题目按截止日期升序考虑，同一截止日期优先安排高分题目。

B、对题目按截止日期降序考虑，同一截止日期优先安排高分题目。

C、对题目按照分数升序考虑，同一分数优先安排早截止题目。

D、对题目按照分数降序考虑，同一分数题目无需考虑截止日期。

答案：【对题目按照分数降序考虑，同一分数题目无需考虑截止日期。】14.单选题：在加权活动选择问题中有n个活动组成的集合，令表示集合中不冲突活动最大权重和，为以活动开始前最后结束的活动，为活动的权重。则递推式为____

选项：

A、

B、

C、

D、

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

选项：

A、36

B、39

C、42

D、45

答案：【42】16.单选题：给定n天的某支股票价格，假定第i天的价格为，为了尽可能多的赚钱，即寻找且以在第i天买进股票，在第j天卖出股票，使得最大化。给出该问题的分治部分算法伪代码如下，则空白处应填入

选项：

A、、、，三种方案中使收益最大的方案

B、、、，三种方案中使收益最大的方案

C、、、，三种方案中使收益最大的方案

D、、、，三种方案中使收益最大的方案

答案：【、、，三种方案中使收益最大的方案】17.单选题：归并排序算法中的合并操作是将2段有序序列通过不断比较两序列首元素大小，合并为1段有序序列。k路归并排序与合并操作相似，给定k个有序序列，总长度为n（）。用优先队列来维护k个有序序列的首元素，每次从优先队列中取出列首元素加入整体有序序列。从而将k个有序序列合并为1个长度为n的有序序列。那么k路归并排序算法的时间复杂度为

选项：

A、

B、

C、

D、

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

选项：

A、

B、

C、

D、

答案：【】19.多选题：下列无向图一定是树的有（多选）

选项：

A、有n个顶点，n-1条边的图。

B、无回路的连通图。

C、连通但删去任意一条边则不连通的图。

D、每对顶点间都连通的图。

答案：【无回路的连通图。;连通但删去任意一条边则不连通的图。】20.多选题：函数用记号可表示为______

选项：

A、

B、

C、

D、

答案：【;;】21.单选题：图为无向连通图，则有。

选项：

A、正确

B、错误

答案：【正确】22.单选题：贪心算法一定能求得问题的全局最优解。

选项：

A、正确

B、错误

答案：【错误】23.单选题：分治算法将问题划分为子问题，划分子问题个数越多则时间复杂度一定越低。

选项：

A、正确

B、错误

答案：【错误】24.单选题：二分图中不存在长度为奇数的环。

选项：

A、正确

B、错误

答案：【正确】25.单选题：统一机器性能后，算法运行时间仅依赖于问题输入规模。

选项：

A、正确

B、错误

答案：【错误】26.递归式的解为

答案：【n】27.已知无向图有10条边，有4个顶点度数为3，其余顶点度数不超过2。则该图至少有个顶点

答案：【8】28.给出a,b,c,d,e共5个字符，其出现频数(千次)分别为[40,13,12,8,9]。按照课程中所讲左0右1，左小右大的规则建