算法设计与分析 - 中国大学mooc

第一章 算法概论

第一章 单元测试

1、下面列出了算法的四个性质，哪个性质是程序不一定具备的？
    A、有输入
    B、有输出
    C、确定性
    D、有穷性

2、在算法设计与分析过程中，有算法设计，算法的正确性证明，算法的复杂性分析,程序设计等几个重要步骤，下面哪种顺序是正确的？
    A、算法的正确性证明->算法设计->算法的复杂性分析->程序设计
    B、算法的正确性证明->算法的复杂性分析->算法设计->程序设计
    C、算法设计->算法的正确性证明->算法的复杂性分析->程序设计
    D、算法设计->算法的复杂性分析->算法的正确性证明->程序设计

3、下面哪些内容不是算法设计之前要完成的内容?
    A、是求精确解还是近似解
    B、确定合适的数据结构
    C、确定合适的算法策略
    D、使用何种计算机语言设计程序

4、下面是快速幂算法求 的代码，这里n≥0, a是实数。对该算法的时间复杂性描述不准确的是哪个？ doule exp2(double a, int n) { int i; double b, s=1.0； i=n；b=a; while（i>0） { if(i%2) s*=b； i/=2; b*=b; } return s; }
    A、
    B、
    C、
    D、

5、下面那个算法在最坏情况下的时间复杂性最低
    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)的递归定义如下， 问T（n）是?
    A、
    B、
    C、
    D、

11、解决同一个问题的算法策略可能有多个，无论使用那种算法策略，算法时间复杂性是相同的。

12、描述算法只能使用二种方法：伪代码或自然语言

第二章 分治法

第二章 单元测试

1、分治法解决问题分为三步走，即分、治、合。下面列出了几种操作， 请按分、治、合顺序选择正确的表述。（1）将各个子问题的解合并为大问题的解，（2）将问题分解为子问题，（3）将各个子问题合并为大问题。（4）求各个子问题的解，（5）将问题分解为可重复的子问题。
    A、(5)(4)(1)
    B、(2)(4)(1)
    C、(2)(1)(3)
    D、(5)(1)(3)

2、分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程， 然后解此方程可得T(n)的结果。T(n)的递归定义如下： 关于该定义中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)是将子问题的解合并为问题的解的时间复杂性。

3、已知斐波那契数列中第n个斐波那契数F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第n个斐波那契数，从下面选项中选取答案。
    A、能，因为它满足分治法的四个适应条件
    B、能，因为它可以用分、治、合三个步骤完成计算
    C、不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）
    D、不能，因为它不可以用分、治、合三个步骤完成计算

4、快速幂算法求 ， 其时间复杂性为O(logn)，a是实数，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 return exp2(a,n/2)* exp2(a,n/2); } } 对该同学的算法评价正确的是？
    A、运行结果正确，时间复杂性为O(logn)
    B、运行结果错误，时间复杂性为O(n)
    C、运行结果正确，时间复杂性为O(n)
    D、运行结果错误，时间复杂性为O(logn)

5、快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O( ), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？
    A、这是因为归并排序把问题划分为子问题时的时间复杂性低，而快速排序划分为子问题是使用partition()函数，划分为子问题的时间复杂性高。
    B、因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)
    C、归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和
    D、以上都不正确

6、猜数游戏：随机选择一个0~100内的整数，让你猜。 猜对了，你赢了，游戏结束。如果没有猜对，会告诉你猜大了，还是猜小了。当然，越早猜对越好。 问你最多猜多少次就能保证一定能猜对？
    A、6
    B、7
    C、51
    D、101

7、对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文。比如：“abcba”、“abba”是回文，“abc”则不是回文。 bool isPal( char *str, int n) { if ( n == 0 || 【 （1） 】) return true; if ( str[0] != 【 （2） 】) return false; return isPal( 【 （3） 】,【 （4） 】); } 算法中【】处缺少语句，请分析算法，从如下选项中选择语句补齐算法。
    A、(1) n==1 (2) str[n] (3) str+1 (4) n-1
    B、(1) n==1 (2) str[n-1] (3) str+1 (4) n-2
    C、(1) str[0]==str[n-1] (2) str[n-1] (3) str (4) n-1
    D、(1) str[0]==str[n-1] (2) str[n] (3) str (4) n-2

