算法分析与设计答案2023

第二章测试

1.

时间复杂度是指算法最坏情况下的运行时间。

A:错 B:对
答案:B
2.

f(n)=3n³+7n²+4nlogn =O（n²）

A:错 B:对 3.

如果一个算法是多项式时间算法，该算法是有效的,是好算法。

A:对 B:错 4.

算法复杂度分析的两种基本方法为（  ）和（    ）。

A:平摊复杂度 平滑复杂度 B:几何复杂度  平均复杂度 C:结构化方法 面向对象方法 D:事后统计  事前分析 5.

下面程序的时间复杂度为（）  

x=1

for i=1 to n  do

for j=1 to i do           

for k=1 to j do     

         x++  

A:O(n^3) B:O(n^2) C:O(n) D:O(nlogn) 6.

对近似递增序列的线性表从小到大排序，使用哪种方法好？

A:插入排序 B:归并排序 C:快速排序 D:堆排序 7.

顺序查找适合的数据结构是（）

A:顺序存储 B:压缩存储 C:散列存储 D:链式存储 8.

给定n个元素的数组A，n=10^{^3}, 使用折半查找比使用顺序查找大约快___倍。

A:1000
B:10
C:10^(3/2)
D:100
9.

则f(n)的渐进性态f(n)=Ω(    )

A:1
B:n^2
C:n
D:100
10.

f=O(g) 当且仅当 g =Ω (f)

A:错 B:对