CSP-S2020初赛易错题解析

二.1.4.将第 14 行的 d[i] < d[j] 改为 d[i] != d[j]，程序输出不会改变。（ ）

答案：正确

解析：因为双层for会遍历所有情况，所以输出不会改变

2.4.当输入的 d[i]d[i] 是严格单调递减序列时，第 17 行的 swap 平均执行次数是( )

A.O(n^2)  B.O(n)  C.O(n log n)  D.O(log n)

正解：

快速排序在数组是降序的情况下，第二层while会一次执行完，所以是O(n)

5.若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )

A.O(n),O(n^2)  B.O(n),O(n log n)  C.O(n log n),O(n^2)  D.O(n log n),O(n log n)

正解：

快速排序查找第K大数平均复杂度是O(n)的，最坏当然是O(n^2)的

6.若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )

A.O(n)  B.O(log n)  C.O(n log n)  D.O(n^2)

正解：

这是快速排序的最坏情况，复杂度退化到O(n^2)