完整版数据结构排序

1、第八章排序：习题 习题 一、选择题1 .在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是.A.希尔排序B.冒泡排序C.插入排序D.选择排序2 .设有1000个无序的记录,希望用最快的速度挑选出其中前10个最大的记录,最好选用排序法.A.冒泡排序B.快速排序C.堆排序D.基数排序3 .在待排序的记录序列根本有序的前提下,效率最高的排序方法是.A.插入排序B.选择排序C.快速排序D.归并排序4 .不稳定的排序方法是指在排序中,关键字值相等的不同记录的前后相对位置.A.保持不变B.保持相反C.不定D.无关5 .内部排序是指在排序的整个过程中,全部数据都在计算机的中完成的排序.A.内存储

2、器B.外存储器C.内存储器和外存储器D.存放器6 .用冒泡排序的方法对n个数据进行排序,第一趟共比较对记录.A.1B.2 C.n-l D.n7 .直接插入排序的方法是从第个记录开始,插入前边适当位置的排序方法.A.1B.2C.3 D.n8 .用堆排序的方法对n个数据进行排序,首先将A.1B.2 C.n-l9 .归并排序的方法对D.nn个数据进行排序,首先将n个记录分成组.n个记录分成组,两两归并.A.1B.2 C.n-l D.n10 .直接插入排序的方法要求被排序的数据存储.D.二叉树A.必须是顺序B.必须是链表C.顺序或链表11 .冒泡排序的方法要求被排序的数据存储.A.必须是顺序B.必须是

3、链表C.顺序或链表D.二叉树12 .快速排序的方法要求被排序的数据存储.A.必须是顺序B.必须是链表C.顺序或链表D.二叉树13 .排序方法中,从未排序序列中依次取出记录与已排序序列初始时为空中的记 录进行比较,将其放入已排序序列的正确位置上的方法,称为 .A.希尔排序B.冒泡排序C.插入排序D.选择排序14 .每次把待排序的记录划分为左、右两个子序列,其中左序列中记录的关键字均小 于等于基准记录的关键字,右序列中记录的关键字均大于基准记录的关键字,那么此排序方法叫做.A.堆排序B.快速排序C.冒泡排序D. Shell排序15 .排序方法中,从未排序序列中挑选记录,并将其依次放入已排序序列初始

4、时为 空的一端的方法,称为.A.希尔排序B.归并排序C.插入排序D.选择排序16 .用某种排序方法对线性表 25, 84, 21 , 47, 15, 27, 68, 35, 20进行排序时,记 录序列的变化情况如下：(1) (25,84,21,47,15,27,68,35,40)(2) (20,15,21,25,47,27,68,35,84)(3) (15,20,21,25,35,27,47,68,84)(4) (15,20,21,25,27,35,47,68,84)那么所采用的排序方法是().A.选择排序B.希尔排序C.归并排序D.快速排序17 . 一组记录的关键字为 (25 , 50, 1

5、5, 35, 80, 85, 20, 40, 36, 70),其中含有 5个 长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果为().A. (15,25,35,50,20,40,80,85,36,70)B. (15,25,35,50,80,20,85,40,70,36)C. (15,25,50,35,80,85,20,36,40,70)D. (15,25,35,50,80,20,36,40,70,85)18 . n个记录的直接插入排序所需记录关键码的最大比较次数为().A. nlog2n B. n2/2 C.(n+2)(n_1)/2 D. n-l19 . n个记录的直接插入排序所需

