《数据结构》课件第8章 (2).ppt

13．下列四个序列中，堆是()。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，10D.?75，45，65，10，25，30，20，1514．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是()。A．N B．2N-1 C．2N D．N-115．排序的趟数与记录序列的初始状态有关的排序方法是()。A．直接插入排序 B.简单选择排序C.冒泡排序 D.快速排序三、问答题1．什么是内部排序？什么是外部排序？什么是稳定排序？什么是不稳定排序？2．请叙述简单选择排序和堆排序的区别。3．一个堆可以表示为一棵完全二叉树。请叙述堆与二叉排序树的区别。4．请叙述直接插入排序、冒泡排序和简单选择排序的过程。5．在使用非递归方法实现快速排序时，通常要利用一个栈记忆排序区间的两个端点。那么能否用队列来代替这个栈？为什么？6．请叙述希尔排序和二路归并排序的过程。四、应用题1．已知序列(35，78，12，26，90，44，66，58)，请写出对此序列采用直接插入排序方法、希尔排序方法进行升序排序时各趟的结果。2．已知序列(23，76，16，25，93，46，69，55)，请写出对此序列采用冒泡排序方法进行升序排序时各趟的结果。3．已知序列(37，87，19，26，99，47，61，59)，请写出对此序列采用快速排序方法进行升序排序时各趟的结果。4．已知序列(30，77，16，26，98，41，67，58)，请写出对此序列采用简单选择排序方法进行升序排序时各趟的结果。5．已知序列(47，83，29，26，19，57，23，69)，请写出对此序列采用堆排序方法进行升序排序时各趟所对应的堆。6．已知序列(47，83，10，26，19，88，23，96)，请写出对此序列采用二路归并排序方法进行升序排序时各趟的结果。实训指导

一、排序方法实现【实训目的】(1)理解和掌握各种排序方法的思想，尤其是直接插入排序、希尔排序、冒泡排序、快速排序和二路归并排序。(2)利用以上排序方法实现对记录的排序。【实训内容】(1)按提示输入10个记录的关键字(即整形数据)。(2)程序达到的功能要求对输入的10个记录按照关键字的大小进行排序，并且将其输出。(3)举例说明如下：10个记录的关键字输入为：92163622582511458210个记录的关键字输出为：291116222536455882【实现提示】将输入的10个记录从小到大排序，记录数组从下标为1的单元来存放。利用以上排序方法实现记录从小到大排序，记录从数组的1单元来存放，并且输出。【实现过程】#includestdio.h#defineMaxsize100//参见结构8-1typedefintDatatype;typedefstruct{Datatypekey;}Recnode;Recnoder[Maxsize];voidinsertsort(Recnoder[],intn);//函数说明，参见算法8-1voidshellsort(Recnoder[],intn); //函数说明，参见算法8-2voidbubblesort(Recnoder[],intn); //函数说明，参见算法8-3intPartition(Recnode*r,intlow,inthigh); //参见算法8-4voidquicksort(Recnode*r,intstart,intend); //参见算法8-4voidselectsort(Recnoder[],intn); //参见算法8-5voidmerge(Recnode*r,intlow,intm,inthigh);//参见算法8-7voidonemerge(Recnode*r,intlenth,intn);//参见算法8-8voidmergesort(Recnode*r,intn); //参见算法8-9voidmain(){inti; intn=10; //记录数组中元素的个数，下标从1