MOOC 算法设计与分析-青岛大学 中国大学慕课答案.docx

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、问题：凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题

23、分解为子问题，并具有最优子结构性质。下图是一凸 6 边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？ 选项：A、右图正确， 9 种B、左图正确， 9 种C、左图正确，4 种D、右图正确， 4 种正确答案:【左图正确，4 种】5、问题：游艇租赁问题：长江游艇俱乐部在长江上设置了 n 个游艇出租站 1n，游客可在这些游艇出租站租用游艇， 并在下游的任何出租站归还游艇，限制只能从上游往下游行进，游艇出租站 i 到出租站 j 直达的租金为 r(i,j)（1=ij=n），计算从游艇出租站 1 到出租站 n 的最小费用。该问题可有二种

24、最优解的结构形式，如图所示： 如下描述中错误的是哪个？选项：A、图 2 方案的算法设计思路：设定二重循环：循环变量 i（问题的终点站编号），循环变量 k（断点位置控制），去计算问题的最优值.时间复杂性为 O(）B、图 1 是将从 i 站到 j 站最小费用问题划分为 2 个子问题 i 到 k 和 k 到 j 的最小费用和，且 ikj，这些不同方式中的最小值还要同 r(i,j)比较， 最小者即为 cost(i,j)C、图 2 是将从 1 站到 i 站的最小费用问题划分为 2 个子问题即从第 1 站到第 k 站的最小费用问题和从 k 站到 i 站的最小费用问题。D、图 1 方案的算法设计思路：设定三

25、重循环：循环变量 r（规模控制），循环遍历 i（规模为 r 的问题个数控制，同时也是问题的首编号），循环变量 k（断点位置控制），去计算问题的最优值,时间复杂性为 O（）正确答案:【图 2 是将从 1 站到 i 站的最小费用问题划分为 2 个子问题即从第 1 站到第 k 站的最小费用问题和从 k 站到 i 站的最小费用问题。】6、问题：0-1 背包问题：现有一背包容量 c=5， n=4。4 个物品分别为：(Wi,Vi)|(1,3), (3,6), (4,9), (2,7)。如下 m 表中 mij是前 i 个物品装背包容量为 j 时的最优值 。其中第四行的数据没有填写，分析问题， 将第四行的数据

26、从如下选项中找出。选项： A、0 3 7 7 10 13B、0 3 3 6 8 15C、0 3 7 10 13 15D、0 3 7 10 10 13正确答案:【0 3 7 10 10 13】7、问题：最长公共子序列问题：现有两个字符序列 X 和 Y, 下面 c 矩阵和 b 矩阵是算法填写出的信息表。 cij是 X 序列的前 i 个字符和 Y 序列的前 j 个字符的最长公共子序列的长度，bij是辅助信息表。已知 X=”ABC”根据表格内容，回答 X 和 Y 的最长公共子序列长度及最长公共子序列包含的符号选项：A、长度 2 “AB”B、长度 1 “C”C、长度 2 “AC”D、长度 1 “A”正确

27、答案:【长度 2 “AC”】8、问题：下面是求最长公共子序列长度和构造最优解的算法。【】中的语句缺失， 请从如下选项中找到正确的答案补齐算法。void LCSLength(int m, int n, char *x,char *y, int *c, int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (j = 1; j = n; i+)c0j = 0; for (i = 1; i = m; i+) for (j = 1; j = n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1; else if (ci-1j=c

28、ij-1) 【1】; bij=2; else 【2】; bij=3; void LCS(int i, int j, char *x, int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); coutxi; else if (bij= 2) 【3】; else 【4】;选项： A、(1)cij=cij-1 (2)cij=ci-1j (3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)B、(1)cij=ci-1j (2)cij=cij-1 (3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)C、(1

29、)cij=cij-1 (2)cij=ci-1j (3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)D、(1)cij=ci-1j (2)cij=cij-1 (3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)正确答案:【(1)cij=ci-1j (2)cij=cij-1 (3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)】9、问题：操场上摆放一行共 n 堆石头，从左到右方向编号为 1n，石子的数目分别为 p1,pn，现要将石子有次序的合并为一堆，规定每次只能选相邻的 2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过 n-1 次合并，

30、最终合并为一堆。计算这 n 堆石子合并为一堆的最小得分。分析该问题，从如下选项中找出用动态规划解决该问题的时间复杂性和空间复杂性选项：A、T（n）=O（ ） S(n)=O(B、T（n）=O（ ） S(n)=O(C、T（n）=O（ ） S(n)=O(D、T（n）=O（ ） S(n)=O()正确答案:【T（n）=O（ ） S(n)=O( )】10、问题：可用动态规划算法解决的问题需要满足几个基本要素，从下面选项中找出这些基本要素选项：A、阶段性B、最优子结构性质C、无后向性D、重复子问题正确答案:【最优子结构性质#重复子问题】11、问题：0-1 背包问题：给定 n 种物品和一背包，物品 i 的重量

31、 wi，价值 vi，背包容量为 c，如何选择装入背包中的物品，使得装入背包中的物品总价值最大。设mij是前 i 个物品装入背包容量为 j 的背包所能获得的最大价值，下面是关于最优值的递归定义，从中选出正确的关于最优值 mij的递归定义。选项：A、B、C、 D、正确答案:【#】12、问题：操场上摆放一行共 n 堆石头，从左到右方向编号为 1n，石子的数目分别为 p1,pn，现要将石子有次序的合并为一堆，规定每次只能选相邻的 2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过 n-1 次合并，最终合并为一堆。计算这 n 堆石子合并为一堆的最小得分。请根据题目要求，从如下选项中找出关于从第

32、 i 堆到第 j 堆合并为一堆的最小得分 mij的递归定义.选项：A、mij=0, if (i=j)B、mij=pi, if (i=j)C、if（ij） mij=min(mik+mk+1j)+sum(i,j) 这里 i= kj， sum（i，j）是 i 堆到 j 堆石子的累加和。D、if（ij） mij=min(mik+mkj)+sum(i,j) 这里 i= kj， sum（i，j）是 i 堆到 j堆石子的累加和。正确答案:【mij=0, if (i=j)#if（ij） mij=min(mik+mk+1j)+sum(i,j) 这里i= kj， sum（i，j）是 i 堆到 j 堆石子的累加和。

33、】13、填空题：操场上摆放一行共 4 堆石头，从左到右方向编号为 14，各堆石子的数目分别为 7,10,3,5，现要将石子有次序的合并为一堆，规定每次只能选相邻的 2堆合并为新的一堆，将新的一堆石子数记为该次合并的得分，经过 5 次合并，最终合并为一堆。计算这 6 堆石子合并为一堆的最小得分正确答案:【50】14、填空题：现有一楼梯共 8 级台阶，有一小朋友一步可以迈出 1、2 或 3 级台阶， 问小朋友有多少种不同的爬楼梯的方法正确答案:【81】第四单元测试1、问题：一个问题，针对某个贪心策略，可通过找反例的方法快速判断出其使用贪心算法不能构造出最优解。下面是关于 0-1 背包问题，贪心策略

34、是优先选择单位重量价值大的物品装入背包，有二个同学分别找到一个反例，证明贪心算法不能构造出 0-1 背包问题的最优解。（1） 背包容量 4，三个物品的重量和价值（wi，vi）:（2，4）,（2，3）,（2，2） （2） 背包容量 5，三个物品的重量和价值（wi， vi）:（1，2）,（2，3）,（4，4）分析判定哪个反例是对的， 哪个反例是错的，从如下选项中找到你的答案。选项：A、（1） 对（2） 错B、（1） 对（2） 对C、（1） 错（2） 错D、（1） 错（2） 对正确答案:【（1） 错（2） 对】2、问题：一个 n 位的 10 进制正整数，使得删除 k 位（kn）后剩余数字组成的正整数

35、最小，用贪心算法实现该算法， 问该问题的贪心策略是什么？也就是每次要删除哪个数字？选项：A、每次从整数中删去数字最大者B、每次从整数中找包含最高位的从左至右的一个最长的非递减序列，将该序列的最后一位删除C、每次删除该整数的最高位数字D、贪心算法不能有效解决该问题正确答案:【每次从整数中找包含最高位的从左至右的一个最长的非递减序列，将该序列的最后一位删除】3、问题：某中学有一个开水房，只有一个供热水龙头， 课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案， 也就是同学们按照他给出的排队方法， 可以使同学们

36、的平均等待时间最短。你分析一下，给出这个排队的方法，假定有 n 个人，第 i 个同学打水所需要的时间为 ti，并给出平均等待时间的计算公式。（注意：第 i 个同学的等待时间包含前 i-1 个的打水时间和+自己打水的时间 ti）选项：A、按照打水时间从大到小排队， 平均等待时间 T=ti/n 1=i=nB、按照打水时间从小到大排队， 平均等待时间 T=ti/n 1=i=nC、按照打水时间从大到小排队，假定排队后第 i 个人的打水时间是 ti, 平均等待时间 T=(n-i+1)ti/n 1=i=nD、按照打水时间从小到大排队，假定排队后第 i 个人的打水时间是 ti, 平均等待时间 T=(n-i+

37、1)ti/n 1=i=n正确答案:【按照打水时间从小到大排队，假定排队后第 i 个人的打水时间是 ti, 平均等待时间 T=(n-i+1)ti/n 1=i=n】4、问题：哈夫曼编码树是用贪心算法解决的典型问题， 分析该算法，回答如下问题， 假定有 n 个字符生成的编码树， 问编码树中的结点总数是多少？可能的最长的字符编码是多少位？选项： A、 2n 个结点， n 位编码B、2n-1 个结点 n-1 位编码C、2n-1 个结点 n 位编码D、2n 个结点 n-1 编码正确答案:【2n-1 个结点 n-1 位编码】5、问题：下图中 AF 顶点分别代表 6 个村庄，图中的边代表村庄之间的距离，为了满

38、足这六个村庄相互通信的需要（任意两个村庄有线路可达），需要架设通信线路，这里要求代价最小化（即线路总长度最小），请你分析问题找到代价最小的方案， 并计算出线路总长度，从如下选项中找出答案。 选项：A、线路总长度 20B、线路总长度 21C、线路总长度 22D、线路总长度 23正确答案:【线路总长度 21】6、问题：一个问题，确定了某个贪心策略， 如果用贪心算法能够构造出问题的最优解， 需要该问题具备哪两个条件？选项： A、没有重复子问题B、最优子结构性质C、无后向性D、贪心选择性质正确答案:【最优子结构性质#贪心选择性质】7、问题：给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另

39、外，给定 V中的一个顶点 A，称为源，求从源顶点 A 出发到其他各顶点的最短路径长度称为单源最短路径长度问题。关于单源最短路径问题的 Dijkstra 算法， 下面哪些描述是正确的？选项：A、设定一个顶点集合 S，初始时，S=A，每次从 V-S 中选择顶点加入 S， 直到全部加入，算法结束。B、每次选择加入 S 集合的顶点是从 A 顶点出发的最短路径长度已知的顶点，也就是 V-S 集合中最短特殊路径长度最小的顶点，通常算法中用 dist 数组记录各顶点的最短特殊路径长度。C、每次从 V-S 集合选择加入 S 集合的顶点是 V-S 集合中的顶点同 S 集合的顶点连接边最短的，通常算法中用 dis

40、t 数组记录 S 集合中各顶点与 V-S 集合中各顶点的最短连接边。D、每次选择一个顶点加入 S 集合后， 都要检查是否需要更新 dist数组元素的值正确答案:【设定一个顶点集合 S，初始时，S=A，每次从 V-S 中选择顶点加入 S， 直到全部加入，算法结束。#每次选择加入 S 集合的顶点是从 A 顶点出发的最短路径长度已知的顶点，也就是 V-S 集合中最短特殊路径长度最小的顶点，通常算法中用 dist 数组记录各顶点的最短特殊路径长度。#每次选择一个顶点加入 S 集合后， 都要检查是否需要更新 dist数组元素的值】8、问题：一个问题，可能有多个最优解， 但是使用贪心算法最多只能找到一个最

41、优解。选项：A、正确B、错误正确答案:【正确】9、问题：教材例题：多机调度问题，是用贪心算法求最优解的一个例子，贪心策略是每次从剩余任务中选择一个花费时间最长的任务，安排在占用时间最少的机器上。选项：A、正确B、错误正确答案:【错误】 10、问题：贪心算法中常包含排序算法， 也就是排序是贪心算法的伴随算法，有人这样解释其原因：贪心算法是根据贪心策略一步一步地选择去构造问题的解，排序就是按照要选择的顺序排列好，选择时只需按照排好的顺序选择就可以了。主要目的就是方便选择。该说法是否正确？选项：A、正确B、错误正确答案:【正确】11、问题：贪心算法是以自底向上的方式构造问题的最优解选项：A、正确B、

42、错误正确答案:【错误】12、填空题：我国的货币单位是 100 元，50 元，20 元、10 元、5 元、2 元、1 元。有人到超市买了 32 元的商品，交给收银员 100 元， 问收银员最少需要几张货币就能完成找零钱？正确答案:【5】13、填空题：最优分解问题：一个正整数分解为若干互不相同的自然数的和，使其乘积最大。使用贪心算法求将 22 这个数最优分解后，取得的最大乘积是多少？正确答案:【1008】第五章 单元测试1、问题：下面关于回溯法的描述中， 不正确的是哪个?选项：A、回溯法可使用递归算法实现B、回溯法是以深度优先的状态生成树法去搜索问题的解，并且能够避免不必要搜索。C、回溯法解决的问

43、题，其解通常可以表达为 n 元组的形式D、回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。正确答案:【回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。】2、问题：下面描述不正确的是？选项：A、解空间树的分类中，尽管子集树的每个非叶子结点都有二个分支， 但是不能把它称为 n 叉树。B、剪枝函数有二种，分别是约束函数和限界函数 C、当解空间树是子集树时，约束函数对 0 分支剪枝，限界函数对 1 分支剪枝。D、对解空间树是 n 叉树（或排列树）来说，回溯法搜索时对每个分支使用的的剪枝条件（函数）是完全相同的。正确答案:【当解空间树是子集

44、树时，约束函数对 0 分支剪枝，限界函数对 1 分支剪枝。】3、问题：n 皇后问题是可用回溯法解决的问题。下面描述不正确的是？选项：A、当其解空间树是 n 叉树时，剪枝函数是任一列或任一（正反）对角线只能安排一个皇后。B、当其解空间树是排列树时，剪枝函数是任一（正反）对角线只能安排一个皇后。C、算法搜索至叶子结点时，就找到了一种新的皇后安排方案，算法可找到所有可行的方案。D、两种不同解空间树的算法效率比较，排列树的时间耗费高于 n 叉树正确答案:【两种不同解空间树的算法效率比较，排列树的时间耗费高于 n 叉树】4、问题：0-1 背包问题的回溯算法，下面的解释不正确的是选项：A、解空间树是子集树B、左(1)分支的剪枝：当选择装入背包的物品重量之和超过背包容量时就剪枝。C、右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）当前最优值 bestp, 就剪枝.D、当搜索至叶子结点时，一定