本章习题解答只给岀算法描述,1~6题略。 1.以关键字序列(tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,quy, any)为例,手工执行以下排序算法(按字典序比较关键字的大小),写出每一趟排序结束 时的关键字状态 (1)直接插入排序;(2)冒泡排序:(3)直接选择排序 (4)快速排序 (5)归并排序:(6)基数排序 2已知序列{503,87,512,61,908,170,897,275,653,462},请给出采 用堆排序对该序列做升序排序时的每一趟结果。 3有n个不同的英文单词,它们的长度相等,均为m,若n>>50,mr[max ]. key) I w=r[minI [min]=r [il r[il=v r min=r
1 本章习题解答只给出算法描述，1~6 题略。 ⒈以关键字序列（tim，kay，eva，roy，dot，jon，kim，ann，tom，jim，guy， amy）为例，手工执行以下排序算法（按字典序比较关键字的大小），写出每一趟排序结束 时的关键字状态： ⑴直接插入排序； ⑵冒泡排序； ⑶直接选择排序； ⑷快速排序； ⑸归并排序； ⑹基数排序。 ⒉已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采 用堆排序对该序列做升序排序时的每一趟结果。 ⒊有 n 个不同的英文单词，它们的长度相等，均为 m，若 n>>50,mr[max].key) max=j; } if (min!=i) { w=r[min]; r[min]=r[i]; r[i]=w; } if (max!=n-i+1) { if (max=i) { w=r[min]; r[min]=r[n-i+1]; r[n-i+1]=w; } else
w=r [maxi r [max]=r [n-i+l]i r[n-i+1]=w; 1++; 6归并插入排序是对关键字进行比较次数最少的一种内部排序方法,它可按如下步骤 进行: (1)另开辟两个大小为n/2的数组sma11和1arge。从i=1到n-1,对每个奇数的 i,比较x[i]和x[i+1],将较小者和较大者分别依次存入数组sma11和1arge中(当 n为奇数时,sma1ln/2]=x[n]); 对数组1age[1.Ln/2小中元素进行归 并插入排序,同时相应调整sma11中的元素,使得在这一步结束时达到 1age[i]<1arge[i+1],i=1,2,,|n/2」-1 small[i]<large[i], 1=1, 2,,Ln/2J; (3)将sma11[11传送至x[1]中,将1arge[]至1 arge [Ln/2传送至x[2]至 Ln/2H+1]中 (4)定义一组整数inti=(21+1+(-1)3)/3,i=1,2,…,t-1,直至int[txn/21 利用折半插入依次将sma11[int[i+1]至sma11[int[i]+1]插入至x数组中去。例 如,若n=21,则得到一组整数int[1]=1,int[2]=3,int[3]=5,int[4]=11,由 此sma11数组中元素应如下次序:sma113],sma11[2],sma11[5],sma11[4], sma11[11],sma11[10],…,sma11[61,插入到x数组中去。 (5)试以n=5和n=11手工执行归并插入排序,并计算排序过程中所作关键字比较的次 7.请以单链表为存储结构实现简单选择排序的算法 typedef struct( Key type key; JElemType; pede struct Lnode ElemType data struct LNode *next 7Lnode * Linklist Link list sort( Link List L)M为带头结点单链表
2 { w=r[max]; r[max]=r[n-i+1]; r[n-i+1]=w; } } i++; } } ⒍归并插入排序是对关键字进行比较次数最少的一种内部排序方法，它可按如下步骤 进行： ⑴另开辟两个大小为n/2的数组 small 和 large。从 i=1 到 n-1，对每个奇数的 i，比较 x[i]和 x[i+1]，将较小者和较大者分别依次存入数组 small 和 large 中（当 n 为奇数时，small[n/2]=x[n]）； ⑵ 对数组 large[1..n/2]中元素进行归 并插入排序，同时相应调整 small 中的元素，使得在这一步结束时达到： large[i]n/2+1, 利用折半插入依次将 small[int[i+1]]至 small[int[i]+1]插入至 x 数组中去。例 如，若 n=21，则得到一组整数 int[1]=1，int[2]=3，int[3]=5，int[4]=11，由 此 small 数组中元素应如下次序：small[3]，small[2]，small[5],small[4]， small[11]，small[10]，…，small[6]，插入到 x 数组中去。 ⑸试以 n=5 和 n=11 手工执行归并插入排序，并计算排序过程中所作关键字比较的次 数。 ⒎请以单链表为存储结构实现简单选择排序的算法。 typedef struct{ KeyType key; … }ElemType; typedef struct Lnode{ ElemType data; struct LNode *next; }Lnode ,*LinkList; LinkList sort ( LinkList L) //L 为带头结点单链表
p=L->next, while(p->next) q p->next; while(q) if(q->data. keynext, x=p->data; date=s->da S->data=x p=p->next, return L) 8.请以单链表为存储结构实现直接插入排序的算法。 LinkList sort ListList L) /L为带头结点的单链表 >next-next L>next->next=NULL while(p) sp->next; pI
3 { p=L->next ; while (p->next) { s=p; q=p->next; while (q) { if (q->data.keynext; } if (s!=p) { x=p->data; p->date=s->data; s->data=x; } p=p->next; } return(L); } ⒏请以单链表为存储结构实现直接插入排序的算法。 LinkList sort (ListList L) //L 为带头结点的单链表 { p=L->next->next; L->next->next=NULL; while (p) { s=p->next; pre=L ;
q=L->next while(q & p->data.key >q->data. key) preq q q->next >next-( pre->nextp return(l) 9.编写一个双向冒泡的算法,即相邻两遍向相反方向冒泡 typedef struct( Key type key J ElemType; typedef struct( ElemTy elem int length is table void sort(s table " L) while(flag) flag =0 for (i=j; Kelem[i]. key>L->elem[i+l]. key
4 q=L->next; while (q && p->data.key > q->data.key) { pre=q; q=q->next; } p->next=q; pre->next=p; p=s; } return(L); } ⒐编写一个双向冒泡的算法，即相邻两遍向相反方向冒泡。 typedef struct{ KeyType key; … }ElemType; typedef struct{ ElemType *elem; int length; }S_table; void sort(S_table *L) { flag = 1; j = 1; while (flag) { flag = 0; for ( i=j ; ilength-j; i++) if (L->elem[i].key>L->elem[i+1].key ) {
X L->elem[]FL->elem[i+1l L->elem i+1=x; flag=1 for(i=L->length-]; i>=j+l; i--) if (L->elemi].keyL->elemi-l key) x=L->elem [] L->elemi=L->elem[ i-1] L->elem i-1=x; flag=1 return 10.已知记录序列a[1.n]中的关键字各不相同,可按如下所述实现计数排序:另设 数组c[1..n],对每个记录a[i],统计序列中关键字比它小的记录个数存于c[i],则 c[i]=0的记录必为关键字最小的记录,然后依c[i]值的大小对a中记录进行重新排列, 试编写实现上述排序的算法 typedef struct( KevT y ElemType void sort(ElemType *A, ElemType "B, int n) int C[n+1 for(i-1; K<=n; 1++) C[]=0; for(i=1; K<=n; 1++)
5 x=L->elem [i]; L->elem[i]=L->elem[i+1] ; L->elem[i+1]=x; flag=1; } for (i=L->length-j; i>=j+1; i--) if (L->elem[i].keyelem[i-1].key) { x=L->elem [i]; L->elem[i]=L->elem[i-1] ; L->elem[i-1]=x; flag=1; } j++; } return; } ⒑已知记录序列 a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设 数组 c[1..n]，对每个记录 a[i]，统计序列中关键字比它小的记录个数存于 c[i]，则 c[i]=0 的记录必为关键字最小的记录，然后依 c[i]值的大小对 a 中记录进行重新排列， 试编写实现上述排序的算法。 typedef struct{ KeyType key; … }ElemType; void sort (ElemType *A, ElemType *B, int n) { int C[n+1] ; for (i=1 ;i<=n; i++) C[i] = 0; for (i=1; i<=n ; i++)
for g =1; ja[i+1], 则将二者交换,以后重复上述二趟过程,直至整个数组有序。 (1)试问排序结束的条件是什么? (2)编写一个实现上述排序过程的算法 排序结束的条件是没有交换发生。 void sort( ElemType A[n+1])/0号单元不用 fl while(flag for(1=1,i+1Ai+l]. key X=AlI A[i=A[i+1] A[i+]=x; return 12.编写算法,对n个关键字取整数值的记录进行整理,以使得所有关键字为负值的
6 { for (j=1 ; ja[i+1]， 则将二者交换，以后重复上述二趟过程，直至整个数组有序。 ⑴试问排序结束的条件是什么？ ⑵编写一个实现上述排序过程的算法。 排序结束的条件是没有交换发生。 void sort ( ElemType A[n+1]) //0 号单元不用 { flag = 1 ; while (flag) { for (i=1, i+1A[i+1].key ) { flag=1; x=A[i]; A[i]=A[i+1]; A[i+1]=x; } } return; } ⒓ 编写算法，对 n 个关键字取整数值的记录进行整理，以使得所有关键字为负值的
记录排在关键字为非负值的记录之前,要求 (1)采用顺序存储结构,至多使用一个记录的辅助存储空间 (2)算法的时间复杂度为o(n) (3)讨论算法中记录的最大移动次数 void process(int A[n]) low=0 high=n-1 while( low0) high++, if (lowelem[0=L->elem lowl K=L->elem[0]. key while (low<high)
7 记录排在关键字为非负值的记录之前，要求： ⑴采用顺序存储结构，至多使用一个记录的辅助存储空间； ⑵算法的时间复杂度为 O(n)； ⑶讨论算法中记录的最大移动次数。 void process (int A[n]) { low = 0; high = n-1; while ( low0) high++; if (lowelem[0] = L->elem[low] ; K=L->elem[0].key; while (low<high)
while (lowelem(high>=k) high-- >elem[low]=L->elem[high] while(lowelem[low=k) low++ ->elem high]=L->elem[low] L->elem[low]=L->elem[0 return(low) Elem Type middle(s table*L, int low, int high if (lowelem[) if(s>(high-low)/2) return(middle(l, low, S-1)) return(middle(l, s+l, high));
8 { while (lowelem[high]>=k) high--; L->elem[low] = L->elem[high] ; while (lowelem[low]elem[high] = L->elem[low] ; } L->elem[low] =L->elem[0]; return(low) ; } ElemType middle(S_table*L, int low , int high ) { if (lowelem[s]) ; if (s>(high-low)/2) return(middle(L,low,s-1)) ; else return(middle(L,s+1,high)); } }
