重庆大学201803批次2算法设计分析D卷答案

青青

201803考试批次2算法设计分析D卷
算法设计分析
题号 一 二 三 四 五  合计
已做/题量 10 / 10 10 / 10 10 / 10 2 / 2 2 / 2 34 / 34
得分/分值 18 / 20 20 / 20 0 / 10 0 / 20 0 / 30 38 / 100
一 、 单项选择题 (共 10 题、18 / 20 分 )
1、
设 m[i, j] 为计算矩阵链Ai…j 所需的乘法运算次数的最小值，则矩阵链A1…n所需的乘法运算次数的最小值为（  ）。
A、
m[1,n+1]
B、
m[1,n-1]
C、
m[1,n]
D、
m[0,n]
收藏该题
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)
B、
n*factorial(n-1)
C、
n*factorial(n-2)
D、
n*factorial(n+1)
收藏该题
8、
实现归并排序利用的算法是（）。
A、
回溯法
B、
动态规划法
C、
贪心法
D、
分治策略
收藏该题
9、
衡量一个算法好坏的标准是（ ）。
A、
时间复杂度低
B、
占用空间少
C、
运行速度快
D、
代码短
收藏该题
10、
如图所示的Huffmann树，
字符s的编码是（    ）。
A、
1110
B、
010
C、
1111
D、
1010
收藏该题
二 、 判断题 (共 10 题、20 / 20 分 )
1、
应用Huffmann编码的目的是用更少的比特流表达更多的信息。（   ）
正确
错误
收藏该题
2、
两个序列的最长公共子序列可以帮助评价两个序列的相似度。（  ）
正确
错误
收藏该题
3、
算法就是一组有穷的规则。( )
正确
错误
收藏该题
4、
要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。( )
正确
错误
收藏该题
5、
归并排序算法是渐近最优算法？( )
正确
错误
收藏该题
6、
最小代价生成树是贪心法的一个经典例子。( )
正确
错误
收藏该题
7、
当n取值较大时，指数时间算法和多项式时间算法在计算时间上差别不大( )
正确
错误
收藏该题
8、
基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法要好( )
正确
错误
收藏该题
9、
T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数n0和c，n〉n0，有T(n)<cf(n)，这种关系记作T(n)=O(f(n))。 （ ）
正确
错误
收藏该题
10、
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。( )
正确
错误
收藏该题
三 、 填空题 (共 10 题、0 / 10 分 )
1、
程序的性能一般指程序的空间复杂性和 ______ 复杂性。
收藏该题
2、
计算机算法指的是解决问题的 ______ 和 ______。
收藏该题
3、
写出两种典型的排序法： ______ 、 ______ 。（其中任意两种即可）
收藏该题
4、
数据的基本单位称为 ______ 。
收藏该题
5、
交换两个参数的函数，用c语言实现：
Public static void swap (int *m, int *n )
{ int *temp= m;
m=n;
______ ;
}
收藏该题
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;
}
收藏该题
2、
设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?
收藏该题
五 、 问答题 (共 2 题、0 / 30 分 )
1、
输入三个不相同的数，求出其中的最小数。用自然语言描述算法。
收藏该题
2、
什么是算法的确定性？
收藏该题
特别提醒：
1、本试卷共有各类试题总数（34）题；
2、客观题由系统自动判卷，主观题需要等待教师批改。
3、按照主观题顺序依次将作业中的主观题答案写到WORD文档当中，每题请标明题号，便于教师批改。
4、点击下方上传按钮，在弹出的页面上传你的答题文件。
5、请不要改变原来的文件扩展名。否则教师在批改时无法打开文件。
6、答案成功上传后，将在主观题答题区下方显示你上传的文件，你可以点击打开查看。
7、重新上传附件可以替换原来的文件。
8、多个文件请压缩为一个压缩包再上传。
9、上传答案后出现“上传成功！”提示，才表示答案附件上传成功。
答案附件：D:\Downland\算法设计分析.docx
  >