2. 从业资格
  3. 对长度为的线性表做快速排序，在情况下的交换次数是()。A.n B.n-1 B

对长度为的线性表做快速排序，在情况下的交换次数是()。A.n B.n-1 B

最全题库2022-08-02  94
问题 对长度为的线性表做快速排序，在情况下的交换次数是()。A.nB.n-1B.(n-1)D.n (1-1) **
选项 A.n
B.n-1
B.(n-1)
D.n (1-1) **
答案 D
解析 本题考查线性表。线性表快速排序之所以快,是因为每次按照基准将数组分成两个差不多长度的子数组。快速排序最坏的情况下就是每次选的基准数都和其他数做过比较,如果两个子数组中有一个长度为0，也就子问题规模每次只减少了1,此时时间复杂度从nlogn变为n^2,此时就需要递归n-1次。第一次递归比较n-1次，第二次递归比较2n2.次.....第n-1次递归比较1次。综上: (n-1) + (n-2) ....1=+n1 (n-1) 12。故本题选D。
转载请注明原文地址:https://www.tihaiku.com/congyezige/1902250.html
本试题收录于： 中学信息技术学科知识与教学能力题库教师资格笔试分类

中学信息技术学科知识与教学能力

教师资格笔试

相关试题推荐
随机试题
最新回复(0)