6、白记录最小移动次数为().A. 2(n-l) B. n2/2C. (n+3)(n-2)/2 D. 2n20 .对以下关键字序列用快速排序法进行排序,()的情况排序最慢.A. 19,23,3,15,7,21,28B. 23,21,28,15,19,3,7C. 19,7,15,28,23,21,3D. 3,7,15,19,21,23,2821 .快速排序在()情况下最不利于发挥其长处,在()情况下最易发挥其长处.A.被排序的数据量很大B.被排序的数据已根本有序C.被排序的数据完全无序D.被排序的数据中最大的值与最小值相差不大E.要排序的数据中含有多个相同值22 , 一组记录的关键字为(45, 80

7、, 55, 40, 42, 85),那么利用快速排序的方法,以第一 个记录为基准得到一次划分结果是().A. (40,42,45,55,80,85).B. (42,40,45,80,55,85)C. (42,40,45,55,80,85) D. (42,40,45,85,55,80)23 .对n个记录的线性表进行快速排序,为减少算法的递归深度,以下表达正确的选项是().A.每次分区后,先处理较短的局部B.每次分区后,先处理较长的局部C.与算法每次分区后的处理顺序无关D.以上都不对24 .直接插入排序和冒泡排序的平均时间复杂度为(),假设初始数据有序(即正序),那么时间复杂度为().A.0(n)

8、B.0(log2n) C.0(nlog2n) D. O(n2)25 . 一组记录的关键字为(45, 80, 55, 40, 42, 85),那么利用堆排序的方法建立的初始 堆为().A. (80,45,55,40,42,85)B. (85,80,55,40,42,45)C. (85,80,55,45,42,40)D. 85,55,80,42,45,4026 .以下序列中是堆的有.A. 12,70,33,65,24,56,48,92,86,33B. 100,86,48,73,35,39,42,57,66,21C. 103,56,97,33,66,23,42,52,30,12D. 5,56,20,

9、23,40,38,29,61,35,7627 .设有1000个无序的记录,希望用最快的速度挑选出前20个最大的记录,最好选用算法.A.冒泡排序B.归并排序C.堆排序D.基数排序28 .以下排序算法中,算法会出现下面情况：在最后一趟结束之前,所有记录不在 其最终的位置上.A.堆排序B.冒泡排序C.快速排序D.插入排序29 .在含有n个记录的小根堆堆顶记录最小中,关键字最大的记录可能存储在位置上.A. Ln/21 B. Ln/2J-2C.1 D. Ln/2_1+330 .数据表 A中每个记录距其最终位置不远,那么采用 算法最省时间.A.堆排序B.插入排序C.直接选择排序D.快速排序31 .以下排序

10、算法中,某一趟轮结束后未必能选出一个记录放在其最终位置上的 是.A.堆排序B.冒泡排序C.直接插入排序D.快速排序32 .待排序的n个记录可分为n/k个组,每个组包含 k个记录,且任一组内的各记 录均分别大于前一组内的所有记录并小于后一组内的所有记录,假设采用基于比较的排序,其时间下界应为.A.Onlog 2 n B.0nlog2 kC.0 klog2 n D.0k log 2 k33 .假设要尽可能地完成对实数数组的排序,且要求排序是稳定的,那么应选 .A.快速排序B.堆排序C.归并排序D.基数排序34 .在含有n个记录的大根堆堆顶记录最大中,关键字最小的记录可能存储在位置上.A. Ln/2

11、1 B. Ln/2_1-1 C.1D. Ln/2_1 + 135 .对任意的7个关键字迸行排序,至少要进行次关键字之间的两两比较.A. 13B. 14C. 15D. 16二、填空题1 .排序是将一组任意排列的记录按 的值从小到大或从大到小重新排列成有序的 序列.2 .在排序前,关键字值相等的不同记录间的前后相对位置保持 的排序方法称为 稳定的排序方法.3 .在排序前,关键字值相等的不同记录间的前后相对位置 的排序方法称为不稳 定的排序方法.4 .外部排序是指在排序前被排序的全部数据都存储在计算机的 存储器中.5 .写出一种不稳定的排序方法的名称 .6 .在直接插入排序的方法中,当需要将第f个数

12、据插入时,此时前i-l个数据是的.7 .对一个根本有序的数据进行排序 排序方法运算次数最小.8 .在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时,当把 第7个记录60插入到有序表时,为寻找插入位置需比较次.9 .在利用快速排序方法对一组记录 (54, 38, 96, 23, 15, 72, 60, 45, 83)进行快速 排序时,递归调用而使用的栈所能到达最大深度为 ,共递归调用的次数为 ,其 中第二次递归调用是对 组进行快速排序.10 .在堆排序、快速排序和归并排序中,假设只从存储空间考虑,那么应首先选取方法, 其次选取,最后选取 方法

