中南大学数据结构与算法第10章内部排序课后作业答案

第10章内部排序习题练习答案1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

(1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序(5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。

答：(1)直接插入排序:(方括号表示无序区)初始态: 265[301 751 129 937 863 742 694 076 438]第一趟：265 301[751 129 937 863 742 694 076 438]第二趟：265 301 751[129 937 863 742 694 076 438]第三趟：129 265 301 751[937 863 742 694 076 438]第四趟：129 265 301 751 937[863 742 694 076 438]第五趟：129 265 301 751 863 937[742 694 076 438]第六趟：129 265 301 742 751 863 937[694 076 438]第七趟：129 265 301 694 742 751 863 937[076 438]第八趟：076 129 265 301 694 742 751 863 937[438]第九趟：076 129 265 301 438 694 742 751 863 937(2)希尔排序(增量为5，3，1)初始态: 265 301 751 129 937 863 742 694 076 438第一趟：265 301 694 076 438 863 742 751 129 937第二趟：076 301 129 265 438 694 742 751 863 937第三趟：076 129 265 301 438 694 742 751 863 937(3)冒泡排序(方括号为无序区)初始态[265 301 751 129 937 863 742 694 076 438]第一趟：076 [265 301 751 129 937 863 742 694 438]第二趟：076 129 [265 301 751 438 937 863 742 694]第三趟：076 129 265 [301 438 694 751 937 863 742]第四趟：076 129 265 301 [438 694 742 751 937 863]第五趟：076 129 265 301 438 [694 742 751 863 937]第六趟：076 129 265 301 438 694 742 751 863 937(4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）初始态：[265 301 751 129 937 863 742 694 076 438]第二层：[076 129] 265 [751 937 863 742 694 301 438] 第三层：076 [129] 265 [438 301 694 742] 751 [863 937] 第四层：076 129 265 [301] 438 [694 742] 751 863 [937] 第五层：076 129 265 301 438 694 [742] 751 863 937第六层：076 129 265 301 438 694 742 751 863 937 (5)直接选择排序：(方括号为无序区)初始态[265 301 751 129 937 863 742 694 076 438]第一趟：076 [301 751 129 937 863 742 694 265 438]第二趟：076 129 [751 301 937 863 742 694 265 438]第三趟：076 129 265[ 301 937 863 742 694 751 438]第四趟：076 129 265 301 [937 863 742 694 751 438]第五趟：076 129 265 301 438 [863 742 694 751 937]第六趟：076 129 265 301 438 694 [742 751 863 937]第七趟：076 129 265 301 438 694 742 [751 863 937]第八趟：076 129 265 301 438 694 742 751 [937 863]第九趟：076 129 265 301 438 694 742 751 863 937(6)堆排序：（通过画二叉树可以一步步得出排序结果）初始态[265 301 751 129 937 863 742 694 076 438]建立初始堆：[937 694 863 265 438 751 742 129 075 301]第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937第二次排序重建堆：[751 694 742 265 438 301 075 129] 863 937第三次排序重建堆：[742 694 301 265 438 129 075] 751 863 937第四次排序重建堆：[694 438 301 265 075 129] 742 751 863 937第五次排序重建堆：[438 265 301 129 075] 694 742 751 863 937第六次排序重建堆：[301 265 075 129] 438 694 742 751 863 937第七次排序重建堆：[265 129 075] 301 438 694 742 751 863 937第八次排序重建堆：[129 075]265 301 438 694 742 751 863 937第九次排序重建堆：075 129 265 301 438 694 742 751 863 937(7)归并排序（为了表示方便，采用自底向上的归并，方括号为有序区）初始态：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]第二趟：[129 265 301 751] [694 742 863 937] [076 438]第三趟：[129 265 301 694 742 751 863 937] [076 438]第四趟：[076 129 265 301 438 694 742 751 863 937](8)基数排序（方括号内表示一个箱子共有10个箱子，箱号从0到9）初始态：265 301 751 129 937 863 742 694 076 438第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的，现举实例如下：以带*号的表示区别。

第10章内部排序答案一、填空题1. 大多数排序算法都有两个基本的操作：比较（两个关键字的大小）和移动（记录或改变指向记录的指针）。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较3次。

(可约定为，从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用插入排序（到尾部）；若初始数据基本反序，则选用选择排序。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。

若对其进行快速排序，在最坏的情况下所需要的时间是O(n2) 。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n) ，所需要的附加空间是O(n) 。

7．【计研题2000】对于n个记录的表进行2路归并排序，整个归并排序需进行log2n 趟（遍），共计移动n log2n次记录。

(即移动到新表中的总次数！共log2n趟，每趟都要移动n个元素)8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是H, C, Q, P, A, M, S, R, D, F, X ,Y；初始步长为4的希尔（shell）排序一趟的结果是P, A, C, S, Q, D, F, X , R, H,M, Y；二路归并排序一趟扫描的结果是H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟扫描的结果是F, H, C, D, P, A, M, Q, R, S, Y，X；堆排序初始建堆的结果是Y, S, X, R, P, C, M, H, Q, D, F, A。

9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

1 3 C (n − 2) + 3 C(n)=
n=2 n=3 n>3
通过逐步递推，可以得到：C(n)=3n/2-2。显然，当 n>=3 时，2n-3>3n/2-2。事实上， 3n/2-2 是解决这一问题的比较次数的下限。 6. 假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个 记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没 h-1 有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2 ；反之，若有 u 个
59.1C 59.2A 59.3D 59.4B 59.5G
60.1B 60.2C 60.3A
61.1B 61.2D 61.3B 61.4C 61.5F
部分答案解释如下： 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值， 而给定的序列并不满足。 20. 本题为步长为 3 的一趟希尔排序。 24.枢轴是 73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于 n/2 的结点上。 64. 因组与组之间已有序， 故将 n/k 个组分别排序即可， 基于比较的排序方法每组的时间下 界为 O(klog 2 k),全部时间下界为 O(nlog 2 k)。 二、判断题 1.√ 14. √ 27. √ 2.× 15. √ 28. × 3.× 16. × 29. × 4.× 17. × 30. × 5.× 18. × 31. √ 6.× 19. × 7.× 20. × 8.× 21. × 9.× 22. × 10. × 23. × 11. × 24. × 12. × 25. √ 13. × 26. ×
第 10 章 排序（参考答案）

数据结构与算法课后习题解答数据结构与算法课后习题解答第一章绪论（参考答案）1.3 (1) O(n)(2) (2) O(n)(3) (3) O(n)(4) (4) O(n1/2)(5) (5) 执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100。

9 100 10010 101 10011 9112。

20 9921 91 98。

30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）数据结构与算法课后习题解答1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define ***** 1024typedef int ElemType;// 实际上，ElemTypetypedef struct{ ElemType data[*****];int last; // last}sequenlist;（2*next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；数据结构与算法课后习题解答}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[*****];2.1 la，往往简称为“链表la”。

是副产品）2.2 23voidelenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的{ int i=0,j;while (ielenum A[i]=x) i++; // 查找插入位置for (j= elenum-1;jj--) A[j+1]=A[j];// 向后移动元素A[i]=x; // 插入元素数据结构与算法课后习题解答} // 算法结束24void rightrotate(ElemType A[],int n,k)// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

第十章内部排序10.23void Insert_Sortl(SqList &L)〃监视哨设在高下标端的插入排序算法{k=L」ength;for(i=k-l;i;-i)//从后向前逐个插入排序if(L.r[i].key>L.r[i+1] .key){L.r[k+l].key=L.r[i].key;// 监视哨for(j=i+l;L.rfj].key>L.r[i].key；4-+j)L.r [j-1 ] .key=L.r[j] .key; 〃前移L.r [j-1 ] .key=L.r[k+1 ] .key; 〃插入}}//Insert_Sortl10.24void BiInsert_Sort(SqList &L)〃二路插入排序的算法{int dlMAXSIZE];//辅助存储x=L.r .key;d =x;first= 1 ;final= 1;for(i=2;i<=L.length;i++){if(L.r[i].key>=x) //插入前部{for(j=final;d[j]>L.r[i].key;j—)dU+l]=dU];d[j+l]=L.r[i].key;final++;}else//插入后部{for(j=first;d[j]d[j-l]=d[j];dl(j-2)%MAXSIZE+ l]=L.r[iJ.key;first=(first-2)%MAXSIZE+1; //&种形式的表达式是为了兼顾first=l的情况}}//forfor(i=first j= 1 ;dLiJ ；i=i%MAXS!ZE+1 ,j++)//^l 各序列复制回去L.r[j].key=d[i];}//BiInsert_Sort10.25void SLInsert_Sort(SLList &L)〃静态链农的插入排序算法L.r[0].key=0;L.r[0].next=l;L.r[l].ncxt=O; 〃建初始循环链表for(i=2;i<=L.length;i++) // 逐个插入{p=O;x=L.r[i].key;while(L.rLL.r[p].next].keyp=L.r[p].next;q=L.r[p].next;L.r[p].ncxt=i;L.r[i].next=q;}//forp=L.r[OJ.next;for(i=l;i{whilc(pq=L.r[p].ncxt;if(p!二i){L.r[pJ<->L.r[iJ;L.r[i].next=p;}p=q；}//for}//SLInsert_Sort10.26void Bubble_Sortl(int a[ ],int n)〃对包含n个元素的数组a进彳亍改进的冒泡排序{change=n-l; //change指示上一趟冒泡中最后发生交换的元素while(change){for(c=0,i=0;iif(a[i]>a[i+1]){a[i]<->a[i+l];c=i+l;//c指示这一趟冒泡屮发生交换的元素}changc=c;}//while}//Bubble_Sortl10.27void Bubblc_Sort2(int a[ ],int n)〃相邻两趟是反方向起泡的冒泡排序算法{low=0;high=n-1; 〃冒泡的上F界change=l;while(low{change=():for(i=low;iif(a[i]>a[i+1])chanse=l:}high-;//修改上界for(i=high;i>low;i-) //从F 向上起泡a[i]<->a[i-l];changc=l;}low++;〃修改卜-界}//while}//Bubble_Sort210.28void Bubble_Sort3(int a[ ],int n)〃对上一题的算法进行化简，循环体中只包含一次冒泡{int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[l]无用d=l;b[0]=0;b[2]=n-l;//d为冒泡方向的标识,1为向上,・1为向下changc=l;while(b[0]{change=0;for(i=b[l -dl ;i!=bfl +d] ;i+=d) // 统一的冒泡算法if((a[i]・a[i+d])*d>0)//注意这个交换条件{a[i]<->a[i+d];change=l;}b[l+d]-=d; //修改边界d*=-l；〃换个方向}//while}//Bubble_Sort310.29void OE_Sort(int a[ ],int n)〃奇偶交换排序的算法{change=l;while(cha nge){change=():for(i= 1 ;iif(a[i]>a[i+1]){a[i]<->a[i+l];change=l;}for(i=0;iif(a[i]>a[i+1])}}//while}//OE_Sort分析:木算法的结束条件是连续两趟比较无交换发生10.30typcdcf struct {int low;int high;} boundary; //了序列的上下界类型void QSort_NotRecurve(int SQList &L)〃快速排序的非递归算法{low= 1 ;high=L.length;InitStack(S); //S 的元素为boundary 类型while(low{if(high-Iow>2) //如果当前了序列氏度大于3 尚未排好序{pivot=Partition(L,low,high); 〃进行一趟划分if(high-pivot>pivot-low){Push(S,{pivot+1 ,high}); //把长的了序列边界入栈high=pivot-l; 〃短的子序列留待下次排序}else{Push(S,{ low,pivot-1});low=pivot+l;}}〃讦else if(low{Easy_Sort(L,low,high); //直接进行比较排序low=high; 〃当前子序列标,忐为已排好序}else//如果当前子序列己排好序但栈屮还有未排序的子序列{Pop(S,a); 〃从栈中取出一个了序列low=a.low;high=a.high;}}//while}//QSort_NotRecurveint Partition(SQList &L,int low,int high)//-•趟划分的算法，与书上相同L.r[0]=L.r[low];pivotkey=L.r[low] .key;while(low=pivotkey)high-;L.r[low]=L.r[high];while(lowlow++;L.r[high]=L.r[low];}//whileL.r[lowJ=L.r[OJ;return low;{//Partitionvoid Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序{if(high-low==l)//子序列只含两个元索if(L.r[low] .key>L.r[high] .key) L.r[low]<->L.r[high];C1SC//T序列含冇三个元素{if(L.r[low].key>L.r[low+ l].key) L.r[low]<->L.r[low+1 ];if(L.r[low+1 J.key>L.r[high].key) L.r[low+1 J<->L.r[high];if(L.r[low].key>L.r[low+ l].key) L.r[low]<->L.r[low+ 1J;}}//Easy_Sort10.31void Divide(int a[ l,int n)〃把数组a中所有值为负的记录调到非负的记录ZMj{low=();high=n-l;whilc(low{while(low=0) high-; 〃以0作为虚拟的枢轴记录a[lowJ<->aLhighJ;while(lowallow]<->a[high];}[//Divide10.32typedef enum {RED,WHITE,BLUE} color; //三种颜色void Flag_Arrange(color a[ ],int n)〃把由三种颜色组成的序列重排为按照红，白，蓝的顺序排列{i=0;j=0;k=n-1;while(j<=k)switch(a[jj){case RED:i++；j++；break;case WHITE:j++；break;case BLUE:a[j]<->a[k];k-; 〃这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况}}//Flag_Arrange分析:这个算法屮设立了三个指针.其屮,j表示当前元素;i以前的元素全部为红色;k以示的元索全部为蓝色.这样，就可以根据j的颜色，把其交换到序列的前部或者后部.10.33void LinkedList_Select_Sort(LinkedList &L)〃单链表上的简单选择排序算法{for(p=L;p->next->next;p=p->next){q=p->ncxt;x=q->data;for(r=q,s=q;r->next;r=r->next)//?l： q后面寻找元素值最小的结点if(「>n ext->data{x=r- >n ext->data;s=r;}if(s!=q) //找至【J了值比q->data更小的最小结点s->next{p->next=s->next;s->next=q;(二q・> next;q・>next二pp->ncxt->ncxt=t;} 〃交换q和s->next两个结点}//for}//LinkedList_Select_Sort10.34void Build_Heap(Heap &H,int n)〃从低下标到高下标逐个插入建堆的算法{for(i=2;i{ 〃此时从H.r[l]到H.r[i・l]己经是大顶堆• •J=l;while(j!=l)//把H.r[i]插入{k=j/2;if(H.r|j] .key>H.r[kJ .key)H.r[j]<->H.r[k];j=k;}}//for}//Build_Heap10.35void TriHeap_Sort(Heap &H)〃利用三叉树形式的堆进行排序的算法{for(i=H.length/3;i>0;i—)Heap_Adjust(H,i,H.length);for(i=H」ength;i>l;i—){H.r[l]<->H.r[i];Heap_Adjust(H, 1 ,i-l);}}//TriHeap_Sortvoid Heap_Adjust(Heap &H,int s,int m)//顺序表H 中,H.r[s+1]到H.r[m]已经是堆，把H.r[s]插入并调整成堆{rc=H.r[s];for(j=3 *s-1 ;j<=m;j=3 *j-1){s=j；}H.rfs]=rc;}//Heap_ Adjust分析:本算法与课本上的堆排序算法相比，只有两处改动:1.建初始堆时,i的上限从H.length/3 开始(为什么?)2.调整堆的时候，要从结点的三个孩子结点中选择最大的那一个，最左边的孩子的序号的计算公式为j=3*s・l(为什么?)10.36void Merge_Sort(int a[ ],int n)〃归并排序的非递归算法{for(l= 1 ;lfor(i=0;(2*i-l)*l{start 1 =2*1 *i; //求出待归并的两段的上下界end l=start 1+1-1;start2=cnd 1+1;end2=(start2+l-1 )>(n-1 )?(n-1 )start2+l-1);//注意end2 可能超出边界Merge(a,start 1 ,end 1 ,start2,end2); 〃归)[■}}//Merge_Sortvoid Merge(int a[ ],int sl,int el,int s2,int e2)〃将有序子序列a[sl]到a[el]和a[s2]到a[e2]归并为有序序列a[sl]到a[e2]{int bfMAXSIZE]; 〃设立辅助存储数组bfor(i=s 1 ,j=s2,k=s 1 ;i<=e 1 &&jv二e2;k++) if(a[i]else b[k]=a[j++]; while(i<=el) b[k++]=a[i++];while(j<=e2) b[k++]=a[j++]；〃归并到b 屮for(i=s 1 ;i<=e2;i++) // 复制回去a[iJ=bLiJ；}//Merge10.37void LinkedList_Merge_Sort 1 (LinkedList &L)〃链农结构上的归并排序非递归算法{for(l= 1 ;lfor(p=L->next,e2=p;p->next;p=e2){for(i= 1 ,q=p;i<=l&&q->next;i++,q=q->next);cl=q；for(i= l;i<=l&&q->next;i++,q=q->next);e2=q; 〃求出两个待归并子序列的尾指针if (el !=e2) LinkedList_Merge(L,p,el,e2); // 归并}}//LinkcdList_Mcrgc_Sort 1void LinkedList_Merge(LinkedList &L,LNode *p,LNode *el,LNode *e2)〃対链表上的子序列进行归并，第一个子序列是从p->next到el,第二个是从e 1 ->next到e2{q=p->ncxt;r=c 1 ->ncxt; //q和r为两个了序列的起始位置while(q!=el->next&&r!=e2->next){if(q->datadata) //^择关键字较小的那个结点接在p的后而{p->next=q;p=q;q=q->ncxt;}else{p->next=r;p=r;r=r->ncxt;}}//whilewhile(q!=el->next) //接上剩余部分{p->ncxt=q;p=q;q=q->next;}while(r!=e2->next){p->next=r;p=r;r=r->next;}//LinkedList_Merge10.38void LinkedList_Merge_Sort2(LinkedList &L)〃初始归并段为最大有序子序列的归并排序，采用链表存储结构{LNodc *cnd[MAXSIZE]; 〃设立一个数组来存储各冇序了序列的尾指针for(p=L->next->nextj=0;p;p=p->next) // 求各有序子序列的尾指针if(!p->nextllp->data>p->next->data) end[i++]=p;while(end[O]->next) //当不止一个子序列时进行两两归并{j=O；k=O；//j：当前子序列尾指针存储位B!；k：归并后的子序列尾指针存储位置for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列{el二end[j];e2=end[j+l]; //确定两个子序列if(e 1 ->next) LinkedList_Merge(L,p,e 1 ,e2); 〃归并cnd[k++]=c2; //用新序列的尾指针取代原来的尾指针j+=2;〃转到后面两个子序列}}//while}//LinkedList_Merge_Sort2void LinkcdList_Mcrgc(LinkcdList &L,LNodc *p,LNodc *cl,LNodc *c2)〃对链表上的了序列进行归并，第一个了序列是从p->next到el,第二个是从el->next到e2{q=p->next;r=e 1 ->next;while(q!=e 1 ->next&&r!=e2->next){if(q->datadata){p->next=q;p=q;q=q->next;}else{p->next=r;p=r;r=r->next;}}//whilewhile(q!=e 1 ->next){p->next=q;p=q;q=q->next;}while(r!=e2->next)p->next=r;p=r;}//LinkedList_Merge,与上一题完全相同10.39void SL_Mcrgc(int a[ ],int ll,int 12)//把长度分别为11,12且11A2<(11+12)的两个有序子序列归并为有序序列{startl=0;start2=ll;//分别表示序列1和序列2的剩余未归并部分的起始位直for(i=0;i{for(j=start2;jk=j-start2; //k为要向右循环移动的位数RSh(a,start 1 j-1 ,k);//W a[startl]到a[j・l]之间的子序列循环右移k位start l+=k+l;start2=j; 〃修改两序列尚未归并部分的起始位置}}//SL_Mergevoid RSh(int a[ ] jnt start,int end,int k)〃将a[start]到a[end]之间的子序列循环右移k 位,算法原理参见5.18{len=end-start+l;for(i=l;i<=k;i++)if(len%i==0&&k%i==0) p=i; 〃求len 和k 的最大公约数pfor(i=0;i{j=start+i;l=start+(i+k)%len;temp=a|jj;while(l!=start+i){a[j]=tcmp;temp=a[l];all]=a|j]；j=l；l=start+(j-start4-k)%len; // 依次|H J右移}a[start+i]=temp;}//for}//RSh10.40E后给出的解题思路在表述上存在问题，无法理解•比如说,“把第一个序列划分为两个子序列, 使其中的第一个子序列含有si个记录,0<=s 110.41void Hash_Sort(int a[ J)//X'j 1000个关键字为四位整数的记录进行排序{int b[ 10000];for(i=0;ivl000;i卄)〃直接按关键字散列{for(j=a[i] ;b[j] ;j=(j+1)% 10000);fo「(i=0,j=0;ivl000;j++)〃将散列收回a 中if(b[j]){for(x=b[j],k=j ;b[kj ;k=(k+1)%10000)if(b[k>=x){a[i++]=x;b[k]=0;}}//if}//Hash_Sort10.42typedef stmct {int gt; //大于该记录的个数int It; 〃小于该记录的个数} place; 〃整个序列中比某个关键字大或小的记录个数int Get_Mid(int a[ J,int n)〃求一个序列的中值记录的位置{place b[MAXSIZEJ;for(i=();ifor(j=0;j{if(a[j]>a[i])b[i].gt++;else if(a[j]}mid=0;min_dif=abs(b[0].gt-b[0].lt);for(i=0;iif(abs(b[i].gt-b[i].lt)return mid;}//Gct_Mid10.43void Count_Sort(int a[ ],int n)〃计数排序算法{int cfMAXSIZE];for(i=0;i{for(j=0,count=0;jif(a[j]c[i]=count;}for(i=0;i{min=();for(j=0;jif(c[j]a[i]<->a[min]; 〃与第i 个记录交换c[minJ=INFINITY; //修改该记录的c值为无穷大以便下一次选収}}//Count_Sort10.44void Enum_Sort(int a[ ],int n)〃对关键字只能取v到w Z间任意整数的序列进行排序int number[w+1 J,pos[w+1J; for(i=0;ifor(pos[0]=0,i=l；ipos[i]=pos[i-l]+num[i]; //pos 数组可以把关键字的值映射为元素在排好的序列中的位置for(i=0;ic[pos[a[i]]++]=a[i];for(i=0;ia[i]=c[i];}//Enum_Sort分析:木算法参考了第五章三元组稀疏矩阵转置的算法思想，其中的pos数组和那里的cpot数组起的是相类似的作用.10.45typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型typedef digit[3] num; //3位自然数类型，假设低位存储在低下标，高位存储在高卜•标void Enuni_Radix_Sort(num a[ ],int n)〃利用计数实现基数排序,其屮关键字为3位白然数，共有n个自然数{int number ,pos ;num c[MAXSIZEJ;for(j=0;j<3;j++) //依次对个位，十位和百位排序{for(i=0;ifor(pos[0]=0,i=l;ipos[iJ=pos[i-l]+numLi]; //把关键字的值映射为元素在排好的序列中的位置for(i=0;ic[pos[a[ij[j]]++]=a[i];for(i=0;ia[i]=c[i];}//for}//Enum_Radix_Sort分析:计数排序是一种稳定的排序方法.」E因为如此，它才能够被用来实现基数排序.10.46typedef struct {int key;int pos;} Shadow;//影子序列的记录类型void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)〃对元素很人的记录序列b进行排序,结果放入a中，不移动元素{Shadow d[MAXSIZE];for(i=0;i{d[i].key=b[i].key;dfi].pos=i;}for(i=n-l ,change= 1 ;i> 1 &&change;i・・)//对影子序列执行冒泡排序{change=0;for(j=O;jif(d[j].key>d[j+l].key){dU]<->dU+U；change=l;}//forfor(i=0;ia[i]=b[d[i].pos]; }//Shadow_Sort。

1．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。

A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

2 else d=d/3; } }
数据结构教程学习指导
（1）指出fun(a，n)算法的功能。 （2）当a[]={5，1，3，6，2，7，4，8}时，问fun(a，8)共执行几趟排序，各趟的排序 结果是什么？ 答：（1）fun(a，n)算法的功能是采用增量递减为1/3的希尔排序方法对a数组中元素进 行递增排序。 （2）当a[]={5，1，3，6，2，7，4，8}时，执行fun(a，8)的过程如下： d=2：2 1 3 6 4 7 5 8 d=1：1 2 3 4 5 6 7 8 共有两趟排序。 4. 在实现快速排序的非递归算法时，可根据基准元素，将待排序序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈 的深度为 O(log2n)。 答：由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。在 排序过程中每次划分都把整个待排序序列根据基准元素划分为左、右两个子序列，然后对 这两个子序列进行类似的处理。 设S(n)为对n个记录进行快速排序时平均所需栈的深度， 则： S(n)=
KeyType QuickSelect(RecType R[],int s,int t,int k) //在 R[s..t]序列中找第 k 小的元素 { int i=s,j=t; RecType tmp; if (s<t) //区间内至少存在 2 个元素的情况 { tmp=R[s]; //用区间的第 1 个记录作为基准 while (i!=j) //从区间两端交替向中间扫描,直至 i=j 为止 { while (j>i && R[j].key>=tmp.key) j--; //从右向左扫描,找第 1 个关键字小于 tmp 的 R[j] R[i]=R[j]; //将 R[j]前移到 R[i]的位置 while (i<j && R[i].key<=tmp.key) i++; //从左向右扫描,找第 1 个关键字大于 tmp 的 R[i] R[j]=R[i]; //将 R[i]后移到 R[j]的位置 } R[i]=tmp; if (k-1==i) return R[i].key; else if (k-1<i) return QuickSelect(R,s,i-1,k); //在左区间中递归查找 else return QuickSelect(R,i+1,t,k); //在右区间中递&& s==k-1) return R[k-1].key; else return -1; }

《数据结构》各章课后作业答案 第一章 绪论课后作业答案1. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2．分析下面各程序段的时间复杂度（每小题5分，共20分）解：1.第一个for 循环执行n+1次，第二个for 循环执行n(m+1)次，A[i][j]=0;语句执行n*m 次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。

故时间复杂度为O(n*m)。

2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：s+=B[i][j];它的执行次数为n 2，所以本程序段的时间复杂度是O(n 2)。

3. 该算法的基本操作是语句x++, 其语句频度为：1111n n i i j --==∑∑=10()n i n i -=-∑=(1)2n n - 所以本程序段的时间复杂度是O(n 2)。

4.设语句执行m 次，则有3m≤n ⇒m ≤log 3n所以本程序段的时间复杂度为O(log 3n)。

第二章 线性表课后作业答案1. 填空题。

（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

（2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。

（2）s=0;for （i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j]; sum=s; 答：O （n 2）（1） for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0;(3) x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(4)i=1;while(i<=n)i=i*3;（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

一、单选题1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。

算法与数据结构课后答案9-11章第9章集合一、基础知识题9.1 若对长度均为n 的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？（1）查找不成功，即表中没有和关键字K 相等的记录；（2）查找成功，且表中只有一个和关键字K 相等的记录；（3）查找成功，且表中有多个和关键字K 相等的记录，要求计算有多少个和关键字K 相等的记录。

【解答】（1）平均查找长度不相同。

前者在n+1个位置均可能失败，后者失败时的查找长度都是n+1。

（2）平均查找长度相同。

在n 个位置上均可能成功。

（3）平均查找长度不相同。

前者在某个位置上(1<=i<=n)查找成功时，和关键字K 相等的记录是连续的，而后者要查找完顺序表的全部记录。

9.2 在查找和排序算法中，监视哨的作用是什么？【解答】监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

9.3 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？【解答】分成45块，每块的理想长度为45(最后一块长20)。

若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。

9.4 用不同的输入顺序输入n 个关键字，可能构造出的二叉排序树具有多少种不同形态? 【解答】 9.5 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，中序前驱结点没有右孩子。

【证明】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左孩子；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结点，没有右孩子。

命题得证。

9.6 对于一个高度为h 的A VL 树，其最少结点数是多少？反之，对于一个有n 个结点的A VL 树，其最大高度是多少? 最小高度是多少?【解答】设以N h 表示深度为h 的A VL 树中含有的最少结点数。

第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。

第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

1. 画出下图所示的无向图的邻接表。

列出深度优先和广度优先搜索遍历该图所的顶点序列和边的序列。

邻接表：深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6边的序列：（1，2） （2，3） （3，4） （4，5） （5，6）广度优先搜索：顶点序列：1 -2 -3 -6 -5-4边的序列：（1，2） （1，3） （1，6） （1，5） （5，4）2 已知以二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 101 00 0 0 0 0 1 0 1 0 2 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 4 0 0 0 0 1 0 0 0 1 0 5 0 0 0 0 0 1 0 0 0 1 6 1 1 0 0 0 0 0 0 0 0 70 0 1 0 0 0 0 0 0 115246 38 1 0 0 1 0 0 0 0 1 09 0 0 0 0 1 0 1 0 0 110 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下：自顶点1出发进行遍历所得的深度优先生成树：自顶点1出发进行遍历所得的广度优先生成树：3请对下图的无向带权图（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。

（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：（1） 邻接矩阵：∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞∞54 ∞ ∞ 6 ∞普里母算法求得的最小生成树：759645635 534 ed25cbhfga（2）邻接表：克鲁斯卡尔算法生成最小生成树过程：4 试列出下图中全部可能的拓扑有序序列。

1. 画出下图所示的无向图的邻接表。

列出深度优先和广度优先搜索遍历该图所的顶点序列和边的序列。

邻接表：深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6边的序列：（1，2） （2，3） （3，4） （4，5） （5，6）广度优先搜索：顶点序列：1 -2 -3 -6 -5-4边的序列：（1，2） （1，3） （1，6） （1，5） （5，4）2 已知以二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 101 0 0 0 0 0 0 1 0 1 02 0 0 1 0 0 0 1 0 0 03 0 0 0 1 0 0 0 1 0 04 0 0 0 0 1 0 0 0 1 05 0 0 0 0 0 1 0 0 0 16 1 1 0 0 0 0 0 0 0 0 70 0 1 0 0 0 0 0 0 115246 38 1 0 0 1 0 0 0 0 1 09 0 0 0 0 1 0 1 0 0 110 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下：自顶点1出发进行遍历所得的深度优先生成树：自顶点1出发进行遍历所得的广度优先生成树：3请对下图的无向带权图（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。

（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：（1） 邻接矩阵：∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞∞54 ∞ ∞ 6 ∞普里母算法求得的最小生成树：759645635 534 ed25cbhfga（2）邻接表：克鲁斯卡尔算法生成最小生成树过程：4 试列出下图中全部可能的拓扑有序序列。

第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。

然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。

每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。

第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。