8、对于一个采用字符数组存放的长度为n的字符串str，下面是判断是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”则不是回文 bool isPal( char *str, int n) { if ( n == 0 || 【 （1） 】) return true; if ( str[0] != 【 （2） 】) return false; return isPal( 【 （3） 】,【 （4） 】); } 请补齐代码后分析算法的时间复杂性，回答如下问题
    A、该算法时间复杂性的递归定义为： T(n)=T(n-1)+1，if n>1;T(n)=O(1),if n≤1。 T(n)=O(n), T(n)=Ω(1)
    B、该算法时间复杂性的递归定义为： T(n)=T(n-1)+1,ifn>1;T(n)=O(1),if n≤1。 T(n)=O(n), T(n)=Ω(n)
    C、该算法时间复杂性的递归定义为： T(n)=T(n-2)+1，if n>1;T(n)=O(1), if n≤1。 T(n)=O(n), T(n)=Ω(1)
    D、该算法时间复杂性的递归定义为： T(n)=T(n-2)+1，if n>1;T(n)=O(1), if n≤1。 T(n)=O(n), T(n)=Ω(n)

9、棋盘nxn（ ）的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治算法。关于该算法时间复杂性描述不正确的是
    A、T(n)=4T(n/2)+O(1) , if n>1; T(n)=O(1) ,if n==1 。
    B、T(k)=4T(k-1)+O(1) , if k>0; T(k)=O(1) , if k==0。 这里n=2^k
    C、T(n)=O(n^4)
    D、T(k)=O(4^k)

10、棋盘8X8的覆盖问题，其中一个点已经被覆盖，用L型模块将其余完全覆盖的分治策略。约定解决四个子问题的顺序为右下，左下, 左上，右上。用数字标识法填写覆盖方案（如3个相连的整数值i构成的L块，代表是第i个被放入棋盘中的L型块）。 使用分治策略的算法有三种形式 ：1使用递归算法实现， 2使用队列存取分解出的子棋盘的非递归算法 3.使用栈存取分解出的子棋盘的非递归算法。下图中有三个覆盖图案（只标出了前7块L型模块位置），问自左至右分别是哪种算法实现的覆盖方案？
    A、栈算法，队列算法，递归算法
    B、队列算法，栈算法，递归算法
    C、递归算法，队列算法， 栈算法
    D、递归算法， 栈算法， 队列算法

11、下面哪些不是递归算法的特点
    A、结构清晰
    B、可读性强
    C、容易用数学归纳法证明算法的正确性
    D、递归算法耗费的时间和占用的内存空间要比解决同一问题的非递归算法要少

12、分治法解决问题时，平衡子问题思想是指：划分出的子问题规模基本一致，算法效率高

第三章 动态规划

第三单元测试

1、求第n个斐波那契数的问题，根据动态规划的二要素分析，是可以用动态规划算法去解决的，下面是用备忘录方法（递归）解决的求第n个斐波那契数f[n]的程序. int f[N]={0,1,1}; int fib(int n) { if (【 1 】) return f[n]; else return 【 2 】; } 代码中【1】 和【2】位置代码缺失， 请从下列选项中选出合适的语句补齐算法。
    A、【1】n<3 【2】 fib(n-1)+fib(n-2)
    B、【1】f[n]>0 【2】 fib(n-1)+fib(n-2)
    C、【1】f[n]>0 【2】 f[n]=fib(n-1)+fib(n-2)
    D、【1】 n<3 【2】 f[n]= fib(n-1)+fib(n-2)

2、动态规划解题的步骤分为四步（1）分析最优解的结构 （2）建立递归关系（3）计算最优值（4）构造最优解。关于这四个步骤的内容描述不正确的是哪个？
    A、分析最优解的结构：一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质
    B、建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。
    C、计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。
    D、构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造

3、矩阵连乘问题：下图是动态规划算法计算6个矩阵A1A2A3A4A5A6连乘所生成的信息表. （a）表描述了计算顺序， （b）表是m[i][j]的最优值表，（c）表是辅助信息表（断开位置）。 分析表格，给出A2A3A4A5A6 五个矩阵连乘所需要的最少数乘次数，并用加括号的方法表示出其乘法顺序。从如下选项中选择。
    A、15125, (A2(A3A4))(A5A6)
    B、10500, (A2(A3A4))(A5A6)
    C、15125, (A2A3)((A4A5)A6)
    D、10500, (A2A3)((A4A5)A6)

