数据的结构单元练习10.doc

单元测验一判断题如下各题，正确的请在前面的括号内打；错误的打 1如果某种排序算法不稳定，如此该排序方法就没有实用价值。2希尔排序是不稳定的排序。3冒泡排序是不稳定的排序。4对n个记录的进展快速排序，所需要的平均时间是O(nlog2n)。5堆排序所需的时间与待排序的记录个数无关。6当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。7快速排序在任何情况下都比其它排序方法速度快。8对快速排序来说，初始序列为正序或反序都是最坏情况。9采用归并排序可以实现外排序。10采用希尔方法排序时，假如关键字的排列杂乱无序，如此效率最高。二填空题（1） 大多数排序算法都有两个根本的操作： 比拟 和移动。（2） 评价排序算法优劣的主要标准是 时间复杂度和算法所需的附加空间。（3） 根据被处理的数据在计算机中使用不同的存储设备，排序可分为： 内排序和外排序。（4） 外排序是指在排序过程中，数据的主要局部存放在计算机的 外存 中。（5） 对n个关键字进展冒泡排序，其可能的最小比拟次数为： n-1 次。（6） 在最坏情况下，在第i趟直接插入排序中，要进展 i-1 次关键字的比拟。（7） 对n个关键字进展冒泡排序，时间复杂度为 O(n2) 。（8） 快速排序在最坏情况下的时间复杂度是 O(n2)。（9） 对于n个记录的集合进展归并排序，所需要的平均时间为：O(log2n)。（10） 对于n个记录的集合进展归并排序，所需要的附加空间是 O(n) 。（11） 假如原始数据接近无序，如此选用 快速排序 最好。（12） 在排序前，关键字值相等的不同记录，排序后相对位置保持 不变 的排序方法，称为稳定排序方法。（13） 在插入排序和选择排序中，假如初始数据根本正序，如此选用 插入排序 较好。（14） 当增量为1时，该趟希尔排序与直接插入排序根本一致。（15） 第一趟排序后，序列中键值最大的记录交换到最后的排序算法是 冒泡排序。（16） 依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。（17） 在插入排序、选择排序和归并排序中，排序是不稳定的为： 选择排序。（18） 在对一组记录54，38，96，23，15，72，60，45，83进展直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比拟 3 次。（19） 两个序列分别为： L1=25，57，48，37，92，86，12，33 L2=25，37，33，12，48，57，86，92。 用冒泡排序法对L1和L2进展排序，交换次数较少的是序列： L2 。20对一组记录54，35，96，21，12，72，60，44，80进展直接选择排序时，第四次选择和交换后，未排序记录是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排序方法中，从无序序列中选择关键字最小的记录，将其与无序区初始为空的第一个记录交换的排序方法，称为 ( 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 个元素开始，插入到前边适当位置的排序方法。 A1 B2 C3 Dn10堆的形状是一棵 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 。 A希尔排序 B插入排序 C冒泡排序 D选择排序15对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 B 。AO(n) BO(n2) CO(nlog2n) DO(n3)16冒泡排序的方法对n个数据进展排序，第一趟排序共需要比拟 C 次。 A1 B2 Cn-1 Dn17对个不同的排序码进展冒泡递增排序，在如下 B 情况比拟的次数最多。A从小到大排列好的 B从大到小排列好的 C 元素无序 D元素根本有序18用直接插入排序法对下面的四个序列进展由小到大的排序，元素比拟次数最少的是 B 。 A，94，32，40，90，80，46，21，69 B21，32，46，40，80，69，90，94 C32，40，21，46，69，94，90，80 D90，69，80，46，21，32，94，4019一组记录的排序码为(25，48，16，35，79，82，23，40)，其中含有4个长度为2的有序表，按归并排序的方法对该序列进展一趟归并后的结果为： A 。 A，16 25 35 48 23 40 79 82 36 72 B16 25 35 48 79 82 23 36 40 72 C16 25 48 35 79 82 23 36 40 72 D16 25 35 48 79 23 36 40 72 8220一个数据序列的关键字为：46，79，56，38，40，84，采用快速排序，并以第一个数为基准得到第一次划分的结果为： C A38，40，46，56，79，84B40，38，46，79，56，84 C40，38，46，56，79，84D40，38，46，79，56，84四排序过程分析1 数据序列10，8，18，15，7，16，写出采用直接插入算法排序时，每一趟排序的结果。解： 10 8 18 15 7 16第一趟完毕时结果： 810 1815 7 16第二趟完毕时结果： 810 1815 7 16第三趟完毕时结果： 8 10 15 18 7 16第四趟完毕时结果： 7 8 10 15 18 16第五趟完毕时结果： 7 8 10 15 16 182 数据序列18，17，60，40，07，32，73，65，写出采用直接插入算法排序时，每一趟排序的结果。解： 18 17 60 40 07 32 73 65第一趟完毕时结果： 17 1860 40 07 32 73 65第二趟完毕时结果： 17 1860 40 07 32 73 65第三趟完毕时结果： 17 18 40 60 07 32 73 65第四趟完毕时结果： 07 17 18 40 60 32 73 65第五趟完毕时结果： 07 17 1832 40 60 73 65第六趟完毕时结果： 07 17 1832 40 60 73 65第七趟完毕时结果： 07 17 1832 40 60 65 73 3. 数据序列17，18，60，40，7，32，73，65，85请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。解： 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 7 18 32 40 60 65第四趟排序结果： 7 17 18 32 40 60第五趟排序结果： 7 17 18 32 40第五趟排序过程中已无记录交换，排序完毕。4 数据序列80，18，9，90，27，75，42，69，34请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。解：80 18 09 90 27 75 42 69 34第一趟排序结果： 18 09 80 27 75 42 69 34 90第二趟排序结果：09 18 27 75 42 69 34 80第三趟排序结果：09 18 27 42 69 34 75第四趟排序结果：09 18 27 42 3469第五趟排序结果：09 18 27 34 40第六趟排序结果：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=4 6 12 4 3 8 18 9 15 10d=2 4 3 6 12 8 15 9 18 10d=1 3 4 6 8 9 10 12 15 18 6 数据序列12，02，16，30，28，10，17，20，06，18，写出希尔排序每一趟排序的结果。设d=5、2、1解： 12 02 16 30 28 10 17 20 06 18d=5 10 02 16 06 18 12 17 20 30 28d=2 12 02 16 06 17 12 18 20 30 28d=1 02 06 10 12 16 17 18 20 28 307 数据序列10，18，4，3，6，12，9，15，写出二路归并排序的每一趟排序结果。10 18 4 3 6 12 9 15 10 18 3 4 6 12 9 15 第一趟排序结果 3 4 10 18 6 9 12 15 第二趟排序结果 3 4 6 9 10 12 15 18 第三趟排序结果8 数据序列53，36，48，36，60，7，18，41，写出采用简单项选择择排序的每一趟排序结果。解： 53 36 48 36 60 7 18 417 36 48 36 60 53 18 417 18 48 36 60 53 36 417 18 36 48 60 53 36 417 18 36 36 60 53 48 417 18 36 36 41 53 48 607 18 36 36 41 48 53 607 18 36 36 41 48 53 607 18 36 36 41 48 53 60 9 数据序列10，1，15，18，7，15，试画出采用快速排序法，第一趟排序的结果。解 10 1 15 18 7 15 low high交换 7 1 15 18 10 15 low high交换第一趟排序结果： 7 1 10 18 15 15 low high10 数据序列10，1，15，18，7，15，试写出采用快速排序法，第一趟排序的结果。解：7 1 1018 15 15五二分插入排序程序填空void BInsSort( ) / 按递增序对R1R n 进展二分插入排序 int i, j, low, high, m; for (i=2;i<=n;i+)R0=Ri; / 设定R0为监视哨low=1;high=n ；while (low<=high) m=(low+high)/2 ;if(R0<Rm) high=m-1 ;else low=m+1; for(j=i-1;j>=high+1;j-)Rj+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=p; p=q;if(s=h)h=h->link;elseh=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->next;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<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) && (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，试画出采用快速排序法，第一趟排序的结果。解：45，10，40，20，15 50 80，602 数据序列82，40，66，13，84，36，96，57，39，80，61，14，写出二路归并排序的每一趟排序结果。解：8240 66 13 84 36 96 57 39 80 61 1440 82 13 66 36 84 57 96 39 80 14 61 第一趟排序结果13 40 66 82 36 57 84 96 14 39 61 80 第二趟排序结果13 36 40 57 66 82 84 96 14 39 61 80 第三趟排序结果13 14 36 39 40 57 61 66 80 82 84 96 第四趟排序结果3 数据序列40，63，11，84，35，93，58，39，15，写出采用简单项选择择排序的每一趟排序结果。解：40 63 11 84 35 93 58 39 1511 63 40 84 35 93 58 39 1511 1540 84 35 93 58 39 6311 15 3584 40 93 58 39 6311 15 35 3940 93 58 84 6311 15 35 39 4093 58 84 6311 15 35 39 40 5893 84 6311 15 35 39 40 58 6384 9311 15 35 39 40 58 63 849311 15 35 39 40 58 63 84 934 数据序列18，17，60，40，07，32，73，65，写出采用冒泡排序法每一趟排序的结果。解： 18 17 60 40 07 32 73 65第一趟完毕时结果： 17 18 40 07 32 60 65 73第二趟完毕时结果： 17 1807 32 40 60 65第三趟完毕时结果： 17 07 1832 4060第四趟完毕时结果： 07 17 1832 40第五趟完毕时结果： 07 17 1832已无交换，完毕。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=5 10 11 09 13 08 12 18 14 15 16d=2 08 11 09 12 10 13 15 14 18 16d=1 08 09 10 11 12 13 14 15 16 186 数据序列39，28，55，80，75，06，17，45，写出采用直接插入算法排序时，每一趟排序的结果。解： 39 28 55 80 75 06 17 45第一趟完毕时结果： 28 39 55 80 75 06 17 45第二趟完毕时结果： 28 39 55 80 75 06 17 45第三趟完毕时结果： 28 39 55 80 07 32 73 65第四趟完毕时结果： 07 28 39 55 80 32 73 65第五趟完毕时结果： 07 28 32 39 55 80 73 65第六趟完毕时结果： 07 28 32 39 55 73 80 65第七趟完毕时结果： 07 28 32 39 55 65 73 80程序填空1 设表的长度为L，试填空完成直接插入排序程序。voidinsertsort(int R )/ 按递增序对R1R n 进展直接插入排序 int i,j; for (i=2; i<=L;i+ )R0=Ri; / 设定R0为监视哨j=i-1 ； while (R0< Rj ) Rj+1=Rj ; j- ; Rj+1=R0; /插入第i个记录 2直接选择排序void selectsort ( ) / 按递增序对R1 Rn 进展直接选择排序 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; 3二分插入排序void BInsSort( ) / 按递增序对R1R n 进展二分插入排序 int i, j, low, high, m; for (i=2;i<=n;i+)R0=Ri; / 设定R0为监视哨low=1;high=n ；while (low<=high) m=(low+high)/2 ;if(R0<Rm) high=m-1 ;else low=m+1; for(j=i-1;j>=high+1;j-)Rj+1=R j ; /元素后移 Rhigh=R0; /插入算法设计题1设计一个函数修改冒泡排序过程以实现双向冒泡排序每一趟排序，通过相邻的关键字比拟，产生最小和最大的两个元素。解： void dbubble(SeqList r) int i,j,t,b; while(b) b=0; for(j=n-i+1;j>=i+1;j-) / 由底向上 if (rj.key<rj-1.key) b=1; t=rj; rj=rj-1; rj-1=t; for(j=i+1;j<n+i-1;j+) / 由上向底 if(rj.key>rj+1.key) b=1; t=rj; rj=rj+1; rj+1=t; i+; 2以单链表为存储结构，写一个直接选择排序算法。解：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=p; p=q; if(s=h)h=h->link;elseh=s;s->link=t;t=s;h=t;3设待排序的文件用单链表做存储结构，头指针为head，写出其选择排序算法。void select ( lklist head ) p=head;while ( p!=NULL ) s=p;q=p->next;while ( q!=NULL ) if ( q->key < s->key ) s=q;q=q->net; if ( s!=p ) t=p->key;p->key=s->key; s->key=t; p=p->next;