13、；假设只从排序结果的稳定性考虑,那么应选取 ;假设只从平均情况下排序最快考虑,那么应选取 ;假设只从最坏情况下排序最快并且要节省内存考虑,那么应选取 方法.11 .在堆排序和快速排序中,假设原始记录接近正序或反序,那么选用 ,假设原始记录 无序,那么最好选用.12 .在考虑如何选择排序中,假设初始数据根本正序,那么选用 ;假设初始数据根本 反序,那么选用.13 .对n个记录的序列进行冒泡排序时,最少的比较次数是 . 三、简做题1 .序列：17,18,60,40,7,32,73, 65,85),请给出采用冒泡排序法对该序列作升序排序时每一趟的结果.2 .序列：503, 87, 512, 61 ,

14、 908, 170, 897, 275, 653, 462),请给出采用快 速排序法对该序列作升序排序时每一趟的结果.3 .序列：503, 87, 512, 61 , 908, 170, 897, 275, 653, 462),请给出采用基 数排序法对该序列作升序排序时的每一趟的结果.4 .序列：503, 17, 512, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703, 941),请给出采用希尔排序法(Dl=8)对该序列作升序排序时每一趟的结果.5 .序列：70, 83, 100, 65, 10, 32, 7, 9),请给

15、出采用插入排序法对该序列 作升序排序时每一趟的结果.6 .序列：10, 18, 4, 3, 6, 12, 1, 9, 18, 8),请给出采用希尔排序法对该序 列作升序排序时每一趟的结果.四、算法设计题1 .编写一个对给定的环形双向链表进行简单插入排序的函数.2 .编写一个下沉式“冒泡函数.3 .编写一个对给定环形双向链表进行简单项选择择排序的函数.4 .如果把堆定义成：一种拟满树且每个结点的值既小于左孩子又小于右孩子,请写一 函数建立一个初始堆.5 .设计一个函数修改冒泡排序过程以实现双向冒泡排序.6 .奇偶转换排序如下所述：第一趟对所有奇数的 i,将ai和ai+l进行比较,第 二趟对所有偶

16、数的i,将ai和ai+1进行比较,每次比较时假设si>si+1,那么将两者交换,以后重复上述两趟过程交换进行,直至整个数组有序.(1)试问排序结束的条件是什么(2)编写结果实现上述排序过程的算法.7 .采用单链表作存储结构,编写一个采用选择排序方法进行升序排序的函数.8 .利用一维数组 A可以对n个整数进行排序.其中一种排序算法的处理思想是：将n个整数分别作为数组 A的n个记录的值,每次(即第 i次)从记录Ai-An中挑选出最小的一个记录Ak(i wkwn),然后将An与Ai换位.这样反复n次完成排序.编写实现上 述算法的函数第八章排序第8章排序一、选择题1.D2.C3.A4.C5.A6

17、.C78.B9.D10.A11.B12.A13.C14.B15.D16.D17.A18.C19.A20.D21. B,C22.C23.A24. D,A25.C,A26.B27. B,D 28.C29.D30.D31.C32.B33.C34.D35.C二、填空题1.关键字.2. /、艾.3.不能保持.4.夕卜.5 .快速排序、希尔排序和堆排序.6 .后序.7.冒泡.8. 3 .9.24 (23, 38, 15).10.堆排序,快速排序,归并排序,归并排序,快速排序,堆排序.B11.堆排序快速排序.12.插入排序选择排序.13.n-l .三、简做题1 .采用冒泡排序法排序的各趟的结果如下：初始：1

