1.在最坏情况下
A. 快速排序的时间复杂度比冒泡排序的时间复杂度要小
B. 快速排序的时间复杂度比希尔排序的时间复杂度要小
C. 希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D. 快速排序的时间复杂度与希尔排序的时间复杂度是一样的
正确答案：C 你的答案：
解析：【解析】对长度为 n 的线性表排序，下表为常用排序方法时间复杂度：
上表中未包括希尔排序，因为希尔排序的时间效率与所取的增量序列有关，如果增量序列为：
d1=n/2, di+1=di/2，在最坏情况下，希尔排序所需要的比较次数为 O(n^1.5)。快速排序
与冒泡排序的时间复杂度均为 O(n^2)，A 选项错误。快速排序比希尔排序的时间复杂度要
大（O(n^2)>O(n^1.5))，B 选项错误。希尔排序的时间复杂度比直接插入排序的时间复杂
度 要小（ O(n^1.5)<O(n^2))，C 选项 正确 。快速 排序 比 希 尔 排序 的 时 间 复 杂 度 大
（O(n^2)>O(n^1.5))，D 选项错误。
2.在深度为 7 的满二叉树中，度为 2 的结点个数为
A. 64
B. 63
剩余39页未读，继续阅读
资源评论
