数据结构单元练习10

1、单元测验10一.判断题(下列各题，正确的请在前面的括号内打，；错误的打X )(义)(1)如果某种排序算法不稳定，则该排序方法就没有实用价值。(，)(2)希尔排序是不稳定的排序。(义)(3)冒泡排序是不稳定的排序。(，)(4)对n个记录的进行快速排序，所需要的平均时间是O(nlog 2n)。(义)(5)堆排序所需的时间与待排序的记录个数无关。(，)(6)当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复 杂度的主要因素。(义)(7)快速排序在 任何情况 下都比其它排序方法速度快。(，)(8)对快速排序来说，初始序列为正序或反序都是最坏情况。(，)(9)采用归并排序可以实

2、现外排序。(，)(10)采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。二.填空题(1)大多数排序算法都有两个基本的操作:比较 和移动。(2) 评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。(3) 根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序 和外排序。(4) 外排序是指在排序过程中，数据的主要部分存放在计算机的外存 中。(5) 对n个关键字进行冒泡排序，其可能的最小比较次数为：n-1 次。(6) 在最坏情况下，在第i趟直接插入排序中，要进行 上次关键字的比较。(7) 对n个关键字进行冒泡排序，时间复杂度为O(n 2)(8) 快速排序在最坏情况下的时间

3、复杂度是O(n 2)。O(log2n)O(n) 。不变的排序方法,称为稳插入排序 较好。(9) 对于n个记录的集合进行归并排序，所需要的平均时间为：(10) 对于n个记录的集合进行归并排序，所需要的附加空间是(11) 若原始数据接近无序，则选用快速排序最好。(12) 在排序前，关键字值相等的不同记录，排序后相对位置保持 定排序方法。(13)在插入排序和选择排序中，若初始数据基本正序，则选用(14)当增量为1时，该趟希尔排序与直接插入排序基本一致。(15)第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。(16)依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。(

4、17)在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。(18)在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时，当把第 7个记录60插入到有序表时，为寻找插入位置需比较工次。(19)两个序列分别为:L1=25 , 57, 48, 37, 92, 86, 12, 33L2=25 , 37, 33, 12, 48, 57, 86, 92。用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：L2 。(20)对一组记录(54, 35, 96, 21, 12, 72, 60, 44, 80)进行直接选择排序时，第四次选择和 交换后，

5、未排序记录是54 , 72, 60, 96, 80 。三.选择题(1)排序是根据(A )的大小重新安排各元素的顺序。A .关键字 B .数组 C .元素件 D .结点(2)评价排序算法好坏的标准主要是( D )。A.执行时间B.辅助空间C.算法本身的复杂度D.执行时间和所需的辅助空间(3)直接插入排序的方法是( B )的排序方法。A .不稳定 B .稳定 C .外部 D .选择(4)直接插入排序的方法要求被排序的数据( B )存储。A .必须链表B .必须顺序C.顺序或链表D .可以任意(5)排序方法中，从无序序列中选择关键字最小的记录，将其与无序区(初始为空)的第一个记录交换的排序方法，称为

6、 (D )。A .希尔排序 B.归并排序C.插入排序D.选择排序(6)每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做( C )。A.冒泡排序B .堆排序 C.快速排序D.归并排序(7)快速排序在(C )情况下最易发挥其长处。A.待排序的数据中含有多个相同的关键字B.待排序的数据已基本有序C.待排序的数据完全无序D .待排序的数据中最大值与最小值相差悬殊(8)下述几种排序方法中，要求内存量最大的是：( D )。A .插入排序B .选择排序C.快速排序D.归并排序(9)直接插入排序的方法是从第( B )个元素开

7、始，插入到前边适当位置的排序方法。A . 1B. 2 C. 3 D. n(10)堆的形状是一棵(C )。A.二叉排序树B .满二叉树C .完全二叉树D .平衡二叉树(11)内排序是指在排序的整个过程中，全部数据都在计算机的( A )中完成的排序。A .内存 B .外存 C .内存和外存D .寄存器(12)快速排序的方法是( A )的排序方法。A .不稳定 B .稳定 C .外部 D .选择(13)下列排序方法中，关键字比较次数与记录的初始排列次序无关的是(A )。A.选择排序B.希尔排序C.插入排序D.冒泡排序(14)下述几种排序方法中，平均时间复杂度最小的是( A )。B ）。A.希尔排序B

