高中信息技术

单选题对长度为n的线性表做快速排序,在最坏情况下的交换次数是()。

A.n
B.n-1
C.n(n-1)
D.n(n-1)/2

参考答案:D进入在线模考
快速排序的基本思路是:在待排序的n条记录中任选一条记录(通常取第一条记录),以该记录的关键字值为基准,用交换的方法将所有记录分成两部分,使所有关键字值比基准小的记录均排在基准记录之前,所有关键字值比基准大的记录都排在基准记录之后,基准记录在两部分中间,其位置为该基准记录的最终位置,它不再参加以后的排序,这就完成了一趟排序。接着对所划分的前后两部分分别重复上面的操作,直到每部分内只有一条记录为止,排序结束。在最坏的情况下,每次划分选取的基准记录都是当前无序区中最小(或最大)的记录,划分的结果是基准记录左边的无序子区为空(或右边的无序子区为空),另外一方的无序子区中记录数目仅仅比划分前的无序区中的记录个数少1个。在此情况下,快速排序必须进行n-1趟排序,每趟需比较并交换n-1次,需要交换的总次数为(n-1)+(n-2)+(n-3)+…1=n(n-1)/2。

你可能感兴趣的试题

1用于实现身份鉴别的安全机制是()。

A.加密机制和数字签名机制
B.力口密机制和访问控制机制
C.数字签名机制和自由控制机制
D.访问控制机制和路由控制机制

3某二叉树结构如图6所示,其后序遍历的结果是( )
 

A.ABDFGCEH
B.FDGBAEHC
C.FCDBHECA
D.HECAGFDB

最新试题

阅读材料,根据要求完成任务。 计算机是信息时代进行数据处理的主要工具,学生理解“数据是如何存入计算机中的? 它们在计

类型:简答题2023-02-03

案例: 为了考查学生对Python语言中循环结构程序的理解情况,特别是range()#c,print()函数相关的参数

类型:简答题2023-02-03

案例: 在教授“信息编码”一课时,王老师利用电影中谍报人员接或留电的剧情导入。随后,他请同学们扮演谍报人员,将接收的密

类型:简答题2023-02-03

请依据《普通高中信息技术课程标准(2017年版2020年修订)》,简述信息社会责任的内涵及具有信息社会责任的学生有哪些主

类型:简答题2023-02-03

我国古代数学家张丘建在《算经》中提出了一个著名的数学问题:“鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁

类型:简答题2023-02-03

为了宣传我国人民的抗疫精神和成果,李明同学计划制作一个视频作品,并在网上发布。请简要回答该作品的制作和发布需要经过的主要

类型:简答题2023-02-03

若通信协议使用的生成码多项式为G(x)=x3+x2+1,接收方接收到的比特串是10110010101011,经检测传输结

类型:单选题2023-02-03

某二叉树结构如图6所示,其后序遍历的结果是( )  

类型:单选题2023-02-03

运行如图5所示的Python程序片段,可以统计“1,2,3,4”四个数字能够组成多少个互不相同且无重复数字的三位数。横线

类型:单选题2023-02-03

用于实现身份鉴别的安全机制是()。

类型:单选题2023-02-03