●Shell排序、快速排序、堆排序的稳定性如何? (23) 。若要尽可能的完成对实数数组的排序,且要求排序

Question

●Shell排序、快速排序、堆排序的稳定性如何? (23) 。

若要尽可能的完成对实数数组的排序，且要求排序是稳定的，则应选 (24) 。

若用插入排序算法对n个记录进行排序，最佳情况下，对关键字进行的比较次数为 (25) 。

对于多关键字而言， (26) 是一种方便而又高效的文件组织方式。

若用冒泡排序对关键字序列{19，16，11，8，5，3}从小到大进行排序，则需要次数为 (27) 。

(23) A．Shell排序是稳定的

B．快速排序是稳定的

C．堆排序是稳定的

D．都不稳定

(24) A．快速排序

B．堆排序

C．归并排序

D．基数排序

(25) A．N2-1

B．N-1

C．N2

D．N+1

(26) A．顺序文件

B．索引文件

C．散列文件

D．倒排文件

(27) A．3

B．6

C．15

D．12

Answer 1

正确答案：D,C,B,D,C
【解析】(23)、(24)空快速排序和堆排序是不稳定的，不符合要求；基数排序不能对实数排序；归并排序是稳定的，且可以对实数排序，所以答案为C。基数排序、归并排序是稳定的排序方法，所有时间复杂度为O(n2)的简单排序方法也是稳定的；快速排序、堆排序和Shell排序等时间性能较好的排序方法都是不稳定的。
(25)空：顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，就是顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。
除了文件本身外，另外建立一张逻辑记录和物理记录之间一一对应的索引表。这类包括文件数据区和索引表两大部分的文件称为索引文件。
散列文件指的是利用Hash法进行组织的文件，根据关键字的特点设计一种哈希函数和冲突处理的方法将记录散列到存储设备上。
多关键字文件的特点是，在对文件进行检索操作时，不仅仅对主关键词进行简单询问，还经常需要对次关键字进行其他类型的询问检索。常见的有多重表文件、倒排文件。
(27)空：5+4+3+2+1=15。