8、.插入排序C.冒泡排序D.选择排序(15)对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A. O(n).。(").O(nlog 2n).。.)(16)冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较(C )次。(17)对n个不同的排序码进行冒泡(递增)排序，在下列(A.从小到大排列好的 B.从大到小排列好的 C.元素无序)情况比较的次数最多。D .元素基本有序(18)用直接插入排序法对下面的四个序列进行由小到大的排序,元素比较次数最少的是(B )。A , 94, 32, 40, 90, 80, 46, 21, 69 B.21, 3246, 40, 80, 69,

9、90, 94C . 32, 40, 21, 46, 69, 94, 90, 80 D(19) 一组记录的排序码为(25, 48, 16, 35, 79按归并排序的方法对该序列进行一趟归并后的结果为：.90, 6980, 46, 21, 32, 94, 4082, 23, 40),其中含有4个长度为2的有序表,A , 16 25 35 48 23 40 79 82 36 72.16 25 35 48 79 82 23 36 40 72C . 16 25 48 35 79 82 23 36 40 72.16 25 35 48 79 23 36 40 72 82(20) 一个数据序列的关键字为：基准

10、得到第一次划分的结果为：(467956,38,40,84),采用快速排序，并以第一个数为A. ( 38, 40, 46567984)(403846, 79,56, 84).( 40, 38, 46567984)(403846, 79,56, 84)四.1 .解：排序过程分析已知数据序列101088,第一趟结束时结果: 第二趟结束时结果: 第三趟结束时结果: 第四趟结束时结果: 第五趟结束时结果:18 8 8 8 7 7181510101071815, 7161518151010151815152 .已知数据序列18, 17,60,4016,写出采用直接插入算法排序时,每一趟排序的结果。1616

11、16序的结果。解：181760 40181616180732,73, 65,写出采用直接插入算法排序时，每一趟排07 32 73 65第一趟结束时结果 第二趟结束时结果 第三趟结束时结果 第四趟结束时结果 第五趟结束时结果 第六趟结束时结果 第七趟结束时结果3 .已知数据序列1717170707070718 60 40 0718181717171760 40 07401818181817 , 18, 60,60 07403232326032327373656532327373656540 607340 60 73656540 60 65 7340, 7, 32, 73, 65, 85请写出采用

12、冒泡排序法对该序列作升序排序时每一趟的结果。解：17 18 60 40 7 32 73 65 85第一趟排序结果：17 18 40 7 32 60 65 73 85第二趟排序结果：17 18 7 32 40 60 65 73第三趟排序结果：17 71832406065口第四趟排序结果：7 1718324060第五趟排序结果：7 17183240J第五趟排序过程中已无记录交换，排序结束。4 . 已知数据序列80, 18, 9, 90, 27, 75, 42, 69, 34 请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。解：80 18 09 90 27 75 42 69 34第一趟排序结果

13、：1809802775426934 90|第二趟排序结果：0918277542693480第三趟排序结果：09 18 27 42 69 34 75 匚第四趟排序结果：091827423469第五趟排序结果：0918273440|第六趟排序结果：09 18 27 34第六趟排序过程中已无记录交换，排序结束。5 .已知数据序列10,18,4, 3, 6,12,9,15,8,写出希尔排序每一趟（设 d=4、2、1）排序的结果。解：10 18 4 3 6 12 9 15 8d=46 12 4 3 8 18 9 15 10d=24 3 6 12 8 15 9 18 10d=13 4 6 8 9 10 1

14、2 15 186 .已知数据序列12, 02, 16, 30, 28, 10, 17, 20, 06, 18,写出希尔排序每一趟排序的结果。（设 d=5、2、1）解： 12 02 16 30 28 10 17 20 06 18d=510021606181217203028I|I|J|Id=2 Illi12021606171218203028I I I I I I I I I Id=102 06 10 12 16 17 18 20 28 307 .已知数据序列10, 18, 4, 3, 6, 12, 9, 15,写出二路归并排序的每一趟排序结果。10 18 4 3 6 12 9 15I I I

15、I I I|10 18 3 4 6 12 9 15第一趟排序结果3 4 10 18 61215第二趟排序结果3 4 6 9 10121518第三趟排序结果8.解:已知数据序列53364836, 60, 718, 41,写出采用简单选择排序的每一趟排序结果。53 36 48 36 60 7 18 41(7)(7(7(7(7(7(7(736 4818)184836369.解10.解:7五.181818181836)36363636364836)36363636已知数据序列10 1 low7 1low101515第一趟排序结果:1,已知数据序列106060605353531836366041)535

16、341414115,48)4848485353)414141416060604818,15 high53 60 )7, 15,试画出采用快速排序法，第一趟排序的结果。交换¥ 10 15 *1 jhigh>T IIt交换7 1 10 18 15 15 high J .low1, 1518, 7, 15,试写出采用快速排序法，第一趟排序的结果。1 10 18 15 15二分插入排序程序填空void BInsSort()/按递增序对R1R n 进行二分插入排序 int i, j, low, high, m;for ( i=2; i<=n ; i+) R0=Ri;/设定R0为监视

17、哨low=1;high=while (low<=high)m=(low+high)/2 ;if ( R0<Rm)high=m-1 ;elselow=m+1; for (j=i-1;j>=high+1;j-)元素后移插入Rl+1= R j /Rhigh=R0;/ 六.算法题1 .以单链表为存储结构，写一个直接选择排序算法。 解： void selectsort(pointer h) pointer p,q,r,s,t;t=NULL; while(h) p=h; q=NULL;s=h; r=NULL; while (p) if (p->key<s->key) s

18、=p； p=q； if (s=h)h=h->link; else h=s;s->link=t; t=s; h=t; 2 .以单链表作为存储结构实现直接插入排序算法。 解： void InsertList(List head) Lnode *p, * pprev , q,*qprev, *current; if (!head)return;pprev=head;p=head->next;查找插入位置最大，无须插入while (p) q=head; qprev=NULL; while (q->key < p->key) / qprev=q; q=q->ne

19、xt; if (q= =p)/ p插在表头插在中间某个位置上初、终下标自右向左找非负 数/ 自左向右找负 数pprev=p; p=p->next; else current=p; p=p->next;pprev->next=p;current->next=q;if (q=head)/head=current;else/qprev->next=current;3设计一个算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的 关键字之前。解： void part (int a ) i=1;j=n;/while (i<j) while (i&

20、lt;j && aj>=0)/j-;while (i<j && ai<0) i+;if (i<j) t=ai;ai=aj;aj=t;i+;j-; 4设已排序的文件用单链表表示，再插入一个新记录，仍然按关键字从小到大的次序排序，试写出该算法。void insert(lklist head;datatype x)s=new ( node );s->key=x;s->next= NULL;if (head= =NULL)head=s;else p=head;q= NULL;while ( p! =NULL) && (

21、s->key > p->key ) q=p; p=p->next; if (q= =NULL) s->next=head; head=s; else if (p=NULL)q->next=s;else s->next=q->next; q->next=s; 排序过程分析1 .果。解:已知数据序列50,60,40, 20,80, 15, 10, 45,试画出采用快速排序法，第一趟排序的结2.45 , 10, 40已知数据序列20,1550 80，6082,40,66, 13,84, 36, 96, 57, 39, 80, 61, 14,写出二

22、路归并排序的每一趟排序结果。解：82 40 66 13 84 36 96 57 39 80 61 14结果。解：40 63 11 843593 58 394.解:(11)(11(11(11(11(11(11(11(1163 40 8415)15151515151515359315583940 8435)3535358439)3939353535393939已知数据序列18 ,18 17 6035404040)4040404017,9393939358)5858585893393984848458585860,63)636340,40 07 32 738484)15636363636393938

23、4 93)07, 32, 73, 65,写出采用冒泡排序法每一趟排序的结果。654082 1366 3684 5796 3980 1461A趟排序结果1340 6682 36578496 1439 6180第二趟排序结果1336 4057 66828496 1439 6180第三趟排序结果1314 3639 40576166 8082 8496第四趟排序结果3.已知数据序列40,63,11, 84，35,93, 58,39, 15,写出采用简单选择排序的每一趟排序第一趟结束时结果：17 18 40 07 32 60 65 73 匚第二趟结束时结果：17 18 07 32 40 60 65第三趟

24、结束时结果：1707183240601第四趟结束时结果：0717183240 U第五趟结束时结果：07171832已无交换，结束。5 .已知数据序列10 , 18, 14, 13, 16, 12, 11, 9, 15, 08,写出希尔排序每一趟排序的结果（设 d=5、 2、 1）。解： 10 18 14 13 16 12 11 09 15 08d=510 11 09 13 08 12 18 14 15 16d=208 110912101315141816口 IIII I IIId=108 09 10 11 12 13 14 15 16 186 .已知数据序列39, 28, 55, 80, 75

25、, 06, 17, 45,写出采用直接插入算法排序时，每一趟排 序的结果。解： 39第一趟结束时结果: 第二趟结束时结果: 第三趟结束时结果: 第四趟结束时结果: 第五趟结束时结果: 第六趟结束时结果: 第七趟结束时结果:2855 80 75 06 17 4528 39 55 80 75 0628 39 55 80 75 0617 4517 4528 39 55 80 07 32 73 6507 2839558032736507 2832395580736507 2832395573806507 28323955657380程序填空1 .设表的长度为L,试填空完成直接插入排序程序。void i

26、nsertsort(int R)/按递增序对R1R n 进行直接插入排序 int i,j;for ( i=2; i<=L ; i+ ) R0=Ri;/设定R0为监视哨j=i-1while (R0<_Rj)Rj+1=Rjj-;Rj+1=R0/插入第i个记录2.直接选择排序void selectsort ( )/ int i, j, k ；for (i=1;i<= n ;i+) k=i ；for (j=i+1 J<=n;j+)/if (Rj<Rk)k=j；if (! k=j ) R0=R i ；/Ri = Rk； Rk=R0；按递增序对R1 Rn进行直接选择排序选择选择关键字最小的记录交换关键字3.二分插入排序void BInsSort( )/ int i, j, low, high, m;for ( i=2; i<= n ; i+) R0=Ri；/low=1;high= n ;while (low