【MOOC】算法设计与分析-北京航空航天大学 中国大学慕课MOOC答案

【MOOC】算法设计与分析-北京航空航天大学中国大学慕课MOOC答案第1章单元测验1、【单选题】函数用记号可表示为______本题答案：【】2、【单选题】函数用记号可表示为______本题答案：【】3、【单选题】函数用记号可表示为______本题答案：【】4、【单选题】函数用记号可表示为______本题答案：【】5、【单选题】函数用记号可表示为______本题答案：【】6、【单选题】函数用记号可表示为______本题答案：【】7、【单选题】下述伪代码希望求出数组中数字出现的次数，则伪代码空白处应填入______输入：数组，数字输出：在数组中出现的次数fortoifthen________endendreturn本题答案：【】8、【多选题】函数用记号可表示为______本题答案：【##】9、【多选题】函数用记号可表示为______本题答案：【###】10、【多选题】函数用记号可表示为______本题答案：【#】第2章单元测验1、【单选题】在归并排序算法中，若每次分解将长度为n的数组分为两段，长度分别为n-1和1，此时归并排序算法的时间复杂度为____本题答案：【】2、【单选题】在归并排序算法中，若每次分解将长度为n的数组分为四段长度为n/4的子数组进行递归，此时归并排序算法的时间复杂度为____本题答案：【】3、【单选题】归并排序的最好情况时间复杂度为____本题答案：【】4、【单选题】的解为=——本题答案：【】5、【单选题】的解为____本题答案：【】6、【单选题】的解为____本题答案：【】7、【单选题】的解为____本题答案：【】8、【单选题】的解为____本题答案：【】9、【单选题】在最大子数组问题的优化枚举算法中，每次计算子数组X[i..j]之和的时间复杂度为____本题答案：【】10、【单选题】在最大子数组问题的分治算法中，若可以用O(1)的时间求得跨越中点的最大子数组，则该算法的时间复杂度为本题答案：【】第3章单元测验1、【单选题】数组中的逆序对个数为____本题答案：【5】2、【单选题】长度为的数组中逆序对个数最多为____本题答案：【】3、【单选题】快速排序算法的最坏情况时间复杂度为____本题答案：【】4、【单选题】在快速排序算法中，假定存在一个神奇的黑盒可以在O(1)的时间内给出最好的主元（也就是中位数），那么使用此神奇黑盒的快速排序算法最差运行时间为____（请选择最准确的答案）本题答案：【】5、【单选题】随机化快速排序算法的最坏情况时间复杂度为____（请选择最准确的答案）本题答案：【】6、【单选题】随机化快速排序算法的期望时间复杂度为____（请选择最准确的答案）本题答案：【】7、【单选题】快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____输入：数组，起始位置，终止位置输出：划分位置whiledowhileanddoendifthenendwhileanddoendifthenendendreturn本题答案：【】8、【单选题】下面给出了计算Fibonacci数列第项的伪代码，该算法的时间复杂度为____（请选择最准确的答案）输入：数字输出：Fibonacci数列的第项iforthenreturnelsereturnend本题答案：【】9、【单选题】随机化次序选择算法的最坏情况时间复杂度为____（请选择最准确的答案）本题答案：【】10、【单选题】随机化次序选择算法的期望时间复杂度为____（请选择最准确的答案）本题答案：【】第4章单元测验1、【单选题】在0-1背包问题中，若背包容量为20,5个物品的体积分别为，价格分别为。则该背包能容纳物品的最大总价格为____本题答案：【25】2、【单选题】在商品个数为、背包容量为的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为____本题答案：【】3、【单选题】0-1背包问题中的递推式为____本题答案：【】4、【单选题】下面给出了0-1背包问题的动态规划算法伪代码，其中空白处应分别填入____输入：商品数量,各商品价值，各商品体积，背包容量输出：商品价格的最大值，最优解方案创建二维数组fordoendfordoendfordofordoifthenendelseendendendfordoifthenprint选择商品endelseprint不选择商品endendreturn,本题答案：【】5、【单选题】设计动态规划算法的一般步骤为____本题答案：【问题结构分析→递推关系建立→自底向上计算→最优方案追踪】6、【单选题】最大子数组问题的分治算法和动态规划算法的时间复杂度分别为____（请选择最准确的答案）本题答案：【】7、【单选题】在最大子数组问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入____输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和//初始化本题答案：【】8、【单选题】在最大子数组问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入___输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化//动态规划fordoifthenendelseendend本题答案：【】9、【单选题】在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入___输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化计算数组和数组//查找解fordoifthenendendreturn本题答案：【】10、【单选题】对于包含个正数元素的数组，我们希望找出数组中的一些元素，使得这些元素在数组中互不相邻并且元素之和最大。例如在数组中，应当选择和，元素之和为。给出该问题的解决算法如下，空白处应填入____输入：正数数组，元素个数输出：选择的元素，最大不相邻元素之和创建数组，表示数组中的最大不相邻元素之和创建数组记录选择方案ifthenendelseendfordoifthenendelseendendreturn本题答案：【】第5章单元测验1、【单选题】给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____本题答案：【gorthmthm】2、【单选题】在最长公共子序列问题中，我们用表示序列和序列的最长公共子序列长度，则递推式应为____本题答案：【】3、【单选题】给出最长公共子序列问题的部分伪代码如下，其中空白处应分别填入____输入：两个序列输出：的最长公共子序列分别代表的序列长度//初始化新建二维数组fordoendfordoendfordofordoifthenendelseifthenendelseendendend本题答案：【】4、【单选题】在最长公共子串问题的递推式中，表示____本题答案：【和中以和结尾的最长公共子串的长度】5、【单选题】最长公共子串问题的递推式为本题答案：【】6、【单选题】给定两个字符串,需要判断中有多少个子序列与相等。例如：则和两个子序列都与相等。思考该问题，可以用表示的子序列中与相等的个数，如上例。则对应的递推式为___本题答案：【】7、【单选题】在支持插入、删除、替换三种操作的最小编辑距离问题中，我们用表示字符串变为的最小编辑距离，则递推式应为本题答案：【】8、【单选题】在支持插入、删除、替换三种操作的最小编辑距离问题中，用数组来记录编辑方案。则数组中的L,U,LU分别代表哪种操作___本题答案：【插入删除替换/空操作】9、【单选题】字符串“algorithm”到字符串“altruistic”的最小编辑距离为___本题答案：【6】10、【单选题】下面给出了最长公共子序列问题中输出最长公共子序列的函数Print-LCS()伪代码，其中空白处应分别填入____输入：追踪数组，序列，当前位置和输出：的最长公共子序列ifthenreturnendifthenPrint-LCS(,,,)printelseifthenPrint-LCS(,,,)endelsePrint-LCS(,,,)end本题答案：【】第6章单元测验1、【单选题】在钢条切割问题中，若钢条长度为，且长度从到的钢条价格分别为。则切割后钢条的最大总收益为____本题答案：【】2、【单选题】在矩阵链乘法问题中，矩阵链中矩阵的规模分别为。则该矩阵链所需标量乘法的最小次数为____次本题答案：【】3、【单选题】在钢条切割问题中，表示切割长度为的钢条可得最大总收益，表示长度为的钢条的价格，则递推式为____本题答案：【】4、【单选题】下面给出了钢条切割问题的动态规划算法的部分伪代码，其中空白处应分别填入____输入：钢条价格表，钢条长度输出：最大收益，钢条切割方案//初始化创建一维数组fordofordoifthenendendend输出最优方案return本题答案：【】5、【单选题】下面给出了钢条切割问题的动态规划算法中追踪最优方案部分的伪代码，其中空白处应分别填入____//输出最优方案whiledoprintend本题答案：【】6、【单选题】在矩阵链乘法问题中，表示计算矩阵链所需标量乘法的最小次数，则该问题的递推式为____本题答案：【】7、【单选题】在矩阵链乘法问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入___输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和//初始化forthenend本题答案：【】8、【单选题】在矩阵链乘法问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和初始化//动态规划fordofordofordoifthenendendendendreturn本题答案：【】9、【单选题】在矩阵链乘法问题的动态规划算法中，给出追踪最优方案部分的伪代码如下，空白处应填入____Print-Matrix-Chain()输入：矩阵链,追踪数组,位置索引和输出：矩阵链加括号方式ifthenprintreturnendprint“(”Print-Matrix-Chain(,,,)print“)(”Print-Matrix-Chain(,,,)print“)”return本题答案：【】10、【单选题】对某仅包含左右括号的字符串而言，若其中左括号和右括号可以正确的匹配，那么称其为均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。给定一个长度为n的仅包含左右括号的字符串S，请求出字符串S的最长均衡子序列。换言之，请从S中挑选出尽量多的字符按顺序组成新字符串S'，使得S'是一个均衡字符串。例如，对字符串“())(()”而言，我们可以挑选其中第1，2，5，6个字符构成一个长度为的均衡字符串“()()”。我们用表示字符串的最长均衡子序列长度，则其递推式应为____本题答案：【】第7章单元测验1、【单选题】在部分背包问题中，若背包容量为，有个物品可供选择。每个物品价格分别为，体积分别为。则该背包可容纳物品最大总价格为____本题答案：【】2、【单选题】下面给出了部分背包问题的贪心算法的伪代码，其中空白处应分别填入输入：商品数量,各商品的价值,各商品的体积，背包容量输出：商品价格的最大值计算商品性价比并按降序排序//分别表示性价比第大的商品的性价比、价格和体积//根据贪心策略求解whiledoifthen选择商品endelse选择体积的商品endendreturn本题答案：【】3、【单选题】给出共5个字符，其出现频数(千次)分别为。按照课程中所讲左0右1，左小右大的规则建树编码，则字符串的霍夫曼编码应为____本题答案：【】4、【单选题】下面给出了霍夫曼编码问题的算法的伪代码，其中空白处应分别填入___输入：各字符频数，字符数输出：霍夫曼编码树//预处理将递增排序新建结点数组fordoendfordo新建结点endreturn本题答案：【】5、【单选题】在活动选择问题中，给出6个活动其时间分别为,则最多能安排活动数为____本题答案：【】6、【单选题】下面给出了活动选择问题的算法的伪代码，其中空白处应分别填入____输入：活动集合,每个活动的起止时间输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动fordoifthenendendreturn本题答案：【】7、【单选题】在加权活动选择问题中，给出个活动其时间分别为,权重分别为,则安排权重最大和为___本题答案：【】8、【单选题】在加权活动选择问题中有个活动组成的集合，令表示集合中不冲突活动最大权重和，为以活动开始前最后结束的活动，为活动的权重。则递推式为____本题答案：【】9、【单选题】给出加权活动选择问题部分伪代码如下，空白处应填入___输入：活动集合,每个活动的起止时间，权重输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动fordo二分查找求解end新建数组//动态规划fordoifthenendelseendendreturn本题答案：【】10、【单选题】给出加权活动选择问题输出方案部分伪代码如下，空白处应填入____//输出方案whiledoifthenprint选择endelseendend本题答案：【】第8章单元测验1、【单选题】对图深度优先搜索（DFS）遍历该图的时间复杂度为____（请选择最准确项）本题答案：【】2、【单选题】图的生成子图应包含个顶点，至少条边本题答案：【】3、【单选题】无向图的一个连通分量包含个顶点，则该连通分量应至少包含____条边本题答案：【】4、【单选题】已知无向图是包含棵树的森林，且该图顶点数与边数相加之和为即。则该森林顶点数为____本题答案：【42】5、【单选题】已知图深度优先搜索（DFS）的搜索树为一棵满二叉树如下图所示，树中有个点的发现时刻和结束时刻相差。则根节点的发现时刻和结束时刻相差____本题答案：【13】6、【单选题】无向图包含7个顶点，10条边，其邻接表和结构如下图所示。以顶点作为起点执行深度优先搜索（DFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到如下图所示搜索树。其中顶点1、2、3处应分别填入____本题答案：【】7、【多选题】在上题中，均不在搜索树中的边有哪些____（多选）本题答案：【#】8、【多选题】在扇形图(FanGraph)中，其邻接表和结构如下第一张图所示。从顶点开始进行广度优先搜索（BFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到搜索树如下第二张图，该搜索树并未画全，应从虚线中选择____补全。（多选）本题答案：【①#②】9、【多选题】同上题，在扇形图(FanGraph)中，其邻接表和结构如下图所示。从顶点开始进行广度优先搜索（BFS），搜索时按照邻接表顺序遍历某一节点的相邻节点得到搜索树如下，该搜索树并未画全，应从虚线中选择____补全。（多选）本题答案：【①#③】10、【多选题】同上题，在扇形图(FanGraph)中，其邻接表和结构如下第一张图所示。从顶点开始进行深度优先搜索（DFS），搜索时按照邻接表顺序遍历某一节点的相邻节点。得到搜索树如下第二张图所示，该搜索树并未画全，应从虚线中选择____补全。（多选）本题答案：【①#②#④】第9章单元测试1、【单选题】有向图上包含个顶点的强连通分量应至少包含____条边。本题答案：【】2、【单选题】已知有向图有个顶点，且所有顶点入度之和与所有顶点出度之和相加为，则该图有____条边本题答案：【】3、【单选题】下面有向图中存在强连通分量，可以将每个强连通分量看作一个点，得到新的图。则中存在个点本题答案：【】4、【单选题】下面给出了使用深度优先搜索(DFS)求强连通分量的部分伪代码，其中空白处应分别填入____本题答案：【】5、【单选题】给出判断有向图中是否存在环的算法伪代码如下，空白处应填入____本题答案：【】6、【单选题】给出深度优先搜索（DFS）进行拓扑排序的算法如下，则空白处应填入____本题答案：【向结尾追加向结尾追加】7、【单选题】图上的哈密顿路径（Hamiltonianpath）是指将所有顶点恰好包含一次的路径，如下左图所示。但并非所有图中都存在哈密顿路径，如下右图所示。现在希望设计一个算法，判断有向无环图（DAG）上是否存在哈密顿路径。给出算法的伪代码如下，空白处应填入____（提示：请思考拓扑序和哈密顿路径的关系）本题答案：【】8、【单选题】上题中判断有向无环图（DAG）是否存在哈密顿路径的算法的时间复杂度是____（请选择最准确项）本题答案：【】9、【多选题】对如下所示有向图，从点开始进行深度优先搜索（DFS），搜索时按照字典序遍历某一节点的相邻节点。在得到的深度优先搜索树中，包含如下哪些类别的边（多选）本题答案：【树边#前向边#后向边#横向边】10、【多选题】对如下所示有向图进行拓扑排序，得到一个拓扑序如下图中所示。其中空白处可以依次填入三个字母。（多选）本题答案：【#】第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、【单选题】对带权的连通无向图，将所有点划分为个树，且个树的总边权之和最小,若无法划分为棵树则输出“NoAnswer”。如下图所示，若，则应按照图中颜色区分划分为棵树，边权之和为。利用Kruskal算法解决该问题的伪代码如下，则空白处应填入____。本题答案：【】第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章单元测试1、【单选题】对如下所示二分图，其最大匹配数为本题答案：【】2、【单选题】给定无向图，如何判断该图是否为二分图？可以用两种颜色给图上顶点染色，若任意相邻顶点颜色均不相同，则该无向图是二分图。给出判断无向图是否为二分图的算法伪代码如下，空白处应填入。本题答案：【】3、【单选题】求二分图最大匹配问题的匈牙利算法伪代码如下，则空白处应填入____本题答案：【】4、【单选题】二分图最大匹配问题的匈牙利算法的时间复杂度是____（请选择最准确项）本题答案：【】5、【单选题】给出一个矩阵，行数与列数均为,其中每个元素都是0或1。现在有两种操作分别是交换任意两行或交换任意两列。请判断是否可以通过任意次以上两种操作使得矩阵主对角线（左上角到右下角）全部为1。观察符合条件的矩阵，可以发现在此类矩阵中，总能从每一行都挑选一个为1的元素，且这些元素都分布在不同列。可将该问题转换为二分图的匹配问题，给出算法伪代码如下，则空白处应填入____本题答案：【】6、【单选题】给出流网络有向图如下所示，则该流网络的最小割为，该最小割的横跨边是。本题答案：【】7、【单选题】给出流网络有向图如下所示，将其转换为残存图，则边上空白处①②③④的值分别应为，该流网络上继续寻找增广路径，下一条增广路径最多可增加流量。本题答案：【】8、【单选题】求最大流问题的Ford-Fulkerson算法伪代码如下，则空白处应填入____本题答案：【】9、【单选题】最大流问题的Ford-Fulkerson算法的时间复杂度是____（请选择最准确项）本题答案：【】10、【单选题】现有题库包含k种类型题目共n道，按要求从其中抽取m道题目组成试卷。已知题库表示第道题目覆盖类型。组卷要求表示卷子中第种类型题目应有道。求符合要求的组卷方案，若不存在解则输出“NoSolution”。该问题可转化为最大流问题解决，将题目与题目类型分别抽象为两列点，左侧与右侧添加一源点和汇点，源点与题目连边，边权为1；题目与该题覆盖类型连边，边权为1；类型与汇点连边，边权为该类型题目所需数量。如下图实例所示。给出算法伪代码如下，空白处应填入本题答案：【】期末考试1、【单选题】的解为____本题答案：【】2、【单选题】归并排序算法中的合并操作是将2段有序序列通过不断比较两序列首元素大小，合并为1段有序序列。k路归并排序与合并操作相似，给定k个有序序列，总长度为n（）。用优先队列来维护k个有序序列的首元素，每次从优先队列中取出列首元素加入整体有序序列。从而将k个有序序列合并为1个长度为n的有序序列。那么k路归并排序算法的时间复杂度为本题答案：【】3、【单选题】给定n天的某支股票价格，假定第i天的价格为，为了尽可能多的赚钱，即寻找且以在第i天买进股票，在第j天卖出股票，使得最大化。给出该问题的分治部分算法伪代码如下，则空白处应填入本题答案：【、、，三种方案中使收益最大的方案】4、【单选题】将一个凸多边形划分为多个三角形，且划分线不交叉，有多少种划分方法？三角形有1种划分方法，四边形有2种划分方法…该问题是典型的卡特兰数应用问题，已知卡特兰数有如下递推关系：给出计算的伪代码如下，则该算法时间复杂度为(请选择最准确项)本题答案：【】5、【单选题】随机化次序选择算法的期望时间复杂度为____本题答案：【】6、【单选题】动态规划算法中，最优子结构的性质是指本题答案：【问题的最优解可以由子问题的最优解组合而成，子问题可以独立求解】7、【单选题】在支持插入、删除、替换三种操作的最小编辑距离问题中，字符串“algorithm”到字符串“altruistic”的最小编辑距离为____本题答案：【6】8、【单选题】在支持插入、删除、替换三种操作的最小编辑距离问题中，我们用表示字符串变为的最小编辑距离，则递推式应为____本题答案：【】9、【单选题】在矩阵链乘法问题中，表示计算矩阵链所需标量乘法的最小次数，则该问题的递推式为____本题答案：【】10、【单选题】有一串特殊的能量项链，上面有N颗能量珠。每颗能量珠上都有两个正整数作为头标记和尾标记。对于相邻的两颗珠子，保证前一颗珠子的尾标记一定等于后一颗珠子的头标记。两颗珠子可以聚合成一颗珠子，同时释放出能量。如果前一颗能量珠的头标记为a，尾标记为b，后一颗能量珠的头标记为b，尾标记为c，则聚合后释放的能量为，新产生的珠子的头标记为a，尾标记为c。现在我们要通过不断聚合相邻珠子直到项链上只剩1颗珠子来获取能量。显然，不同的聚合顺序能获得不同的能量。请你设计聚合顺序使得释放总能量最大。例如：N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。应先将第1颗和第4颗合并，然后再依次和第2颗、第3颗合并。可得到总能量为。则下面给出的伪代码中空白处应填入本题答案：【】11、【单选题】对某仅包含左右括号的字符串而言，若其中左括号和右括号可以正确的匹配，那么称其为均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。给定一个长度为n的仅包含左右括号的字符串S，请求出字符串S的最长均衡子序列。换言之，请从S中挑选出尽量多的字符按顺序组成新字符串S'，使得S'是一个均衡字符串。例如，对字符串“())(()”而言，我们可以挑选其中第1，2，5，6个字符构成一个长度为4的均衡字符串“()()”。我们用表示字符串的最长均衡子序列长度，则其递推式应为____本题答案：【】12、【单选题】在部分背包问题中，若背包容量为，有个物品可供选择。每个物品价格分别为，体积分别为。则该背包可容纳物品最大总价格为____本题答案：【42】13、【单选题】在加权活动选择问题中有n个活动组成的集合，令表示集合中不冲突活动最大权重和，为以活动开始前最后结束的活动，为活动的权重。则递推式为____本题答案：【】14、【单选题】老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。假设每个题目均需要花费一天的时间来完成，这期间无法完成其他题目。请你设计算法指定题目的完成计划，从而使总的得分最大。下面给出一个包含了7个题目及相应的分数、截止日期的实例：题目