数据结构排序答案(数据结构排序算法题)
导语：华文慕课-数据结构内排序题库
1、已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用直接插入排序的方法（第一个数字不用插入）,写出第四次向前面有序表插入一个元素后的排列结果。
解析
未插入元素前，排列结果为46 74 16 53 14 26 40 38 86 65 27 34
第一次插入74，结果为 46 74 16 53 14 26 40 38 86 65 27 34
第二次插入16，结果为 16 46 74 53 14 26 40 38 86 65 27 34
第三次插入53，结果为 16 46 53 74 14 26 40 38 86 65 27 34
第四次插入14，结果为 14 16 46 53 74 26 40 38 86 65 27 34
答案： 14 16 46 53 74 26 40 38 86 65 27 34
2、下列排序方法的比较次数与记录的初始排列状态无关的是：
A、直接选择排序
B、直接插入排序
C、冒泡排序
D、快速排序
解析
直接选择排序不管记录初始排列如何，第i趟排序中选出最小关键字的记录都需要比较n-i次，选最小关键字一共需要比较
n-1+n-2+...+1=n(n-1)/2 次，还有比较是否需要交换关键字，一共n-1次
3、某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用快速排序方法（课程中介绍的快速排序实现方式），取第一个元素值６作为分割数，将Ａ中元素由小到大排序，写出快速排序第一次分隔后Ａ中的结果()。
解析
选择轴值并存储轴值;
最后一个元素放到轴值位置;
初始化下标 i, j，分别指向头尾;
i 递增直到遇到比轴值大的元素，将此元素覆盖到j的位置；j 递减直到遇到比轴值小的元素，将此元素覆盖到 i 的位置；
重复上一步直到 i==j，将轴值放到 i 的位置，完毕。
答案： 1 2 0 5 3 4 6 8 7 9
扩展一个例子：
4、在对一组记录（50，40，95，20，15，70，60，45，80）进行从小到大冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。
解析
参考上课的例子：
从最后两个元素开始
第一趟需要交换45和60，45和70，15和20，15和95，15和40，15和50，所以共6次，
而交换7趟过后，就已经NoSwap==true了，故答案为6 7
答案： 6 7
5、需要对1000个大型的记录进行排序，记录本身存储在外存中，在内存中只保存了所有记录的排序码。排序码之间的比较非常快，但是移动代价很大，因为一旦移动一个排序码，相应的外存中的记录也要移动，将涉及上百个磁盘块的移动，应该使用何种排序方法（）
A、直接选择排序
B、堆排序
C、快速排序
D、插入排序
解析
应该选择直接选择排序，此排序法可以达到尽量少的移动量，虽然比较次数达到N^2,但是相对于外存的处理时间来说，不是关键因素。
6、已知一组元素的排序码为(67, 34, 56, 12, 88, 3, 15, 36, 27, 98, 11, 55)，利用自顶向下划分的非优化归并排序方法（划分到小于等于2个元素），写出第二趟二路归并排序后的结果。
参考例子：归并排序
自顶向下拆分
(67, 34, 56, 12, 88, 3, 15, 36, 27, 98, 11, 55）
(67, 34, 56, 12, 88, 3) (15, 36, 27, 98, 11, 55)
(67, 34, 56) (12, 88, 3) (15, 36, 27) (98, 11, 55)
(67)(34, 56) (12)(88, 3) (15)( 36, 27) (98)(11, 55)
再归并
(34 56 67) (3 12 88) (15 27 36) (11 55 98)
(3 12 34 56 67 88) (11 15 27 36 55 98)
(3 11 12 15 27 34 36 55 56 67 88 98)
第一趟二路归并结果：（34 56 67 ）（3 12 88）（ 15 27 36 ）（11 55 98）
第二趟二路归并结果：（3 12 34 56 67 88）（ 11 15 27 36 55 98）
答案： 3 12 34 56 67 88 11 15 27 36 55 98
7、排序算法大都是基于数组实现的，大部分的算法也能用链表来实现，但有些特殊的算法不适合线性链表存储，不适合（使算法复杂度增大）链式存储的算法有
A、堆排序
B、shell排序
C、直接选择排序
D、插入排序
E、归并排序
F、快速排序
解析
堆排序：因为需要随机访问。
shell排序：它是采用增量序列{2k,2k-1,…,2,1}，也就是说对每隔n个（n为增量序列的某个数）数字进行排序，这种方法过于依赖数据的位置，用链式存储，实在是很不方便。
直接选择排序：用一个指针维护已排好序的数组末尾（也就是乱序数组开头）就可以了。
插入排序：不需要随机访问，是顺序访问并且移动的，而且移动操作比较多，所以用链表比较合适
归并排序：不需要随机访问，是顺序访问并且合并的，而且移动操作比较多，所以用链表比较合适
快速排序：不需要随机访问，是顺序访问并且移动的，而且移动操作比较多，所以用链表比较合适
8、对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法
A、插入排序
B、堆排序
C、快速排序
D、归并排序
显示解析
如果初始状态递增，插入排序不需要交换，只需要n-1次比较，是最少时间代价的。而堆排序需要建堆，归并排序需要分组排序再合并，都需要数据的移动时间。而快速排序需要的比较次数太多，最小时间代价为Θ(nlog n)
9、下面的排序算法哪些是稳定的()。
A、插入排序
B、冒泡排序
C、归并排序
D、桶式排序
E、shell排序
F、选择排序
G、堆排序
H、快速排序
10、假设数组长度为n (n>=20)，基数为r (r>=10)，排序码个数为d (d>=3)，则采用顺序存储的基数排序的空间复杂度至少为 Θ(________)
A、n+r
B、n
解析：
该例子中，数组长度为10000，基数为10：0 1 2 3 4 5 6 7 8 9，排序码个数为4：个十百千
11、对于序列{E，A，S，Y，Q，U，E，S，T，I，O，N}，以{6，3，1}为增量采用Shell排序。头两趟{6，3}增量排序后，关键字的累积比较次数为：17
解析：
第一趟比较的时候，E和E比较，A和S比较，S和T比较，Y和I比较后交换，Q和O比较后交换，U和N比较后交换，结果为是EASIONESTYQU。 然后EIEY分为一组，用插入排序需要比较IE EI EE YI，AOSQ分为一组，比较OA SO QS QO，SNTU分为一组，比较NS TS UT。第一趟比较次数为6，第二趟比较次数为11。
12、下面是图的拓扑排序的是？(多选)
A、2 8 0 7 1 3 5 6 4 9 10 11 12
B、2 8 7 0 6 9 11 12 10 1 3 5 4
C、8 2 7 3 0 6 1 5 4 9 10 11 12
D、8 2 7 0 6 9 10 11 12 1 3 5 4
解析：
每次删除入度为0的节点，及这个节点的所有出边。均是一条拓扑排序的结果。
13、在图书馆里计算机类书籍区一共有12列书架，书架上的书本来都是按照编目号排列好的，其中有些书被读者放错了地方，但通常不会超过一个书架。来将这些书重新放回正确位置，应该使用何种排序方法：
A、插入排序
B、归并排序
C、快速排序
D、直接选择排序
E、堆排序
解析：
既然偏移的位置并不是很远，而且大部分有序，那么可以选择插入排序。
14、15个记录的冒泡排序算法所需最大交换次数为______，最小交换次数为______。
解析
n个记录的冒泡排序算法的最大交换次数为n(n-1)/2,最小交换次数为0
答案：105和0
本文内容由小悦整理编辑！