数据结构第九章排序习题及答案.doc

(完整版)数据结构第九章排序习题及答案习题九 排序一、单项选择题1下列内部排序算法中: A快速排序 B.直接插入排序 C。 二路归并排序 D。 简单选择排序 E。 起泡排序 F。 堆排序(1) 其比较次数与序列初态无关的算法是（ ) (2）不稳定的排序算法是（ ）（3)在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序,kn）的情况下,排序效率最高的算法是（ )（4）排序的平均时间复杂度为O（nlogn）的算法是（ )为O（nn)的算法是（ ）2比较次数与排序的初始状态无关的排序方法是( ）。A直接插入排序 B起泡排序 C快速排序 D简单选择排序3对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4) 15 21 25 47 84 则采用的排序是 （ ）。 A。 选择 B. 冒泡 C。 快速 D. 插入4下列排序算法中（ ）排序在一趟结束后不一定能选出一个元素放在其最终位置上。A. 选择 B. 冒泡 C。 归并 D. 堆5一组记录的关键码为(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）6下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序。 A 冒泡 B。 希尔 C。 快速 D. 堆 7。 就平均性能而言，目前最好的内排序方法是（ ）排序法.A。 冒泡 B. 希尔插入 C. 交换 D。 快速 8. 下列排序算法中，占用辅助空间最多的是：( ) A。 归并排序 B。 快速排序 C。 希尔排序 D。 堆排序9。 若用冒泡排序方法对序列10,14，26,29，41，52从大到小排序,需进行 （ ）次比较. A. 3 B. 10 C. 15 D. 25 10. 快速排序方法在（ )情况下最不利于发挥其长处。 A。 要排序的数据量太大 B. 要排序的数据中含有多个相同值C。 要排序的数据个数为奇数 D。 要排序的数据已基本有序11下列四个序列中，哪一个是堆（ )。A。 75，65，30，15，25，45，20，10 B. 75,65,45,10，30,25,20,15C。 75,45,65，30,15,25，20，10 D. 75,45，65，10，25，30，20,1512。 有一组数据（15，9,7,8，20,-1,7，4），用堆排序的筛选方法建立的初始堆为 ( ）A1,4，8,9，20，7,15，7 B-1，7,15，7，4,8,20，9C-1，4,7,8,20，15，7,9 DA,B，C均不对。二、填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序,这些记录的相对次序仍然保持不变，则称这种排序方法是_的，否则称为_的。2。按照排序过程涉及的存储设备的不同，排序可分为_排序和_排序。3直接插入排序用监视哨的作用是_。4对n个记录的表r1.。n进行简单选择排序，所需进行的关键字间的比较次数为_.5下面的c函数实现对链表head进行选择排序的算法，排序完毕,链表中的结点按结点值从小到大链接.请在空框处填上适当内容，每个空框只填一个语句或一个表达式：include link=head; head=p；while（p-link!=null） q=p-link； r=p； while （(1）_) if （q-linkdatar-linkdata) r=q； q=qlink; if (（2）_) s=r-link; r-link=s-link; slink= （3)_）; （(4）_); (（5）_) ; p=head； head=headlink; free(p）； return(head)； 6下面的排序算法的思想是：第一趟比较将最小的元素放在r1中，最大的元素放在rn中，第二趟比较将次小的放在r2中,将次大的放在rn-1中，依次下去，直到待排序列为递增序。（注：-）代表两个变量的数据交换）.void sort（SqList r，int n) i=1;while（(1)_) min=max=1；for （j=i+1；(2）_ ;+j) if(（3)_) min=j； else if(rj。keyrmax.key) max=j； if（(4）_） rmin - rj；if（max！=n-i+1)if （(5)_) rmin rni+1； else (6）_)； i+;/sort 7下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将ai和ai+1进行比较，第二趟对所有偶数的i，将ai和ai+1进行比较,每次比较时若aiai+1,将二者交换;以后重复上述二趟过程,直至整个数组有序.void oesort （int an）int flag,i,t; do flag=0；for（i=1；iai+1) flag=(4)_；t=ai+1; ai+1=ai; ai=t； while （5)_； 第九章 排序一、单项选择题1（1) DC （2)ADF （3）B (4）ACF BDE 2D3A4C5C6C7. D8. A9。 C10。 D11C12。 C二、填空题1。稳定、不稳定2.内部、外部3免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4n(n1）/25题中为操作方便，先增加头结点(最后删除),p指向无序区的前一记录，r指向最小值结点的前驱,一趟排序结束，无序区第一个记录与r所指结点的后继交换指针.(1)q-link！=NULL (2）r！=p （3）p-link （4）p-link=s (5)p=plink6.（1）in-i+1 (2）j=n-i+1 （3)rj。keyrn-i+17（1）1 (2）ai=t （3)（i=2;i=n；i+=2) (4）1 （5)flag