4、凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形(ABCDEF)的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？
    A、右图正确， 9种
    B、左图正确， 9种
    C、左图正确，4种
    D、右图正确， 4种

5、游艇租赁问题：长江游艇俱乐部在长江上设置了n个游艇出租站1~n，游客可在这些游艇出租站租用游艇， 并在下游的任何出租站归还游艇，限制只能从上游往下游行进，游艇出租站i到出租站j直达的租金为r(i,j)（1<=i<j<=n），计算从游艇出租站1到出租站n的最小费用。该问题可有二种最优解的结构形式，如图所示： 如下描述中错误的是哪个？
    A、图2方案的算法设计思路：设定二重循环：循环变量i（问题的终点站编号），循环变量k（断点位置控制），去计算问题的最优值.时间复杂性为O( ）
    B、图1是将从i站到j站最小费用问题划分为2个子问题i到k和k到j的最小费用和，且i<k<j，这些不同方式中的最小值还要同r(i,j)比较， 最小者即为cost(i,j)
    C、图2是将从1站到i站的最小费用问题划分为2个子问题即从第1站到第k站的最小费用问题和从k站到i站的最小费用问题。
    D、图1方案的算法设计思路：设定三重循环：循环变量r（规模控制），循环遍历i（规模为r的问题个数控制，同时也是问题的首编号），循环变量k（断点位置控制），去计算问题的最优值, 时间复杂性为O（ ）

6、0-1背包问题：现有一背包容量c=5， n=4。 4个物品分别为： (Wi,Vi)| (1,3), (3,6), (4,9), (2,7)。如下m表中m[i][j]是前i个物品装背包容量为j时的最优值。 其中第四行的数据没有填写，分析问题， 将第四行的数据从如下选项中找出。
    A、0 3 7 7 10 13
    B、0 3 3 6 8 15
    C、0 3 7 10 13 15
    D、0 3 7 10 10 13

7、最长公共子序列问题：现有两个字符序列X和Y, 下面c矩阵和b矩阵是算法填写出的信息表。 c[i][j]是X序列的前i个字符和Y序列的前j个字符的最长公共子序列的长度，b[i][j]是辅助信息表。已知X=”ABC” 根据表格内容，回答X和Y的最长公共子序列长度及最长公共子序列包含的符号
    A、长度2 “AB”
    B、长度1 “C”
    C、长度2 “AC”
    D、长度1 “A”

8、下面是求最长公共子序列长度和构造最优解的算法。【】中的语句缺失， 请从如下选项中找到正确的答案补齐算法。 void LCSLength(int m, int n, char *x, char *y, int **c, int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (j = 1; j <= n; i++) c[0][j] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { 【1】; b[i][j]=2; } else { 【2】; b[i][j]=3; } } } void LCS(int i, int j, char *x, int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1,j-1,x,b); cout<<x[i]; } else if (b[i][j]== 2) 【3】; else 【4】; }
    A、(1)c[i][j]=c[i][j-1] (2)c[i][j]=c[i-1][j] (3)LCS(i-1,j,x,b) (4)LCS(i,j-1,x,b)
    B、(1)c[i][j]=c[i-1][j] (2)c[i][j]=c[i][j-1] (3)LCS(i,j-1,x,b) (4)LCS(i-1,j,x,b)
    C、(1)c[i][j]=c[i][j-1] (2)c[i][j]=c[i-1][j] (3)LCS(i,j-1,x,b) (4)LCS(i-1,j,x,b)
    D、(1)c[i][j]=c[i-1][j] (2)c[i][j]=c[i][j-1] (3)LCS(i-1,j,x,b) (4)LCS(i,j-1,x,b)

9、可用动态规划算法解决的问题需要满足几个基本要素，从下面选项中找出这些基本要素
    A、阶段性
    B、最优子结构性质
    C、无后向性
    D、重复子问题

10、0-1背包问题：给定n种物品和一背包，物品i的重量wi，价值vi，背包容量为c，如何选择装入背包中的物品，使得装入背包中的物品总价值最大。设m[i][j]是前i个物品装入背包容量为j的背包所能获得的最大价值，下面是关于最优值的递归定义，从中选出正确的关于最优值m[i][j]的递归定义。
    A、
    B、
    C、
    D、