云南开放大学数据结构网上作业7

一、单项选择题(共25题,共100分)
第1 题（4分）：
稳定的排序算法指（    ）。
A．经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B．经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C．排序算法的性能与被排序元素的个数关系不大
D．排序算法的性能与被排序元素的个数关系密切
正确答案: A
第2 题（4分）：
以下排序方法中，（   ）不需要进行关键字的比较。
A．快速排序     B．归并排序    C．基数排序   D．堆排序
正确答案: C
第3 题（4分）：
以下排序方法中，稳定的排序方式是（   ）。
A．快速排序     B．希尔排序    C．基数排序   D．堆排序
正确答案: C
第4 题（4分）：
将1000个英文单词进行排序，采用（     ）方法最好。
A．快速排序     B．直接插入排序    C．堆排序   D．基数排序
正确答案: D
第5 题（4分）：
外排序是指（     ）。
A．在外存上进行的排序方法
B．不需要使用内存的排序方法
C．数据很大，需要人工干预的排序方法
D. 排序前后数据在外存，排序时数据调入内存的排序方法
正确答案: D
第6 题（4分）：
在待排序的元素序列基本有序的前提下，效率最高的排序方法是（   ）。
A.直接插入排序    B．简单选择排序   C．快速排序   D．归并排序
正确答案: A
第7 题（4分）：
内部排序算法的稳定性是指(      )。
A．该排序算法不允许有相同的关键字记录
B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法
D．以上都不对
正确答案: D
第8 题（4分）：
下面给出的四种排序算法中，(    )是不稳定的排序。
A．插入排序       B．堆排序         C．二路归并排序      D．冒泡排序
正确答案: B
第9 题（4分）：
在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（    ）。
A．直接插入排序  B．冒泡排序      C．快速排序     D．直接选择排序
正确答案: D
第10 题（4分）：
关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(    )的两趟排序后的结果。
A．选择排序       B.冒泡排序          C.插入排序       D.堆排序
正确答案: C
第11 题（4分）：
下列排序方法中，(      )所需的辅助空间最大。
A．选择排序      B．希尔排序      C．快速排序     D．归并排序
正确答案: D
第12 题（4分）：
一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（   ）。
A．(38,40,46,56,79,84)               B．(40,38,46,79,56,84)
C．(40,38,46,56,79,84)               D．(40,38,46,84,56,79)
正确答案: C
第13 题（4分）：
在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较(      )次。
A. 2              B. 4              C. 6               D. 8
正确答案: A
第14 题（4分）：
从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为(      )。
A. 希尔排序       B. 直接选择排序   C. 冒泡排序       D. 快速排序
正确答案: B
第15 题（4分）：
当待排序序列基本有序时，以下排序方法中，( )最不利于其优势的发挥。
A. 直接选择排序   B. 快速排序      C.冒泡排序        D.直接插入排序
正确答案: B
第16 题（4分）：
对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（     ）。
A.原序列是升序排列             B.原序列是降序排列
C.对序列只进行了2趟冒泡       D. 对序列只进行了3趟冒泡
正确答案: D
第17 题（4分）：
对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（     ）次元素间的比较。
A．j     B．j-1 C．n-j D．n-j-1
正确答案: C
第18 题（4分）：
对n个元素进行冒泡排序若某趟冒泡中只进行了（      ）次元素间的交换，则表明序列已经排好序。
A．1        B．2     C．0         D．n-1
正确答案: C
第19 题（4分）：
排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（      ）排序。
A．归并        B．插入       C．选择     D．快速
正确答案: C
第20 题（4分）：
排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是(     )。
A．直接插入排序     B．快速排序    C．冒泡排序    D．选择排序
正确答案: A
第21 题（4分）：
排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（   ）。
A．冒泡      B．直接插入     C．选择排序     D．折半插入
正确答案: D
第22 题（4分）：
一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（     ）。
A．31，29，37，85，47，70
B．29，31，37，47，70，85
C．31，29，37，70，47，85
D．31，29，37，47，70，85
正确答案: D
第23 题（4分）：
以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（     ）。
A．直接选择          B．冒泡          C．直接插入      D．折半插入
正确答案: A
第24 题（4分）：
在对一组元素（64，48，106，33，25，82，70，55，93）进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行（      ）次元素间的比较（指由小到大排序）。
A．6          B．2         C．3           D．4
正确答案: C
第25 题（4分）：
在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（    ）。
A．冒泡          B．选择        C．直接插入         D．折半插入
正确答案: D