本文主要是介绍数据结构 排序 思考题1,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案
题目1: 对于7个数进行冒泡排序,最坏情况下需要进行的比较次数为
-
A. 7
-
B. 14
-
C. 21
-
D. 49
第一轮冒泡,索引 1 的数与索引 2 的数比较,2与3比较……6与7比较,比较6次。
第二轮就是5次。以此类推,到最后一轮只有一个数的时候不进行比较,是0次。
6+5+4+3+2+1+0= 21
题目二:给定初始序列{34, 8, 64, 51, 32, 21},冒泡排序和插入排序分别需要多少次元素交换才能完成?
-
A. 冒泡8次,插入8次
-
B. 冒泡8次,插入9次
-
C. 冒泡9次,插入8次
-
D. 冒泡9次,插入9次
首先我们需要明白究竟是从大到小还是从小到大排序,题目中没说,所以我们直接使用课程里给的代码:
冒泡排序:
第一轮:34和8换,64和51换,64和32换,64和21换。{8,34,51,32,21,64}
第二轮:51和32换,51和21换。{8,34,32,21,51,64}
第三轮:34和32换,34和21换。{8,32,21,34,51,64}
第四轮:32和21换。{8,21,32,34,51,64}
总共9次。
插入排序:
第一轮,放入34,{34}
第二轮,放入8,交换一次{8,34}
第三轮,放入64,不交换{8,34,64}
第四轮,放入51,需要跟64交换(所谓交换就是64后移){8,34,51,64}
第五轮,放入32,需要跟64,51,34交换{8,32,34,51,64}
第五轮,放入21,需要跟32,34,51,64交换{8,21,32,34,51,64}
总共交换9次
题目三:对一组包含10个元素的非递减有序序列,采用插入排序排成非递增序列,其可能的比较次数和移动次数分别是
-
A. 45, 44
-
B. 54, 63
-
C. 100, 54
-
D. 100, 100
移动100次这就不可能了。移动的次数小于比较的也是不可能的。所以选A
题目四:序列{34, 8, 64, 51, 32, 21}中有多少逆序对?
-
A. 7
-
B. 8
-
C. 9
-
D. 10
选C
题目五:希尔排序是稳定的。
-
A. √
-
B. ×
错。
可以看到,比如我们有这种情况:
1 4 4 3 ,增量为2,那么,索引 0 和索引 2 的不需要交换,但是索引 1 和 索引 3 的需要交换一下。所以 4 和 4 虽然一样,但是希尔排序后两个的位置换了一下,即不稳定。
这篇关于数据结构 排序 思考题1的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!