单选题
高中信息技术
题号 #6110568
对长度为的线性表做快速排序,在情况下的交换次数是()。
参考答案
D
答案解析
本题考查线性表。线性表快速排序之所以快,是因为每次按照基准将数组分成两个差不多长度的子数组。快速排序最坏的情况下就是每次选的基准数都和其他数做过比较,如果两个子数组中有一个长度为0,也就子问题规模每次只减少了1,此时时间复杂度从nlogn变为n^2,此时就需要递归n-1次。第一次递归比较n-1次,第二次递归比较2n2.次.....第n-1次递归比较1次。综上: (n-1) + (n-2) ....1=+n1 (n-1) 12。故本题选D。
你可能感兴趣的试题
A.加密机制和数字签名机制
A.加密机制和数字签名**
B.加密机制和访问控制机制
B.加密机制和访问控制机制
C.数字签名机制和路由控制机制
C.数字签名机制和路由控制机制
D.访问控制机制和路由控制机制
D.访问控制机制和路由控制机制
A.inrange (1, 4)
A.inrange (1, 4)
B.inrange (1, 5)
B.inrange (1, 5)
C.in random.uniform (*, 4)
C.in random.uniform (*, 4)
D.in random.uniform (1, 5)
D.in random.uniform (1, 5)
A.ABDFGCEH
A.ABDFGCE*
B.FDGBAEHC
B.FDGBAEHC
C.FGDBHECA
C.FGDBHECA
D.HECAGFDB
D.HECAGFDB