18、7, 18, 60, 40,7, 32, 73, 65, 85l 趟：17, 18, 40,7,32, 60, 65, 73, 852 趟：17,18,7,32, 40, 60, 65, 73, 853 趟：17,7,18, 32, 40, 60, 65, 73, 854 趟：7, 17, 18, 32, 40, 60, 65, 73, 855 趟：7, 17, 18, 32, 40, 60, 65, 73, 856 5趟无元素交换,那么排序结束.7 .采用快速排序法排序的各趟的结果如下：初始：503, 87, 512, 61,908, 170, 897, 275, 653, 462l 趟：4

19、62, 87, 275, 61,170 503 897, 908, 653, 5122 趟：170,87,275,61 462,503 897,908,653,5128 趟：61,87 170 275 462,503897,908,653,5129 趟：61 87 170 275 462,503 897,908,653,51210 趟：61,87,170 275462, 503 897, 908, 653, 51211 趟：61,87, 170, 275, 462,503 897, 908, 653, 51212 趟：61,87,170,275,462, 503 512, 653 897908

20、13 趟：61,87,170,275,462, 503, 512 653 89790814 趟：61,87,170,275,462, 503, 512, 653, 89790815 趟：61,87, 170, 275, 462, 503, 512, 653, 897, 9083.采用基数排序法排序的各趟结果如下：初始：503, 87, 512, 61,908, 170, 897, 275, 653, 4621 趟(按个位排序)：170, 61, 512, 462, 503, 653, 275, 87, 897, 9082 趟(按十位排序)：503, 908, 512, 653, 61,462,

21、 170, 275, 87, 8973 趟(按百位排序)：61, 87, 170, 275, 462, 503, 512, 653, 897, 9084.采用希尔排序的各趟结果如下：初始：503, 17, 512, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703,941 趟(D1=8): 426, 17, 509, 612, 170, 765, 275, 94, 503, 154, 512, 908, 677, 897, 703, 6532 趟(D2=4): 170, 17, 275, 94, 426, 154, 509,

22、612, 503, 765, 512, 653, 677, 897,703, 9083 趟(D3=2): 170, 17, 275, 94, 426, 154, 503, 612, 509, 653, 512, 765, 677, 897,703, 9084 趟(D4=1): 17, 94, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765,897, 9085 .采用插入排序的各趟结果如下：初始：(70), 83, 100, 65, 10, 32,7, 9l 趟：(70, 83), 100, 65, 10, 32,7,92 趟

23、：(70, 83, 100), 65, 10, 32,7,93 趟：(65, 70, 83, 100), 10, 32,7,94 趟：(10, 65, 70, 83, 100), 32,7,95 趟：(10, 32, 65, 70, 83, 100),7,96 趟：(7, 10, 32, 65, 70, 83, 100),97 趟：(7,9,10, 32, 65, 70, 83, 100)8 .采用希尔排序的各趟结果如下：初始:10,18,4 , 3, 6, 12,1 , 9, 15,8for (i=0; i<10; i十+)insert (head, i);return head;vo

24、id output (pnode h) pnode p=h;p=p->rlink ;printf ( "%d", p->data); while (p->rlink!=h);printf "n'n");void sort_insert (pnode head)pnode pl, p2, p3, p4;int temp;pl=head->rlink;while (pl->rlink ! =head) pl=pl->rlink;printf ("current plis %dn",pl->

25、data);p2=head->rlink;while (p2 ! =pl) if <p2->data<pl->data) p2=p2 ->rlink; else break;printf("pl should be in the front of %dn",p2->data);pl->llink->rlink-.pl->rlink;pl->rlink->llink=pl->llink; /* output (head) ;*/ p3=pl;pl=pl->llink;p3->rlink=

26、p2 ;p3->llink=p2->llink;p3->llink->rlink=p3;p2->llink=p3, ;main ()pnode th=init ();printf ("Before sort : n");output (lh) ;sort insert (lh);printf( "After sort :n");output (lh);getch();2 .# define MAX 100void main()int dMAX;int s , j , t, n;printf ("How many n

