MOOC 算法设计与分析-北京航空航天大学 中国大学慕课答案.docx
《MOOC 算法设计与分析-北京航空航天大学 中国大学慕课答案.docx》由会员分享,可在线阅读,更多相关《MOOC 算法设计与分析-北京航空航天大学 中国大学慕课答案.docx(86页珍藏版)》请在文库网上搜索。
1、 MOOC 算法设计与分析-北京航空航天大学 中国大学慕课答案第 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、问题:函数选项:用 记号可表示为_A、B、C、D、正确答案:【7、问题:下述伪代码希望求出数组应填入_输入:数组中数字 出现的次数,则伪代码空白处,数字 输出: 在数组 中出现的次
2、数then _ endendreturnfor选项:to ifA、B、C、D、正确答案:【】 8、问题:函数选项:用 记号可表示为_A、B、C、D、正确答案:【#】9、问题:函数选项:用 记号可表示为_A、B、C、D、正确答案:【#】10、问题:函数选项:用 记号可表示为_A、B、C、D、正确答案:【#】第 2 章单元测验1、问题:在归并排序算法中,若每次分解将长度为 n 的数组分为两段,长度分别为 n-1 和 1,此时归并排序算法的时间复杂度为_选项:A、B、 C、D、正确答案:【】2、问题:在归并排序算法中,若每次分解将长度为 n 的数组分为四段长度为 n/4的子数组进行递归,此时归并排序
3、算法的时间复杂度为_选项:A、B、C、D、正确答案:【】3、问题:归并排序的最好情况时间复杂度为_选项: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、问题:选项:的解为_A、B、C、D、正确答案:【】9、问题:在最大子数组问题的优化枚举算法中,每次计算子数组 Xi.j 之和的时间复杂度为_选项: A、B、C、D、正确答案:【】10、问题:在最大子数组问题的分治算法中,若可以用 O(1)的时间
4、求得跨越中点的最大子数组,则该算法的时间复杂度为选项:A、B、C、D、正确答案:【】第 3 章单元测验1、问题:数组选项:中的逆序对个数为_A、4B、5C、6D、7正确答案:【5】2、问题:长度为 的数组中逆序对个数最多为_选项:A、B、C、D、正确答案:【】 3、问题:快速排序算法的最坏情况时间复杂度为_选项:A、B、C、D、正确答案:【】4、问题:在快速排序算法中,假定存在一个神奇的黑盒可以在 O(1)的时间内给出最好的主元(也就是中位数),那么使用此神奇黑盒的快速排序算法最差运行时间为_(请选择最准确的答案)选项:A、B、C、D、正确答案:【】5、问题:随机化快速排序算法的最坏情况时间复
5、杂度为_(请选择最准确的答案)选项:A、B、C、D、正确答案:【】6、问题:随机化快速排序算法的期望时间复杂度为_(请选择最准确的答案)选项:A、B、C、 D、正确答案:【】7、问题:快速排序算法的关键为数组的划分,下面给出了一种划分数组的方法,其中空白处应填入_输入:数组 ,起始位置 ,终止位置 输出:划分位置whileendwhilereturndowhileanddoendifthenanddoendifthenendend选项:A、B、C、D、正确答案:【】8、问题:下面给出了计算 Fibonacci 数列第 项的伪代码,该算法的时间复杂度为_(请选择最准确的答案)or then re
6、turn else return选项:输入:数字 输出:Fibonacci 数列的第 项 ifendA、B、C、D、正确答案:【】9、问题:随机化次序选择算法的最坏情况时间复杂度为_(请选择最准确的答案)选项:A、B、C、D、正确答案:【】 10、问题:随机化次序选择算法的期望时间复杂度为_(请选择最准确的答案)选项:A、B、C、D、正确答案:【】第 4 章单元测验1、问题:在 0-1 背包问题中,若背包容量为 20,5 个物品的体积分别为,价格分别为。则该背包能容纳物品的最大总价格为_选项:A、22B、23C、25D、26正确答案:【25】2、问题:在商品个数为 、背包容量为 的 0-1 背
7、包问题中,蛮力枚举算法和动态规划算法的时间复杂度分别为_选项:A、B、C、D、正确答案:【】3、问题:0-1 背包问题中的递推式为_选项:A、B、C、 D、正确答案:【】4、问题:下面给出了 0-1 背包问题的动态规划算法伪代码,其中空白处应分别填入_输入:商品数量 ,各商品价值 ,各商品体积 ,背包容量 输出:商品价格的最大值,最优解方案创建二维数组fordoendfordo endforthendofor do ifend elsethen print 选择商品endendendfor do ifendelse print 不选择商品 endendreturn选项:,A、B、C、D、正确答
8、案:【】5、问题:设计动态规划算法的一般步骤为_选项:A、递推关系建立问题结构分析自上向下计算最优方案追踪B、递推关系建立问题结构分析自底向上计算最优方案追踪C、问题结构分析递推关系建立自上向下计算最优方案追踪D、问题结构分析递推关系建立自底向上计算最优方案追踪正确答案:【问题结构分析递推关系建立自底向上计算最优方案追踪】6、问题:最大子数组问题的分治算法和动态规划算法的时间复杂度分别为_ (请选择最准确的答案)选项:A、B、C、D、正确答案:【】 7、问题:在最大子数组问题的动态规划算法中,给出初始化部分的伪代码如下,空白处应填入_输入:数组 ,数组长度 输出:最大子数组和 ,子数组起止位置
9、 新建一维数组选项:和/初始化A、B、C、D、正确答案:【】8、问题:在最大子数组问题的动态规划算法中,给出计算部分的伪代码如下,空白处应填入_ _输入:数组 ,数组长度 输出:最大子数组和 ,子数组起止位置 新建一维数组和对初始化/动态规划 for do ifthenend elseendend选项:A、B、C、D、正确答案:【】9、问题:在最大子数组问题的动态规划算法中,给出查找解部分的伪代码如下,空白处应填入_ _ 输入:数组 ,数组长度 输出:最大子数组和 ,子数组起止位置 新建一维数组 初始化 计算 数组和对和数组 /查找解fordo ifthenend end return选项:A
10、、B、C、D、正确答案:【】 10、问题:对于包含一些元素,使得这些元素在数组中互不相邻并且元素之和最大。例如在数组个正数元素的数组,我们希望找出数组中的中,应当选择 和 ,元素之和为 。给出该问题的解决算法如下,空白处应填入_输入:正数数组 ,元素个数 输出:选择的元素,最大不相邻元素之和创建数组,表示数组中的最大不相邻元素之和创建数组记录选择方案thenifendelseendfordoif thenendelseendendreturn选项:A、B、C、D、正确答案:【】第 5 章单元测验1、问题:给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长
11、公共子序列和最长公共子串的选项是_选项:A、gorthm thmB、thm gorthmC、glorhthm orthmD、orthm glorhthm正确答案:【gorthm thm】2、问题:在最长公共子序列问题中,我们用的最长公共子序列长度,则递推式应为_选项:表示序列和序列A、B、 C、D、正确答案:【】3、问题:给出最长公共子序列问题的部分伪代码如下,其中空白处应分别填入_输入:两个序列 输出: 的最长公共子序列 分别代表 的序列长度/初始化新建二维数组endforfordoforendelsedodo endfordoifthen endelse if thenendendend选
12、项:A、B、C、D、正确答案:【】4、问题:在最长公共子串问题的递推式中,选项:表示_A、B、C、D、和和和和是否相等中以 或 结尾的最长公共子串中的最长公共子串 的长度中以 和 结尾的最长公共子串中以 和 结尾的最长公共子串的长度的长度正确答案:【和的长度】 5、问题:最长公共子串问题的递推式为选项:A、B、C、D、正确答案:【】6、问题:给定两个字符串,需要判断 中有多少个子序列与 相等。例如:则和两个子序列都与 相等。思考该问题相等的个数,如上例,可以用选项:表示的子序列中与。则对应的递推式为_A、B、C、D、正确答案:【】 7、问题:在支持插入、删除、替换三种操作的最小编辑距离问题中,
13、我们用表示字符串 变为 的最小编辑距离,则递推式应为选项:A、B、C、D、正确答案:【】8、问题:在支持插入、删除、替换三种操作的最小编辑距离问题中,用数组来记录编辑方案。则选项:数组中的 L,U,LU 分别代表哪种操作_A、删除 插入 替换/空操作B、插入 替换/空操作 删除C、插入 删除 替换/空操作 D、替换/空操作 删除 插入正确答案:【插入 删除 替换/空操作】9、问题:字符串“algorithm”到字符串“altruistic”的最小编辑距离为_选项:A、8B、7C、6D、5正确答案:【6】10、问题:下面给出了最长公共子序列问题中输出最长公共子序列的函数 Print-LCS(,当
14、前位置 和 输出:thenPrint-LCS(, )endelsePrint-LCS()伪代码,其中空白处应分别填入_输入:追踪数组的最长公共子序列 if thenreturn, , , )print else if,序列endifthenPrint-LCS(, , , ,)end选项:A、B、C、D、正确答案:【】第 6 章单元测验1、问题:在钢条切割问题中,若钢条长度为 ,且长度从 到 的钢条价格分别为。则切割后钢条的最大总收益为_选项:A、B、C、D、正确答案:【】2、问题:在矩阵链乘法问题中,矩阵链中矩阵的规模分别为。则该矩阵链所需标量乘法的最小次数为_次选项: A、B、C、D、正确答
15、案:【】3、问题:在钢条切割问题中,表示切割长度为 的钢条可得最大总收益,表示长度为 的钢条的价格,则递推式为_选项:A、B、C、D、正确答案:【】4、问题:下面给出了钢条切割问题的动态规划算法的部分伪代码,其中空白处应分别填入_输入:钢条价格表割方案/初始化创建一维数组for doif,钢条长度 输出:最大收益,钢条切fordothenendendend 输出最优方案 return选项:A、B、C、D、正确答案:【】5、问题:下面给出了钢条切割问题的动态规划算法中追踪最优方案部分的伪代码,其中空白处应分别填入_/输出最优方案 while doprint选项:endA、 B、C、D、正确答案:
16、【】6、问题:在矩阵链乘法问题中,次数,则该问题的递推式为_选项:表示计算矩阵链所需标量乘法的最小A、B、C、D、正确答案:【】7、问题:在矩阵链乘法问题的动态规划算法中,给出初始化部分的伪代码如下,空白处应填入_输入:矩阵维度数组 ,矩阵个数 输出:最小标量乘法次数,分割方式追踪数组新建二维数组then和/初始化forend选项:A、B、C、D、正确答案:【】8、问题:在矩阵链乘法问题的动态规划算法中,给出计算部分的伪代码如下,空白处应填入 输入:矩阵维度数组 ,矩阵个数 输出:最小标量乘法次数,分割方式追踪数组新建二维数组doendendendendreturn和初始化/动态规划 fori
17、f thendoforfordo选项:A、 B、C、D、正确答案:【】9、问题:在矩阵链乘法问题的动态规划算法中,给出追踪最优方案部分的伪代码如下,空白处应填入_Print-Matrix-Chain( )输入:矩阵链 ,追踪数,位置索引 和 输出:矩阵链加括号方式 if thenprint returnendprint, , )print “)(”Print-Matrix-Chain( , , , )print “)”return组“(”Print-Matrix-Chain( ,选项:A、B、C、D、正确答案:【】10、问题:对某仅包含左右括号的字符串而言,若其中左括号和右括号可以正确的匹配,
18、那么称其为均衡字符串。例如,字符串“()”和“()()”都是均衡字符串,但是“()()”不是均衡字符串。给定一个长度为 n 的仅包含左右括号的字符串 S,请求出字符串 S 的最长均衡子序列。换言之,请从 S 中挑选出尽量多的字符按顺序组成新字符串 S,使得 S是一个均衡字符串。例如,对字符串“()()”而言,我们可以挑选其中第 1,2,5,6 个字符构成一个长度为 的均衡字符串“()()”。我们用表示字符串选项:A、的最长均衡子序列长度,则其递推式应为_B、C、 D、正确答案:【】第 7 章单元测验1、问题:在部分背包问题中,若背包容量为 ,有 个物品可供选择。每个物品价格分别为价格为_ _选
19、项:A、,体积分别为。则该背包可容纳物品最大总B、C、D、正确答案:【】2、问题:下面给出了部分背包问题的贪心算法的伪代码,其中空白处应分别填入输入:商品数量 ,各商品的价值 ,各商品的体积 ,背包容量 输出:商品价格的最大值计算商品性价比比第 大的商品的性价比、价格和体积doif then 选择商品并按降序排序/分别表示性价/根据贪心策略求解 whileendelse 选择 体积的商品选项:endendreturnA、B、C、D、正确答案:【】 3、问题:给出共 5 个字符,其出现频数(千次)分别为。按的霍夫曼编码照课程中所讲左 0 右 1,左小右大的规则建树编码,则字符串应为_选项:A、B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- MOOC MOOC答案 中国大学慕课答案