28-算法设计分析
201803批次网上考试算法设计分析B卷
一 、 单项选择题 (共 10 题、0 / 20 分 )
1、设 m[i, j] 为计算矩阵链Ai…j 所需的乘法运算次数的最小值，则矩阵链A1…n所需的乘运算次数的最小值为（ ）。
A、m[1,n-1]
B、m[1,n]
C、m[0,n]
D、m[1,n+1]
2、二分搜索算法是基于（ ）设计的算法。
A、穷尽法
B、动态规划法
C、分治法
D、贪心法
3、直接或间接的调用自身的算法称为（ ）。
A、迭代算法
B、递归算法
C、动态规划算法
D、贪心算法
4、算法分析的两个主要方面是（ ）。
A、可读性和文档性
B、正确性和简单性
C、空间复杂度和时间复杂度
5、下述关于最优子结构的说法，不正确的是（ ）。
A、原问题的最优解包含子问题的最优解
B、原问题的最优解依赖于子问题的最优解
C、原问题的最优解建立在子问题的最优解基础之上
D、原问题的最优解通过子问题的非最优解合并而得
6、衡量一个算法好坏的标准是( ）。
A、代码短
B、时间复杂度低
C、运行速度快
D、占用空间少
7、阶乘函数用递归定义
Public static int factorial(int n)
{
if(n==0) return 1;
return ( ) ;
}
A、n*factorial(n+1)
B、n*factorial(n-2)
C、n*factorial(n-1)
D、n*factorial(n)
8、以下关于贪心算法，不正确的说法是 （ ）。
A、用于解决优化问题
B、总是选择在当前看来最好的选择
C、所需求解的问题可以不满足最优子结构性质
D、期望通过局部最优达到全局最优
9、一个p行q列的矩形同一个q行r列的矩形相乘，总共要作多少次乘法运算？（ ）
A、 p x q x r
B、 p x r
C、q2
D、q3
10、二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较：如果（ ），则只要在数组a的左半部继续搜索x。
A、x=a[n/2]
B、x>a[n/2]
C、x>=a[n/2]
D、x＜a[n/2]
二 、 判断题 (共 10 题、0 / 20 分 )
1、应用Huffmann编码的目的是用更少的比特流表达更多的信息。（ ）
正确
错误
2、两个序列的最长公共子序列可以帮助评价两个序列的相似度。（ ）
正确
错误
3、算法就是一组有穷的规则。( )
正确
错误
4、要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。( )
正确
错误
5、归并排序算法是渐近最优算法？( )
正确
错误
6、最小代价生成树是贪心法的一个经典例子。( )
正确
错误
7、找零钱问题可以用动态规划算法求解。（ ）
正确
错误
8、二分搜索方法在最坏的情况下用O(log n)时间完成搜索任务。（ ）
正确
错误
9、在活动选择问题中，如果活动A晚于活动B开始，则两个活动相容。（ ）
正确
错误
10、动态规划的一个重要思想是要记住已经计算过的子问题的解。（ ）
正确
错误
三 、 填空题 (共 10 题、0 / 10 分 )
1、程序的性能一般指程序的空间复杂性和 ______ 复杂性。时间
2、计算机算法指的是解决问题的 ______ 和 ______。方法 过程
3、权最小的生成树 (或耗费最小的生成树) 称为G的 ______ 。最小生成树
4、写出两种典型的排序法： ______ 、 ______ 。（其中任意两种即可）归并排序/快速排序 /选择排序/起泡排序
5、数据的基本单位称为 ______ 。数据元素
6、矩阵连乘问题的算法可由（动态规划算法 ）设计实现。
7、程序是______用某种程序设计语言的具体实现。算法
8、算法的时间复杂度随着问题规模n的增大而 ____增大__ 。
9、最优子结构性质的含义是_问题的最优解包含其子问题的最优解____。
10、贪心算法与动态规划算法的主要区别是__贪心选择性质____。
四 、 简答题 (共 2 题、0 / 20 分 )
1下面程序段的所需要的计算时间为___________
int MaxSum(int n, int *a, int &besti, int &bestj) {
int sum=0;
for(int i=1;i<=n;i++){
int thissum=0;
for(int j=i;j<=n;j++){
thissum+=a[j];
if(thissum>sum) {
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
参考答案：
O(n2)
2、设是一个流网络，(S,T)被称为G的一个割的条件是什么？
[P_B9A8580A891977EC8A6C54B5DFF7E962]
五 、 问答题 (共 2 题、0 / 30 分 )
1、 输入三个不相同的数，求出其中的最小数。用自然语言描述算法。
参考答案：
先设置一个变量min，用于存放最小数。当输入a、b、c三个不相同的数后，先将a与b进行比较，把小者送给变量min，再把c与min 进行比较，若c＜min，则min=c。
2、 试简述归并排序算法的基本思想？
