【正文】 表、有序表：順序查找成功時，平均查找長度均為1/(n)*(1+2+…+n)=(n+1)/2；兩者相同。②無序表：順序查找不成功時，平均查找長度為n+1；有序表，平均查找長度為1/(n+1)*(1+2+…+(n+1))=(n+2)/2；兩者不相同。③表中只有m個關(guān)鍵字等于給定值k的記錄，無序表：ASL=n+1；有序表：ASL=（n+1）/2+m；兩者不相同。（2）4180261338687730（3）計算哈希地址：H(13)=(13 mod 7)+1=7 H(15)=(15mod 7)+1=2 H(22)=(22 mod 7)+1=2 H(8)=(8 mod 7)+1=2 H(34)=(34 mod 7)+1=7 H(19)=(19 mod 7)+1=6 H(21)=(21 mod 7)+1=1 H(29)=(29 mod 7)+1=2①012345678211522829191334②012345678910212 8 19132934③780123456ΛΛΛΛ21Λ152219Λ 8 29ΛΛ1321Λ4.（1）int SeqSearch(RecordType r, int n, KeyType k){ i=0。 r[n].key=k。 while (r[i].key!=k) i++。 if (in) return n。 else return 1。 }(2)KeyType MaxNode (BSTree bt){ if (bt!=NULL) { f=bt。while (btrchild!=NULL) { f=bt。 bt=btrchild。}return fkey。} }(3)int level(BSTree bt, KeyType k){ d=0。 if (bt==NULL) return 0。 //空樹深度為0 else { d++。 //根結(jié)點深度為1while (btdata!=k){ if (btdatak) bt=btrchild。 //右子樹中查找 else bt=btrchild。 //左子樹中查找 d++。} return d。}(4)define N 50int IsBSTree(BSTree bt){BSNode *stack[N],*p。 KeyType k。 int isbst，top。 isbst=1。 //標志變量，首先假定bt是二叉排序樹 top=1。 //置空棧 p=bt。 //p從根出發(fā)while (isbst amp。amp。 (p!=NULL || top!=1)) {while ((p!=NULL) {k=pkey。 if (plchildkeyk || prchildkeyk) { isbst=0。 break。} if (prchild!=NULL) stack[++top]=prchild。 p=plchild。 } if (top!=1)p=stack[top]。 }return isbst。}(5)BSTree BSTDeleteAll(BSTree t, KeyType k){BSTree p。 p=BSTSearch1(t,k)。 //查找關(guān)鍵字值不小于x的結(jié)點 while (p!=NULL) { t=BSTDelete(t,p)。 //刪除p所指示結(jié)點 p=BSTSearch1(t,k)。 }}注：函數(shù)BSTSearch1，BSTDelete參閱教材167。,167。第8章 習(xí)題答案填空題（1） i（2） n1（3） n/2（4） O(n2)（5） O(n)（6） 冒泡排序（7） 希爾排序（8） 直接插入排序（9） 插入排序 、 選擇排序（10） 79，46，71，35，41，25，56（11） 25，41，35，46，56，79，71（12） n/2 n1 O(nlogn)（13） 正 反 反（14） 直接選擇排序、希爾排序、堆排序、快速排序（15） 堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序判斷題（1）√（2）√（3）（4）（5）（6）（7）（8）（9）（10）√簡答題（1）略 （參考教材寫）。（2）易于鏈表實現(xiàn)的是插入排序、歸并排序和基數(shù)排序（3）初始狀態(tài)為逆序時，直接插入、直接選擇和冒泡排序的比較次數(shù)分別為(n+2)(n1)/n(n1)/n(n1)/2，移動次數(shù)分別為(n+4)(n1)/2，3(n1)，3n(n1)/2，因此文件逆序時采用直接選擇排序較好。（4）在初始狀態(tài)為逆序情況下，采用冒泡排序是穩(wěn)定排序。（5）高度為h的堆，最多有2h1個元素，最少有2h1個元素。在高度為h的大頂堆中，關(guān)鍵字最小的元素存放在堆的第h層上的最后一個元素的位置w上，其中2h1≤ w≤2h1。（6）最好選用堆排序，對比其他效率較高的排序算法，大都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部順序，而無法知道排序過程中部分元素的有序性，而堆排序則每次輸出一個極值元素，且比較次數(shù)不超過，要好于如冒泡排序、選擇排序等簡單排序算法，由題意，只選擇前10個大元素，所以可以利用大頂堆進行排序。（7）d是8，分配和收集8趟，rd是26，隊列個數(shù)26。（8）①是大頂堆②不是堆，可以調(diào)整為下面的小頂堆 1234567891012243065335648988670③是大頂堆④不是堆，可以把它調(diào)整為下面的小頂堆1234567891011120523203528382961567640100算法設(shè)計題（1）分析與解答給head單鏈表設(shè)置一個附加表頭結(jié)點，在排序過程中，單鏈表分成兩個子表，即排序子表和未排序子表，首先將單鏈表的頭結(jié)點和第一個結(jié)點看成是已經(jīng)排序的子表，設(shè)置rear指針指向已排序子表的最后一個結(jié)點，初始時也就是單鏈表的第一個結(jié)點。設(shè)置h指針指向未排序子表的第一個結(jié)點，初始時也就是單鏈表的第二個結(jié)點，每次取出未排序子表的第一個結(jié)點，將其插入到前面已排序子表的合適位置上。設(shè)置q指針從已排序子表的第一個結(jié)點出發(fā)，順序查找合適位置；并設(shè)置指針p用來跟蹤q的直接前驅(qū)，以便插入操作。typedef struct node{ int data。 struct node *next。}ListNode。typedef ListNode *LinkList。Instersort (LinkList head) { ListNode *p,*q,*h,*rear。 rear=head→next。/*rear指向已排序子表的最后一個結(jié)點，初始時為單鏈表的第一個結(jié)點*/ h=rear→next。 /*h指向未排序子表的第一個結(jié)點*/ while (h!=NULL) if (h→datarear→data) {p=head。 q=p→next。 /*q從已排序子表的第一個結(jié)點出發(fā)，找插入位置*/ while (q→datah→data) { p=q。 q=q→next。} rear→next=h→next。 /*從未排序子表中分離出h結(jié)點*/ h→next=q； /*將h結(jié)點插入到已排序子表的p和q之間*/ p→next=h。 h=rear→next。 /*h指向下一個待插入的結(jié)點*/ } else { rear=h。 h=h→next。} }（2）i從左向右掃描數(shù)組，找到正數(shù)后，j從右向左掃描數(shù)組，找到負數(shù)后，交換i、j位置上的數(shù)據(jù)，然后i繼續(xù)向右掃描，反復(fù)執(zhí)行上述操作，直到i和j相遇。define MaxSize 100 /*待排序記錄可能達到的最大長度*/typedef struct /*記錄類型*/{ KeyType key； /*關(guān)鍵字項*/ InfoType OtherData；/*其他數(shù)據(jù)項，InfoType根據(jù)實際情況定義*/}RecordType；typedef RecordType RecData[MaxSize]；/*RecData為順序表類型*/void Resort(RecData r){ int i=0,j=n1。 RecordType x。 do { while ( ij amp。amp。 r[i].key0) i++。 while ( ji amp。amp。 r[j].key0) j。 if (ij) { x=r[i]。 r[i]=r[j]。 r[j]=x。} i++。 j。 }while(ij)。 }(3) void BubbleSort(RecData r,int n)/*自下往上掃描的冒泡排序算法*/{ int lastexchange,j,i=0,x。 while (in1) {lastexchange=n1。 for (j=n1。 ji。 j) /*自下往上掃描r[0..i]*/ if (r[j1].key r[j].key) /* r[j1]和r[j]交換 */ { x=r[j]。 r[j]=r[j1]。 r[j1]=x。 lastexchange=j。 } i= lastexchange。 } }(4)①排序結(jié)束條件為沒有交換元素為止或進行了幾趟排序。②函數(shù)描述如下：void Qrsort(RecData r)/*排序元素r[0]～r[n1]*/{ int i,flag。 RecordType t。 do { flag=0。 for ( i=0。 in。 i++) /*奇數(shù)掃描*/ { if (r[i].keyr[i+1].key) { flag=1。 t=r[i+1]。 r[i+1]=r[i]。 r[i]=t。} i++。 } for ( i=1。 in。 i++) /*偶數(shù)掃描*/ { if (r[i].keyr[i+1].key) { flag=1。 t=r[i+1]。 r[i+1]=r[i]。 r[i]=t。} i++。 } }while (glag!=0)。 }（5） 略（參考教材）。（6）設(shè)向量c有10個元素，其值在0～9之間，如下圖所示：cn101234567891905438762 根據(jù)題意排序結(jié)果如下圖所示：bn101234567890123456789算法描述如下:Sort (int c[],int b[], int n){ int i。 for (i=0。 in。 i++) b[c[i]]=c[i]。}（7）堆的類型定義：define N 50 typedef struct element。 { KeyType key。 }RecType。typedef struct list。 { KeyType R[N]。 int n。 }SeqList。void HeapDelete(SeqList *heap, int i){ int j。 heap→R[i]=heap→R[n]。 /*R[i]與堆底元素交換位置*/heap→n=1。 Heapify(heap,i,haep→n)。/*調(diào)用調(diào)整堆算法*/ }Heapify (SeqList *heap, int i。 int base)/*將R[i..base]調(diào)整為堆*/{ int j。 RecType temp=heap→R[i]。 for (j=2*i。 j=base。 j*=2) { if (jbase amp。amp。 heap→R[j].keyheap→R[j+1].key) j++。/*若i有右孩子，且右孩子大于左孩子，則讓j指向右孩子*/ if (heap→R[j].key=) break。 heap→R[i]=heap→R[j]。 i=j。 } }38