数据结构习题-排序-简答题 <编程 编程学习 IT料理>
数据结构习题 <编程 编程学习 IT料理>
简答题
- 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。
比较 移动
- 属于不稳定排序的有__________
希尔排序、简单选择排序、快速排序、堆排序等
- 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法
冒泡 快速
- 直接插入排序用监视哨的作用是_______
免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率
- 对 n 个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______
n(n-1)/2
- 从平均时间性能而言，__________排序最佳
快速
- 快速排序在_____的情况下最易发挥其长处
最好每次划分能得到两个长度相等的子文件
- 在数据表有序时，快速排序算法的时间复杂度是____
O(n^2)
- 堆排序的算法时间复杂度为：_____
O(nlog2 n)
- 设有 5 个互不相同的元素 a、b、c、d、e，能否通过 7 次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因
可以做到。取a与b进行比较，c与d进行比较。设a>b,c>d(ad，则有序a>b>d；若bd>b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。
- 设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大
对冒泡算法而言，初始序列为反序时交换次数最多。
- 设待排序的记录共 7 个，排序码分别为 8，3，2，5，9，1，6。
(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(3) 直接插入排序算法和直接选择排序算法的稳定性如何？
(1)直接插入排序
第一趟(3)[8,3],2,5,9,1,6
第二趟(2)[8,3,2],5,9,1,6
第三趟(5)[8,5,3,2],9,1,6
第四趟(9)[9,8,5,3,2],1,6
第五趟(1)[9,8,5,3,2,1],6
第六趟(6)[9,8,6,5,3,2,1]
(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）
第一趟(9)[9],3,2,5,8,1,6
第二趟(8)[9,8],2,5,3,1,6
第三趟(6)[9,8,6],5,3,1,2
第四趟(5)[9,8,6,5],3,1,2
第五趟(3)[9,8,6,5,3],1,2
第六趟(2)[9,8,6,5,3,2],1
(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。
- 在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是哪种？
快速排序
- 快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？
不是。因为当序列已有序时，快速排序将退化成冒泡排序，时间复杂度为O(n2)。当待排序序列无序，使每次划分完成后，枢轴两侧子文件长度相当，此时快速排序性能最好。
- 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素 28 进行划分，写出其快速排序第一遍的排序过程
初始序列：[28],07,39,10,65,14,61,17,50,21
21移动：21,07,39,10,65,14,61,17,50,[]
39移动：21,07,[],10,65,14,61,17,50,39
17移动：21,07,17,10,65,14,61,[],50,39
65移动：21,07,17,10,[],14,61,65,50,39
14移动：21,07,17,10,14,[28],61,65,50,39
- 判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
(1)是大堆；(2)是大堆；（4）是小堆；
(3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，20