27、odes? n");scanf( "ood", &n);/*接收输入结点值,放置在数组d中*/for(s=O;s<n;s+)printf ("Input No ood valuen", s+l);scanf( "%d, &ds); /*冒泡排序*/for(S=O;s<n;s+) for (j=0;j<ns 1;j+)/+从前往后比较,将最大的值放在后面*/if(dj>dj+1)/*比较相邻接点的值*/ft=dj+1;dj+1=dj;dj=t; /*输出排序后的结点序列*/for(s=O; s&l

28、t;n;s+) printf("t%d",ds);printf(" n ");)3 ./*标准文本模板*/#include "Stdio .h"#include "Conio . h" struct _node int data;structnode *llink;structnode *rlink;);typedef struct node node.typedef node*, pnode; insert (pnode h, int n) pnode i , head,pnew; head=h;pnew= (p

29、node) malloc( sizeof (node);if (pnew=NULL) printf( "Memory allocate error!");exit (1);) pnew->data=n; pnew->rlink-head->rlink; head->rlink=pnew; pnew->llink=head;pnew->rlink->llink=pnew;) pnode init () int i;pnode head;head= (pnode) malloc ( sizeof (node) ;if (head=NUL

30、L)printf ( "Memory allocate error !");exit (1) ;head->rlink=head;head->llink=head;head->data=999;for (i=0; i<10; i+) insert (head, i) ; return head;void output (pnode h) pnode p=h;do p=p->rlink ;printf ( "%d", p->data); while (p->rlink!=h);printf ( " nn&

31、quot;);void sort select (pnode head)pnode pl, p2, min;int temp;pl=head->rlink; while (pl->rlink ! =head) min=pl; p2=pl; while (p2->rlink ! =head) if (p2->data<min->data) min=p2 ;p2=p2->rlink; /*find min*/ temp=min->data;/* insert min to right position */min->data=pl->da

32、ta;pl->data=temp; pl=pl->rlink; ;main () pnode th=init ();printf ("Before sort : n");output (lh) ;sort select (lh) ;printf ("After sort : n");output (lh) ; getch () ; 4. #include "Stdio.h"#include "Conio.h"void dui_format (int *d, int n) int s,t,q;s= (n-

33、l) /2; while (s>=0)while ( q=2*s+l) <n) s=q;elsebreak; d (q-l) /2 =t;s-； ) void out_heap(int* d,int n) ( int i;printf ( "nn").main () (intdata10=f 3,6,8,4,2,1,7,9,5,10);out_heap (data, 10);/*堆原始数据 */duiformat (data, 10);out_heap (data, 10);/*初始化完成后的堆(以验证)*/getch();5./*双向起泡排序是每一趟通过每两个

34、相邻的关键字进行比较, 产生最小和最大的元素.*/#include " Stdio . h "#include "Conio . h" void sort (int *d, int n) int i , j , temp;for (i=O; i<n;i+) for (j=0; j<n-i-l; j+) if(dj>dj+1) temp=dj;dj=dj+1;d j+l =temp; void output (int *d, int n) int i;for (i=O;i<n;i+) printf( "%d 一,di);

35、printf( " nn"); main() int data 10=3,36,8,43, 19,1,7,9,5,10); clrscr();output (data, 10);sort (data, 10);output (data, 10); getch(); 6 . #include<stdlib . h> void oesort (int a,int n)int i , flag;int tdo flag=0;for (i=l; i<n-l; i=i+2)if(ai>ai+1)flag=1;t=ai+1;ai+1=ai;ai=t;for (i

36、=0; i<n-l; i=i+2)printf ( "n");for (i=0; i<10; i+) getch ();while (flag! =0);main () int i;int n=10;int A10=1,32, 45, 78, 56, 98, 95, 4, 5, 6;printf (" 排序前：");for (i=0; i<10; i+)printf ( "%dt", A i);oesort (A, n);printf ("t 排序后:");for (i=0; i<10; i

37、+)printf ( "%dt", A i); getch ();7. #include " stdio . h"#include "stdlib.h"struct nodeint key;struct node *link;typedef struct _node node;typedef node; * pnode;insert (pnode h, int n)pnode p,pnew;p=h;pnew= (pnode) malloc ( sizeof (node » ;if (pnew=NULL)printf ( "Memory a