MOOC 算法设计与分析-青岛大学 中国大学慕课答案.docx
《MOOC 算法设计与分析-青岛大学 中国大学慕课答案.docx》由会员分享,可在线阅读,更多相关《MOOC 算法设计与分析-青岛大学 中国大学慕课答案.docx(36页珍藏版)》请在文库网上搜索。
1、 MOOC 算法设计与分析-青岛大学 中国大学慕课答案第一章 单元测试1、问题:下面列出了算法的四个性质,哪个性质是程序不一定具备的?选项:A、有输入B、有输出C、确定性D、有穷性正确答案:【有穷性】2、问题:在算法设计与分析过程中,有算法设计,算法的正确性证明,算法的复杂性分析,程序设计等几个重要步骤,下面哪种顺序是正确的?选项:A、算法的正确性证明-算法设计-算法的复杂性分析-程序设计B、算法的正确性证明-算法的复杂性分析-算法设计-程序设计C、算法设计-算法的正确性证明-算法的复杂性分析-程序设计D、算法设计-算法的复杂性分析-算法的正确性证明-程序设计正确答案:【算法设计-算法的正确性
2、证明-算法的复杂性分析-程序设计】3、问题:下面哪些内容不是算法设计之前要完成的内容?选项:A、是求精确解还是近似解B、确定合适的数据结构C、确定合适的算法策略D、使用何种计算机语言设计程序正确答案:【使用何种计算机语言设计程序】4、问题:下面是快速幂算法求 的代码,这里 n0, a 是实数。对该算法的时间复杂性描述不准确的是哪个?doule exp2(double a, int n)int i;double b, s=1.0;i=n;b=a;while(i0)if(i%2) s*=b;i/=2; b*=b;return s;选项:A、B、C、D、正确答案:【】 5、问题:下面哪个算法在最坏情
3、况下的时间复杂性最低选项:A、归并排序B、插入排序C、快速排序D、冒泡排序正确答案:【归并排序】6、问题:有时间复杂性选项:,时间复杂性从低到高的顺序是?A、B、C、D、正确答案:【】7、问题:有一个算法, 它的时间复杂性 T(n)的递归定义如下, 问 T(n)是?选项:A、B、C、D、正确答案:【】8、问题:有一个算法, 它的时间复杂性 T(n)的递归定义如下, 问 T(n)是?选项:A、B、C、 D、正确答案:【】9、问题:有一个算法, 它的时间复杂性 T(n)的递归定义如下, 问 T(n)是?选项:A、B、C、D、正确答案:【】10、问题:有一个算法, 它的时间复杂性 T(n)的递归定义
4、如下, 问 T(n)是?选项:A、B、C、D、正确答案:【】11、问题:A 公司处理器速度是 B 公司的 100 倍。对于复杂性为 O( )的算法,B公司的计算机可以在 1 小时内处理规模为 n 的问题,A 公司的计算机在 1 小时内能处理的问题规模是多少?选项:A、nB、10nC、100nD、正确答案:【10n】 12、问题:关于算法的正确性,下面哪些说法是正确的?选项:A、若算法是正确的, 则算法一定能结束(运行时间是有限的)B、若算法是正确的,则对于问题的任何实例,算法都能得到正确的结果。C、对于问题的一个实例,如果算法能够获得正确的结果,就证明算法是正确的。D、对于问题的一个实例, 如
5、果算法不能获得正确的结果, 就证明算法是不正确的。正确答案:【若算法是正确的, 则算法一定能结束(运行时间是有限的)#若算法是正确的,则对于问题的任何实例,算法都能得到正确的结果。#对于问题的一个实例, 如果算法不能获得正确的结果, 就证明算法是不正确的。】13、问题:解决同一个问题的算法策略可能有多个,使用不同算法策略设计的算法,其算法时间复杂性可能有显著差异。选项:A、正确B、错误正确答案:【正确】14、问题:学习主定理和递归树等求解递归方程方法,主要目的是解决求递归算法的时间复杂性问题选项:A、正确B、错误正确答案:【正确】15、问题:自然语言、伪代码都可以描述算法,而流程图不能描述算法
6、选项:A、正确B、错误正确答案:【错误】第二章 单元测试1、问题:分治法解决问题分为三步走,即分、治、合。下面列出了几种操作, 请按分、治、合顺序选择正确的表述。(1)将各个子问题的解合并为原问题的解,(2)将问题分解为各自独立的多个子问题,(3)将多个子问题合并为原问题。(4)求各个子问题的解,(5)将问题分解为可重复的多个子问题。选项:A、(5)(4)(1)B、(2)(4)(1)C、(2)(1)(3) D、(5)(1)(3)正确答案:【(2)(4)(1)】2、问题:分治法的时间复杂性分析,通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程, 然后解此方程可得 T(n)的结果。T(n
7、)的递归定义如下:关于该定义中 k,n/m, f(n)的解释准确的是选项:A、k 是常系数;n/m 是规模为 n 的问题分为 m 个子问题;f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和。B、k 是子问题个数,n/m 是子问题的规模,f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和C、k 是子问题个数,n/m 是子问题的规模,f(n)是规模为 n 的问题分解为子问题的时间复杂性D、k 是常系数,n/m 是规模为 n 的问题分为 m 个子问题,f(n)是将子问题的解合并为问题的解的时间复杂性。正确答案:【k 是子问题个数,n/m 是子问题的规模,f(n)是分
8、解为子问题的时间复杂性与合并子问题的解的时间复杂性之和】3、问题:已知斐波那契数列中第 n 个斐波那契数 F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第 n 个斐波那契数,从下面选项中选取答案。选项:A、能,因为它满足分治法的四个适应条件B、能,因为它可以用分、治、合三个步骤完成计算C、不能,因为它不满足分治法的第四个适应条件(子问题是相互独立的,也就是没有重复子问题)D、不能,因为它不可以用分、治、合三个步骤完成计算正确答案:【不能,因为它不满足分治法的第四个适应条件(子问题是相互独立的,也就是没有重复子问题)】4、问题:快速幂算法求 ,其时间复杂性为 O(logn),a 是
9、实数,n 为非负整数。下面是一同学用 c 语言编写的求 的代码 double exp2(double a,int n) if(a=0)return 0; if (n=0) return 1; else if(n%2) return a* exp2(a,n/2)* exp2(a,n/2); else returnexp2(a,n/2)* exp2(a,n/2); 对该同学的算法评价正确的是?选项:A、运行结果正确,时间复杂性为 O(logn)B、运行结果错误,时间复杂性为 O(n)C、运行结果正确,时间复杂性为 O(n)D、运行结果错误,时间复杂性为 O(logn)正确答案:【运行结果正确,时间
10、复杂性为 O(n)】 5、问题:快速排序和归并排序是常用的排序算法,也都是采用分治法解决的问题。快速排序的时间复杂性为 O( ), 而归并排序的时间复杂性为 O(nlogn), 究其原因,下面的解释你认为哪个正确?选项:A、这是因为归并排序把问题划分为子问题时的时间复杂性是 O(1),而快速排序划分为子问题是使用 partition()函数,其时间复杂性是 O(n)。B、因为归并排序把问题划分为两个子问题时其规模大致相等,是原来规模的 n/2,而快速排序划分为子问题是使用 partition()函数,划分为子问题时不能保证二个子问题的规模大致相同,在极端状况下,每次都只划分为 1 个子问题,其
11、规模为原问题规模 n-1,因此快速排序在极端状况下的时间复杂性的递归定义为 T(n)=T(n-1)+O(n)C、归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和D、因为快速排序将问题划分为子问题的个数比归并排序要多正确答案:【因为归并排序把问题划分为两个子问题时其规模大致相等,是原来规模的 n/2,而快速排序划分为子问题是使用 partition()函数,划分为子问题时不能保证二个子问题的规模大致相同,在极端状况下,每次都只划分为 1 个子问题,其规模为原问题规模 n-1,因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)】6、问题:猜数游戏:
12、随机选择一个 0100 内的整数,让你猜。猜对了,你赢了,游戏结束。如果没有猜对,会告诉你猜大了,还是猜小了。当然,越早猜对越好。问最少需要猜多少次,就能保证一定能猜对?选项:A、6B、7C、51D、101正确答案:【7】7、问题:对于一个采用字符数组存放的长度为 n 的字符串 str,下面是用分治策略的递归算法去判断字符串 str 是否为回文,如是回文,函数返回 true,否则返回false。比如:“abcba”、“abba”是回文,“abc”则不是回文。bool isPal( char *str, intn) if ( n = 0 | 【 (1) 】) return true; if (
13、str0 != 【 (2) 】) return false; returnisPal( 【 (3) 】,【 (4) 】);算法中【】处缺少语句,请分析算法,从如下选项中选择语句补齐算法。选项:A、(1) n=1 (2) strn (3) str+1 (4) n-1B、(1) n=1 (2) strn-1 (3) str+1 (4) n-2C、(1) str0=strn-1 (2) strn-1 (3) str (4) n-1D、(1) str0=strn-1 (2) strn (3) str (4) n-2正确答案:【(1) n=1 (2) strn-1 (3) str+1 (4) n-2】
14、8、问题:对于一个采用字符数组存放的长度为 n 的字符串 str,下面是判断是否回文的不完整算法。比如:“abcba”、“abba”是回文,“abc”则不是回文 bool isPal( char*str, int n) if ( n = 0 | 【 (1) 】) return true; if ( str0 != 【 (2) 】) return false;return isPal( 【 (3) 】,【 (4) 】);请补齐代码后分析算法的时间复杂性,回答如下问题选项:A、该算法时间复杂性的递归定义为: T(n)=T(n-1)+1,ifn1;T(n)=O(1),if n1。T(n)=O(n),
15、 T(n)=(1)B、该算法时间复杂性的递归定义为: T(n)=T(n-1)+1,ifn1;T(n)=O(1),if n1。T(n)=O(n), T(n)=(n)C、该算法时间复杂性的递归定义为: T(n)=T(n-2)+1,ifn1;T(n)=O(1), if n1。T(n)=O(n), T(n)=(1)D、该算法时间复杂性的递归定义为: T(n)=T(n-2)+1,ifn1;T(n)=O(1), if n1。T(n)=O(n), T(n)=(n)正确答案:【该算法时间复杂性的递归定义为: T(n)=T(n-2)+1,ifn1;T(n)=O(1), ifn1。T(n)=O(n), T(n)=
16、(1)】9、问题:棋盘 nxn()的覆盖问题,其中一个点已经被覆盖,用 L 型模块将其余完全覆盖的分治算法。关于该算法时间复杂性描述不正确的是选项:A、 T(n)=4T(n/2)+O(1) , if n1; T(n)=O(1) ,if n=1 。B、T(k)=4T(k-1)+O(1) , if k0;T(k)=O(1) , if k=0。 这里 n=2kC、T(n)=O(n4)D、 T(k)=O(4k)正确答案:【T(n)=O(n4)】10、问题:棋盘 8X8 的覆盖问题,其中一个点已经被覆盖,用 L 型模块将其余完全覆盖的分治策略。约定解决四个子问题的顺序为右下,左下, 左上,右上。用数字标
17、识法填写覆盖方案(如 3 个相连的整数值 i 构成的 L 块,代表是第 i 个被放入棋盘中的 L 型块)。 使用分治策略的算法有三种形式 :1 使用递归算法实现, 2使用队列存取分解出的子棋盘的非递归算法 3.使用栈存取分解出的子棋盘的非递归算法。下图中有三个覆盖图案(只标出了前 7 块 L 型模块位置),问自左至右分别是哪种算法实现的覆盖方案? 选项:A、栈算法,队列算法,递归算法B、队列算法,栈算法,递归算法C、递归算法,队列算法, 栈算法D、递归算法, 栈算法, 队列算法正确答案:【递归算法,队列算法, 栈算法】11、问题:下面哪些不是递归算法的特点选项:A、结构清晰B、可读性强C、容易
18、用数学归纳法证明算法的正确性D、递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少正确答案:【递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少】12、问题:给定 n 个正整数组成的无序序列, 要找到该序列的中位数,解决该问题的最优算法的时间复杂性是?选项:A、O(logn)B、O(n)C、O(nlogn) D、正确答案:【O(n)】13、问题:将一个递归算法改造为非递归算法, 常用的数据结构是?选项:A、顺序表B、链表C、栈D、队列正确答案:【栈】14、问题:分治法解决问题时,平衡子问题思想是指:当问题划分出的子问题规模基本一致时,算法计算效率高选项:A、正确
19、B、错误正确答案:【正确】15、问题:递归程序代码简短,结构清晰,易读性强,相比解决同一问题的非递归程序,递归程序运行时间短。选项:A、正确B、错误正确答案:【错误】第三单元测试1、问题:求第 n 个斐波那契数的问题,根据动态规划的二要素分析,是可以用动态规划算法去解决的,下面是用备忘录方法(递归)解决的求第 n 个斐波那契数fn的程序.这里 N 是一个较大的正整数常量,注意备忘录方法的设计要点(也就是,对于一个问题, 首先判断是否该问题已被解决过,如果解决,不再重复。另外,解决过的问题,答案要记住)int fN=0,1,1;int fib(int n) if (【 1 】)returnfn;
20、elsereturn 【 2 】;代码中【1】 和【2】位置代码缺失, 请从下列选项中选出合适的语句补齐算法。选项:A、【1】n3 【2】 fib(n-1)+fib(n-2)B、【1】fn0 【2】 fib(n-1)+fib(n-2)C、 【1】fn0 【2】 fn=fib(n-1)+fib(n-2)D、【1】 n3 【2】 fn= fib(n-1)+fib(n-2)正确答案:【 【1】fn0 【2】 fn=fib(n-1)+fib(n-2)】 2、问题:动态规划解题的步骤分为四步(1)分析最优解的结构 (2)建立递归关系(3)计算最优值(4)构造最优解。关于这四个步骤的内容描述不正确的是哪个
21、?选项:A、分析最优解的结构:一个一般化问题可以分解为几个性质相同的子问题,并且问题的最优解可以通过子问题的最优解合并得到,也就是要满足最优子结构性质B、建立递归关系:建立关于问题最优值的递归定义,即问题的最优值通过子问题的最优值合并得到。C、计算最优值:以自顶往下的方法计算问题的最优值,也就是先求解规模较大的问题的最优值。D、构造最优解:根据计算最优值时得到的信息构造出问题的最优解,通常是用递归算法完成最优解的构造正确答案:【计算最优值:以自顶往下的方法计算问题的最优值,也就是先求解规模较大的问题的最优值。】3、问题:矩阵连乘问题:下图是动态规划算法计算 6 个矩阵 A1A2A3A4A5A6
22、 连乘所生成的信息表.(a)表描述了计算顺序, (b)表是 mij的最优值表,(c)表是辅助信息表(断开位置)。 分析表格,给出 A2A3A4A5A6 五个矩阵连乘所需要的最少数乘次数,并用加括号的方法表示出其乘法顺序。从如下选项中选择。选项:A、15125, (A2(A3A4)(A5A6)B、10500, (A2(A3A4)(A5A6)C、15125, (A2A3)(A4A5)A6)D、 10500, (A2A3)(A4A5)A6)正确答案:【 10500, (A2A3)(A4A5)A6)】4、问题:凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分,首先要分析最优解的结构,也就是将问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- MOOC MOOC答案 中国大学慕课答案