算法分析与设计（山东联盟）第二章测试_智慧树知到答案2021年

第二章 算法分析：介绍算法的时间和空间复杂度, 算法复杂度分析和比较的方法,常用算法的复杂度分析，以及时空均衡的概念和处理方法。2.1算法分析:引入时间复杂度和空间复杂度的概念，介绍算法分析的方法和阶段，问题的规模和关键操作。
2.2几个符号:介绍算法渐近复杂性的数学表述和性质，算法的上界、下界、同阶、高阶和低阶的表示。算法的分类和划分标准。
2.3复杂度比较:算法复杂度比较的方法和实例分析。
2.4分析实例:实例分析常用算法的复杂度。
2.5时空均衡:时空均衡的概念和处理方法。

[判断题]时间复杂度是指算法最坏情况下的运行时间。
对
错
答案：对
[判断题]f(n)=3n3+7n2+4nlogn =O（n2）
错
对
答案：错
[判断题]如果一个算法是多项式时间算法，该算法是有效的,是好算法。
错
对
答案：对
[单选题]算法复杂度分析的两种基本方法为（  ）和（    ）。
几何复杂度  平均复杂度
平摊复杂度 平滑复杂度
事后统计  事前分析
结构化方法 面向对象方法
答案：事后统计  事前分析
[单选题]下面程序的时间复杂度为（）  x=1for i=1 to n  dofor j=1 to i do           for k=1 to j do              x++  
O(n^2)
O(n)
O(n^3)
O(nlogn)
答案：n^3
[单选题]对近似递增序列的线性表从小到大排序，使用哪种方法好？
堆排序
插入排序
归并排序
快速排序
答案：插入排序
[多选题]顺序查找适合的数据结构是（）
链式存储
压缩存储
顺序存储
散列存储
答案：顺序存储
链式存储
[单选题]给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。
10^(3/2)

10

100

1000

答案：100
[单选题]则f(n)的渐进性态f(n)=Ω(    )
n

1

n^2

100

答案：1
[判断题]f=O(g) 当且仅当 g =Ω (f)
错
对
答案：对