2021 算法分析与设计(山东财经大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-09-05到2022-01-10

第二章 算法分析 第二章 测验

小提示:本节包含奇怪的同名章节内容

1、 问题:从资源划分，算法的复杂度分为（
）和（）。
选项：
A:时间复杂度  空间复杂度     
B:空间复杂度   平均复杂度
C:最好复杂度 最坏复杂度
D:时间间复杂度   平均复杂度
答案: 【时间复杂度  空间复杂度     】

2、 问题:算法复杂度分析的两种基本方法为（  ）和（    ）
选项：
A:结构化方法 面向对象方法 
B:事后统计  事前分析
C:几何复杂度  平均复杂度  
D: 平摊复杂度 平滑复杂度
答案: 【事后统计  事前分析】

3、 问题:设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≥Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）=W（g（N）），即f（N）的阶（   ）g（N）的阶。
选项：
A:不高于
B:不低于 
C:等价于
D:逼近
答案: 【不低于 】

4、 问题: f(n)=   100     当n为奇数 f(n)=5n^2+3n.   当n为偶数   f(n)的渐进性态f(n)= W(    )
选项：
A: n  
B:n^2
C:2^n
D:1
答案: 【1】

5、 问题:下面程序的时间复杂度为（）  x=1for i=1 to n  dofor j=1 to i do           for k=1 to j do                   
                x++ 
选项：
A:n
B:n^3
C:n^2
D:nlogn
答案: 【n^3】

6、 问题:对近似递增序列的线性表从小到大排序，使用哪种方法好？
选项：
A:堆排序 
B:快速排序
C:插入排序
D:归并排序
答案: 【插入排序】

7、 问题:给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
选项：
A:10
B:100
C:1000
D:141
答案: 【100】

8、 问题:给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ(  )
选项：
A:n
B:m
C:n+m
D:n^m
答案: 【n+m】

9、 问题:logn!=Q(    ) 
选项：
A:n
B:nlogn
C:n^2
D:logn   
答案: 【nlogn】

10、 问题:顺序查找的时间复杂度为（）
选项：
A:θ(n)  
B:O(n^2）
C:O(logn)
D:o(n^2)
答案: 【θ(n)   】

11、 问题:下面程序的时间复杂度是（）             i=1while(i<=n)
do       i=i*3
选项：
A:Q(logn)  
B:Q(n)
C:O(n)  
D: Ω(n)
答案: 【Q(logn)  】

12、 问题:给定n个整数，n个数的取值范围为[1,k],计数排序的时间复杂度是O （n+k） 。
选项：
A:n+k
B:n
C:k
D:nk
答案: 【n+k】

13、 问题:给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为(  ) 
选项：
A:θ(n^2)  
B:O(n)
C:W(n^2) 
D:o(n^2)
答案: 【θ(n^2)   】

14、 问题:顺序查找适合的数据结构是（）
选项：
A:散列存储
B:顺序存储
C:链式存储
D:压缩存储
答案: 【顺序存储;
链式存储 】

15、 问题:f(n)=3n^3+7n^2+4nlogn =（）（n^3）
选项：
A:Ο
B:Ω
C:θ
D:o 
E:ω
答案: 【Ο;
Ω;
θ】

16、 问题:下面那些算法的时间复杂度为O（n^2）?
选项：
A:顺序查找
B:折半查找  
C:插入排序
D:冒泡排序
E:折半插入排序
答案: 【插入排序;
冒泡排序;
折半插入排序】

17、 问题:两个n*n的矩阵相加的时间复杂度是（ ）
选项：
A:θ(n^2)
B:O(n^2)
C:W(n^2)
D:o(n^2)
答案: 【θ(n^2);
O(n^2);
W(n^2)】

18、 问题:以空间换时间的方法有（）
选项：
A:预处理 
B:预构造
C:动态规划
D:数据压缩
答案: 【预处理  ;
预构造;
动态规划】

19、 问题:时间复杂度是指算法最坏情况下的运行时间。
选项：
A:正确
B:错误
答案: 【正确】

20、 问题:f(n)=O(g(n)).
g(n)=O(h(n))    则h(n)=O(f(n)) 
选项：
A:正确
B:错误
答案: 【错误】

21、 问题:f(n)=O(g(n))  则 f(n)^2=O(g(n)^2)  
选项：
A:正确
B:错误
答案: 【正确】

22、 问题:f(n)=3n^3+7n^2+4nlogn =O（n^2）
选项：
A:正确
B:错误
答案: 【错误】