第九章 查找9.25int Search_Sq(SSTable ST,int key)/ 在有序表上順序查找的算法 , 監(jiān)視哨設(shè)在 高下標端ST.elemST.length+1.key=key; for(i=1;ST.elemi.key>key;i+);if(i>ST.length|ST.elemi.key<key) return ERROR;return i;/Search_Sq分析: 本算法查找成功情況下的平均查找長度為 ST.length/2, 不成功情況下為 ST.length.9.26int Search_Bin_Recursive(SSTable ST,int key,int low,int high)/折半查找的遞歸算法if(low>high) return 0; / 查找不到時返回 0 mid=(low+high)/2;if(ST.elemmid.key=key) return mid;else if(ST.elemmid.key>key)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive9.27int Locate_Bin(SSTable ST,int key)/折半查找 , 返回小于或等于待查元素的最后一個結(jié)點號int *r;r=ST.elem;if(key<r.key) return 0;else if(key>=rST.length.key) return ST.length;low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if(key>=rmid.key&&key<rmid+1.key) / 查找結(jié)束的條件 return mid;else if(key<rmid.key) high=mid; else low=mid; / 本算法不存在查找失敗的情況 , 不需要 return 0; /Locate_Bin9.28 typedef struct int maxkey; int firstloc; Index; typedef struct int *elem;int length;Index idxMAXBLOCK; / 每塊起始位 置和最大元素 , 其中 idx0 不利用 , 其內(nèi)容初始化為 0,0 以利于折半查找int blknum; / 塊的數(shù)目 IdxSqList; /索引順序表類型int Search_IdxSeq(IdxSqList L,int key)/分塊查找 , 用折半查找法確定記錄所在塊 , 塊內(nèi)采用順序查找法 if(key>L.idxL.blknum.maxkey) return ERROR; /超過最大元素low=1;high=L.blknum;found=0; while(low<=high&&!found) / 折半查找記錄所在塊號 mid mid=(low+high)/2; if(key<=L.idxmid.maxkey&&key>L.idxmid-1.maxkey)found=1; else if(key>L.idxmid.maxkey)low=mid+1; else high=mid-1; i=L.idxmid.firstloc; / 塊的下界 j=i+blksize-1; / 塊的上界 temp=L.elemi-1; / 保存相鄰元素 L.elemi-1=key; / 設(shè)置監(jiān)視哨 for(k=j;L.elemk!=key;k-); /順序查找L.elemi-1=temp; / 恢復元素 if(k<i) return ERROR; /未找到return k;/Search_IdxSeq分析: 在塊內(nèi)進行順序查找時 , 如果需要設(shè)置監(jiān)視哨 , 則必須先保存相鄰塊的相鄰 元素, 以免數(shù)據(jù)丟失 .9.29typedef struct LNode *h; /h 指向最小元素LNode *t; /t 指向上次查找的結(jié)點 CSList;LNode *Search_CSList(CSList &L,int key)/ 在有序單循環(huán)鏈表存儲結(jié)構(gòu)上的 查找算法 , 假定每次查找都成功 if(L.t->data=key) return L.t;else if(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i+);else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i+);L.t=p; / 更新 t 指針return p;/Search_CSList分析: 由于題目中假定每次查找都是成功的 , 所以本算法中沒有關(guān)于查找失敗的 處理. 由微積分可得 , 在等概率情況下 , 平均查找長度約為 n/3.9.30typedef struct DLNode *pre; int data;DLNode *next; DLNode;typedef struct DLNode *sp;int length; DSList; / 供查找的雙向循環(huán)鏈表類型DLNode*Search_DSList(DSList &L,int key)/ 在有序雙向循環(huán)鏈表存儲結(jié)構(gòu)上 的查找算法 , 假定每次查找都成功p=L.sp; if(p->data>key)while(p->data>key) p=p->pre;L.sp=p;else if(p->data<key)while(p->data<key) p=p->next;L.sp=p;return p;/Search_DSList分析: 本題的平均查找長度與上一題相同 , 也是 n/3.9.31int last=0,flag=1;int Is_BSTree(Bitree T)/ 判斷二叉樹 T 是否二叉排序樹 , 是則返回 1, 否則返 回0if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data<last) flag=0; / 與其中序前驅(qū)相比較 last=T->data;if(T->rchild&&flag) Is_BSTree(T->rchild);return flag;/Is_BSTree9.32int last=0;void MaxLT_MinGT(BiTree T,int x)/ 找到二叉排序樹 T 中小于 x 的最大元素和 大于 x 的最小元素if(T->lchild) MaxLT_MinGT(T->lchild,x); / 本算法仍是借助中序遍歷來 實現(xiàn)if(last<x&&T->data>=x) / 找到了小于 x 的最大元素 printf("a=%dn",last);if(last<=x&&T->data>x) / 找到了大于 x 的最小元素 printf("b=%dn",T->data);last=T->data;if(T->rchild) MaxLT_MinGT(T->rchild,x);/MaxLT_MinGT9.33從大到小輸出二叉排序樹 T 中所有不小于 xvoid Print_NLT(BiTree T,int x)/ 的元素if(T->rchild) Print_NLT(T->rchild,x);if(T->data<x) exit(); /當遇到小于 x 的元素時立即結(jié)束運行printf("%dn",T->data);if(T->lchild) Print_NLT(T->lchild,x); /先右后左的中序遍歷/Print_NLT9.34void Delete_NLT(BiTree &T,int x)/ 刪除二叉排序樹 T 中所有不小于 x 元素結(jié) 點, 并釋放空間if(T->rchild) Delete_NLT(T->rchild,x);if(T->data<x) exit(); /當遇到小于 x 的元素時立即結(jié)束運行q=T;T=T->lchild;free(q); / 如果樹根不小于 x, 則刪除樹根 , 并以左子樹的根作為新的樹根 if(T) Delete_NLT(T,x); /繼續(xù)在左子樹中執(zhí)行算法/Delete_NLT9.35void Print_Between(BiThrTree T,int a,int b)/打印輸出后繼線索二叉排序樹 T 中所有大于 a 且小于 b 的元素p=T;while(!p->ltag) p=p->lchild; /找到最小元素while(p&&p->data<b)if(p->data>a) printf("%dn",p->data); / 輸出符合條件的元素 if(p->rtag) p=p->rtag;else p=p->rchild; while(!p->ltag) p=p->lchild; / 轉(zhuǎn)到中序后繼/while/Print_Between9.36void BSTree_Insert_Key(BiThrTree &T,int x)/ 在后繼線索二叉排序樹 T 中插 入元素 xif(T->data<x) / 插入到右側(cè)if(T->rtag) /T沒有右子樹時 , 作為右孩子插入 p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode); q->data=x;T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p; / 修改原線索else BSTree_Insert_Key(T->rchild,x);/T有右子樹時 , 插入右子樹中/ifelse if(T->data>x) /插入到左子樹中if(!T->lchild) /T沒有左子樹時 , 作為左孩子插入 q=(BiThrNode*)malloc(sizeof(BiThrNode); q->data=x;T->lchild=q; q->rtag=1;q->rchild=T; / 修改自身的線索else BSTree_Insert_Key(T->lchild,x);/T有左子樹時 , 插入左子樹中/if/BSTree_Insert_Key9.37Status BSTree_Delete_key(BiThrTree &T,int x)/在后繼線索二叉排序樹 T中刪除元素 xBTNode*pre,*ptr,*suc;/ptr 為 x 所在結(jié)點 ,pre 和 suc 分別指向 ptr 的前 驅(qū)和后繼p=T;last=NULL; /last始終指向當前結(jié)點 p 的前一個 ( 前驅(qū) )while(!p->ltag) p=p->lchild; /找到中序起始元素while(p)if(p->data=x) / 找到了元素 x 結(jié)點pre=last;ptr=p;else if(last&&last->data=x) suc=p; /找到了 x 的后繼if(p->rtag) p=p->rtag;elsep=p->rchild;while(!p->ltag) p=p->lchild; / 轉(zhuǎn)到中序后繼last=p;/while / 借助中序遍歷找到元素 x 及其前驅(qū)和后繼結(jié)點if(!ptr) return ERROR; /未找到待刪結(jié)點Delete_BSTree(ptr); / 刪除 x 結(jié)點if(pre&&pre->rtag)pre->rchild=suc; / 修改線索return OK;/BSTree_Delete_keyvoid Delete_BSTree(BiThrTree &T)/ 課本上給出的刪除二叉排序樹的子樹 T 的算法 , 按照線索二叉樹的結(jié)構(gòu)作了一些改動q=T;if(!T->ltag&&T->rtag) /結(jié)點無右子樹 , 此時只需重接其左子樹T=T->lchild;else if(T->ltag&&!T->rtag) /結(jié)點無左子樹 , 此時只需重接其右子樹T=T->rchild;else if(!T->ltag&&!T->rtag) /結(jié)點既有左子樹又有右子樹p=T;r=T->lchild;while(!r->rtag)s=r;r=r->rchild; / 找到結(jié)點的前驅(qū) r 和 r 的雙親 sT->data=r->data; / 用 r 代替 T 結(jié)點if(s!=T)s->rchild=r->lchild;else s->lchild=r->lchild; / 重接 r 的左子樹到其雙親結(jié)點上q=r;/elsefree(q); / 刪除結(jié)點/Delete_BSTree分析: 本算法采用了先求出 x 結(jié)點的前驅(qū)和后繼 , 再刪除 x 結(jié)點的辦法 , 這樣修改 線索時會比較簡單 , 直接讓前驅(qū)的線索指向后繼就行了 . 如果試圖在刪除 x 結(jié)點 的同時修改線索 , 則問題反而復雜化了 .9.38 void BSTree_Merge(BiTree &T,BiTree &S) 把二叉排序樹 S合并至U T 中if(S->lchild) BSTree_Merge(T,S->lchild);if(S->rchild) BSTree_Merge(T,S->rchild); /合并子樹Insert_Key(T,S); / 插入元素/BSTree_Mergevoid Insert_Node(Bitree &T,BTNode *S)/ 把樹結(jié)點 S 插入至 T 的合適位置上 if(S->data>T->data)if(!T->rchild) T->rchild=S;else Insert_Node(T->rchild,S);else if(S->data<T->data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchild=NULL; /插入的新結(jié)點必須和原來的左右子樹斷絕關(guān)系S->rchild=NULL; /否則會導致樹結(jié)構(gòu)的混亂/Insert_Node分析: 這是一個與課本上不同的插入算法 . 在合并過程中 , 并不釋放或新建任何結(jié) 點, 而是采取修改指針的方式來完成合并 . 這樣, 就必須按照后序序列把一棵樹中 的元素逐個連接至另一棵樹上 , 否則將會導致樹的結(jié)構(gòu)的混亂 .9.39void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)/把二叉排序樹 T分裂為兩棵二叉排序樹 A和B,其中A的元素全部小于等于x,B的元素全部大于x if(T->lchild) BSTree_Split(T->lchild,A,B,x);if(T->rchild) BSTree_Split(T->rchild,A,B,x); /分裂左右子樹if(T->data<=x) Insert_Node(A,T);else Insert_Node(B,T); / 將元素結(jié)點插入合適的樹中/BSTree_Splitvoid Insert_Node(Bitree &T,BTNode *S)/ 把樹結(jié)點 S 插入至 T 的合適位置上 if(!T) T=S; /考慮到剛開始分裂時樹 A和樹B為空的情況else if(S->data>T->data) / 其余部分與上一題同if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S);else if(S->data<T->data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchild=NULL;S->rchild=NULL;/Insert_Key9.40typedef struct int data;int bf;int lsize; /lsize域表示該結(jié)點的左子樹的結(jié)點總數(shù)加 1BlcNode *lchild,*rchild; BlcNode,*BlcTree; / 含 lsize 域的平衡二叉排序樹類型BTNode *Locate_BlcTree(BlcTree T,int k)/ 在含 lsize 域的平衡二叉排序樹 T中確定第k小的結(jié)點指針if(!T) return NULL; /k 小于 1 或大于樹結(jié)點總數(shù)if(T->lsize=k) return T; / else if(T->lsize>k)就是這個結(jié)點return Locate_BlcTree(T->lchild,k); /在左子樹中尋找else return Locate_BlcTree(T->rchild,k-T->lsize);/ 在右子樹中尋找 ,注意要修改 k 的值 /Locate_BlcTree9.41typedef struct enum LEAF,BRANCH tag; / 結(jié)點類型標識int keynum;BPLink parent; /雙親指針int keyMAXCHILD; / 關(guān)鍵字 union BPLinkchildMAXCHILD;/ 非葉結(jié)點的孩子指針struct rectype *infoMAXCHILD;/ 葉子結(jié)點的信息指針BPNode *next; / 指向下一個葉子結(jié)點的鏈接 leaf; BPNode,*BPLink,*BPTree;/B+ 樹及其結(jié)點 類型Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)/B+樹中按關(guān)鍵字隨機查找的算法 , 返回包含關(guān)鍵字的葉子結(jié)點的指針 ptr 以及關(guān)鍵字在葉子 結(jié)點中的位置 posp=T;while(p.tag=BRANCH) / 沿分支向下查找 for(i=0;i<p->keynum&&key>p->keyi;i+); / 確定關(guān)鍵字所在子樹 if(i=p->keynum) return ERROR; /關(guān)鍵字太大p=p->childi; for(i=0;i<p->keynum&&key!=p->keyi;i+); / 在葉子結(jié)點中查找 if(i=p->keynum) return ERROR; /找不到關(guān)鍵字ptr=p;pos=i;return OK;/BPTree_Search9.42void TrieTree_Insert_Key(TrieTree &T,StringType key)/ 在 Trie 樹 T 中插 入字符串 key,StringType 的結(jié)構(gòu)見第四章 q=(TrieNode*)malloc(sizeof(TrieNode); q->kind=LEAF;q->lf.k=key; / 建葉子結(jié)點 klen=key0;p=T;i=1; while(p&&i<=klen&&p->bh.ptrord(keyi) last=p; p=p->bh.ptrord(keyi); i+; / 自上而下查找 if(p->kind=BRANCH) / 如果最后落到分支結(jié)點 ( 無同義詞 ):直接連上葉子p->bh.ptrord(keyi)=q; / p->bh.num+;else / 如果最后落到葉子結(jié)點 ( 有同義詞 ): r=(TrieNode*)malloc(sizeof(TrieNode); / 建立新的分支結(jié)點 last->bh.ptrord(keyi-1)=r; /用新分支結(jié)點取代老葉子結(jié)點和上一層的聯(lián)系r->kind=BRANCH;r->bh.num=2; r->bh.ptrord(keyi)=q;r->bh.ptrord(p->lf.ki)=p; /新分支結(jié)點與新老兩個葉子結(jié)點相連/TrieTree_Insert_Key分析: 當自上而下的查找結(jié)束時 , 存在兩種情況 . 一種情況 , 樹中沒有待插入關(guān)鍵 字的同義詞 , 此時只要新建一個葉子結(jié)點并連到分支結(jié)點上即可 . 另一種情況 , 有 同義詞 , 此時要把同義詞的葉子結(jié)點與樹斷開 , 在斷開的部位新建一個下一層的 分支結(jié)點 , 再把同義詞和新關(guān)鍵字的葉子結(jié)點連到新分支結(jié)點的下一層 .9.43Status TrieTree_Delete_Key(TrieTree &T,StringType key)/在 Trie 樹 T 中刪除字符串 keyp=T;i=1;while(p&&p->kind=BRANCH&&i<=key0) / 查找待刪除元素 last=p; p=p->bh.ptrord(keyi); i+;if(p&&p->kind=LEAF&&p->lf.k=key) /找到了待刪除元素 last->bh.ptrord(keyi-1)=NULL; free(p); return OK;else return ERROR; / 沒找到待刪除元素 /TrieTree_Delete_Key9.44void Print_Hash(HashTable H)/ 按第一個字母順序輸出 Hash 表中的所有關(guān)鍵 字, 其中處理沖突采用線性探測開放定址法for(i=1;i<=26;i+) for(j=i;H.elemj.key;j=(j+1)%hashsizesizeindex) /線性探測 if(H(H.elemj.key)=i) printf("%sn",H.elemj);/Print_Hashint H(char *s)/求 Hash 函數(shù)if(s) return s0-96; / 求關(guān)鍵字第一個字母的字母序號 ( 小寫 ) else return 0;/H9.45typedef *LNodeMAXSIZE CHashTable; / 鏈地址 Hash 表類型Status Build_Hash(CHashTable &T,int m)輸入一組關(guān)鍵字,建立 Hash表,表長為m,用鏈地址法處理沖突.if(m<1) return ERROR;T=malloc(m*sizeof(WORD); / 建立表頭指針向量 for(i=0;i<m;i+) Ti=NULL;while(key=Inputkey()!=NULL) / 假定 Inputkey 函數(shù)用于從鍵盤輸入關(guān) 鍵字 q=(LNode*)malloc(sizeof(LNode); q->data=key;q->next=NULL;n=H(key);if(!Tn) Tn=q; / 作為鏈表的第一個結(jié)點else for(p=Tn;p->next;p=p->next); p->next=q; / 插入鏈表尾部 . 本算法不考慮排序問題 ./whilereturn OK;/Build_Hash9.46Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)/ 根據(jù)行列值在Hash表表示的稀疏矩陣中確定元素 key的位置k h=2*(100*(row/10)+col/10); / 作者設(shè)計的 Hash 函數(shù) while(H.elemh.key&&!EQ(H.elemh.key,key) h=(h+1)%20000;if(EQ(H.elemh.key,key) k=h;else k=NULL;/Locate_Hash分析：本算法所使用的Hash表長20000,裝填因子為50%,Hash函數(shù)為行數(shù)前兩位 和列數(shù)前兩位所組成的四位數(shù)再乘以二 , 用線性探測法處理沖突 . 當矩陣的元素 是隨機分布時 , 查找的時間復雜度為 O(1).另解：第九章 查找習題及答案題號： 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16 17 1819 20 21 22 23一、基礎(chǔ)知識題1. 對含有 n 個互不相同元素的集合，同時找最大元和最小元至少需進行多少次比較?答：我們可以設(shè)立兩個變量max和min用于存放最大元和最小元 (的位置)，第一次取兩個元素進行比較，大的放入max，小的放入 min，從第2次開始，每次取一個元素先和max比較，如果大于 max則以它替換 max并結(jié)束本次比較；若小于 max則再與min相比較，在最好的情況下，一路比較下去都不用和 min 相比較，所以這種情況下，至少要進行 n-1 次比較就能找到最大元和最小元。 (順便說一下，最壞情況下，要進行 2n-3 次比較才能得到結(jié)果 )2. 若對具有 n 個元素的有序的順序表和無序的順序表分別進行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度：(1) 查找不成功，即表中無關(guān)鍵字等于給定值 K 的記錄； (2) 查找成功，即表中有關(guān)鍵字等于給定值 K 的記錄。答：查找不成功時，需進行n+1次比較才能確定查找失敗。因此平均查找長度為n+1，這時有序表和無序表是一樣的。查找成功時，平均查找長度為 (n+1)/2, 有序表和無序表也是一樣的。因為順序查找對表的原始序列的有序性不感興趣。3. 畫出對長度為 18的有序的順序表進行二分查找的判定樹，并指出在等概率時查找成功的平均查找長度，以及查找失敗時所需的最多的關(guān)鍵字比較次數(shù)。答：請看題圖。等概率情況下，查找成功的平均查找長度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556也可以用公式代，大約為： ASL=(18+1)lg(18+1)/18-1=3.346查找失敗時，最多的關(guān)鍵字比較次樹不超過判定樹的深度，此處為5. 如圖：4. 為什么有序的單鏈表不能進行折半查找 ?答： 因為鏈表無法進行隨機訪問，如果要訪問鏈表的中間結(jié)點，就必須先從頭結(jié)點開始進行依次訪問， 這就要浪費很多時間， 還不如進行順序查找，而且，用鏈存儲結(jié)構(gòu)將無法判定二分的過程是否結(jié)束，因此無法用鏈表實現(xiàn)二分查找。5. 設(shè)有序表為 (a,b,c,e,f,g,i,j,k,p,q),請分別畫出對給定值 b,g 和 n 進行折半查找的過程。解： b 的查找過程如下 (其中括號表示當前查找區(qū)間，圓括號表示當前比較的關(guān)鍵字)下標：1 23 4 5 67 8 9 10 11 12 13第一次比較： a bc d e f (g) h ij k p q第二次比較：a b (c)d e f gh ijkpq第三次比較：a(b)c d e fgh ijkpq經(jīng)過三次比較，查找成功。g 的查找過程如下：a b c d e f (g) h i j k p q一次比較成功。n 的查找過程如下：下標：1 2第一次比較： a b第二次比較：a b第三次比較：a b第四次比較：a b3 4 5 67 8 9 10c d e f (g) h ijc d e fg h i (j)c d e f gh ic d e fg h i11 12 13k p qk p qjk (p) qj k p q經(jīng)過四次比較，查找失敗。6. 將(for, case, while, class, protected, virtual, public,private, do, template, const ,if,int)中的關(guān)鍵字依次插入初態(tài)為空的二叉排序樹中，請畫岀所得到的樹T。然后畫岀刪去for之后的二叉排序樹T',若再將for插入T'中得到的二叉排序樹T''是否與T相同？最后給岀T"的先序、中序和后序序列。答：見題圖 :T"的先序序列是： do case class const while protected private iffor int virtualpublic templateT"的中序序列是：case class const do for if int privateprotected public template virtual whileT"的后序序列是：const class case for int if private templatepublic virtual protected while do二叉排序樹 T 如下圖：刪去 for 后的二叉排序樹如下圖：圈內(nèi)的 for 表示再插入后的結(jié)點：7. 對給定的關(guān)鍵字集合，以不同的次序插入初始為空的樹中，是否有可能得到同一棵二叉排序樹？答：有可能。如有兩個序列： 3， 1， 2， 4 和 3 ， 4， 1， 2，它們插入空樹所得的二叉排序樹是相同的。8. 將二叉排序樹 T的先序序列中的關(guān)鍵字依次插入一空樹中，所得和二叉排序樹T'與T"是否相同？為什么？答：這兩棵二叉樹完全相同。9. 設(shè)二叉排序樹中關(guān)鍵字由 1至1000 的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為 363的結(jié)點，下述關(guān)鍵字序列哪一個不可能是在二叉排序樹上查找到的序列(a) 2 ， 252， 401 ， 398， 330, 344 ， 397， 363；(c) 925, 202, 911, 240, 912, 245, 363;(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.答： (c) 是不可能查找到的序列。我們可以把這四個序列各插入到一個初始為空的二叉排序樹中，結(jié)果可以發(fā)現(xiàn)， (c) 序列所形成的不是一條路徑，而是有分支的，可見它是不可能在查找過程中訪問到的序列。10. 設(shè)二叉排序樹中關(guān)鍵字互不相同，則其中最小元必無左孩子，最大元必無右孩子。此命題是否正確?最小元和最大元一定是葉子嗎?一個新結(jié)點總是插在二叉排序樹的某葉子上嗎 ?答：此命題正確。假設(shè)最小元有左孩子，則根據(jù)二叉排序樹性質(zhì)，此左孩子應比最小元更小，如此一來就產(chǎn)生矛盾了，因此最小元不可能有左孩子，對于最大元也是這個道理。但最大元和最小元不一定是葉子，它也可以是根、內(nèi)部結(jié)點 ( 分支結(jié)點 ) 等，這得根據(jù)插入結(jié)點時的次序而定。如3，1， 2，4這個集合，根據(jù)不同的插入次序可以得到不同的二叉排序樹：03/ 01 040202/ 0103040403020102/ 03新結(jié)點總是插入在二叉排序樹的某個葉子上的。?若刪去某結(jié)點中的一個關(guān)鍵字，而導致結(jié)點11. 在一棵m階的B-樹中，當將一關(guān)鍵字插入某結(jié)點而引起該結(jié)點的分裂時，此結(jié)點原有多少個關(guān)鍵字合并時，該結(jié)點中原有幾個關(guān)鍵字答：在此樹中，若由于一關(guān)鍵字的插入某結(jié)點而引起該結(jié)點的分裂時，則該結(jié)點原有m-1 個關(guān)鍵字。若刪去某結(jié)點中一個關(guān)鍵字而導致結(jié)點合并時，該結(jié)點中原有廠m/2q-1個關(guān)鍵字。12. 在一棵B-樹中，空指針數(shù)總是比關(guān)鍵字數(shù)多一個，此說法是否正確？請問包含8個關(guān)鍵字的3階B-樹(即2-3樹)最多有幾個結(jié)點？最少有幾個結(jié)點？畫出這兩種情況的B-樹。答：這個說法是正確的。包含8個關(guān)鍵字的3階B-樹最多有7個結(jié)點，最少有 4個結(jié)點。見題圖。 : 圖如下：13. 從空樹開始，依次輸入20 , 30, 50 , 52 ,60 , 68, 70，畫出建立2-3樹的過程。并畫出刪除50和68后的B-樹狀態(tài)。答：過程如下：(1) 插入 20, 30： (2) 插入 50：(3) 插入 52： (4)插入 60：(5) 插入 68： (6)插入 70：(7) 刪去 50： (8) 刪去 6814。畫出依次插入 z,v,o,p,w,y 到圖9.12(h)所示的5階B-樹的過程。答：如圖：第一步,插入 z:第二、三步 , 插入 v,o ：第四五六步,插入 p,w,y:15. 在含有n個關(guān)鍵字的m階B-樹中進行查找，至多讀盤多少次？完全平衡的二叉排序樹的讀盤次數(shù)大約比它大多少倍？答：在含有n個關(guān)鍵字的 m階B-樹中進行查找至多讀盤次數(shù)不超過B-樹高h,即logt(n+1)/2)+1,(注，此處t為底，值是除根外的每個內(nèi)部結(jié)點的最小度數(shù)廠m/2n ).完全平衡的二叉樹高為lgn,所以它的讀盤次數(shù)至多也是lgn，它與上述B-樹的讀盤次數(shù)的比值約為lgt倍(此處底是2).16. 為什么在內(nèi)存中使用的B-樹通常是3階的，而不使用更高階的B-樹？答：因為查找等操作的cpu時間在B-樹上是O(lgn ? (m/lgt), 而m/lgt>1,所以m較大時它所費時間比平衡的二叉排序樹上相應操作時間大得多，因此，僅在內(nèi)存中使用的B-樹通常取最小值3.17. 為什么二叉排序樹長高時，新結(jié)點總是一個葉子，而B-樹長高時，新結(jié)點總是根？哪一種長高能保證樹平衡？答：因為在二叉排序樹中，關(guān)鍵字總是作為一個葉子結(jié)點插入以原來的樹中，所以當樹增高時，新結(jié)點總是一個葉子；而B-樹中關(guān)鍵字插入總是插入到葉子結(jié)點內(nèi)部，在葉結(jié)點中的關(guān)鍵字數(shù)目尚未超過它能夠容納的數(shù)目之前是不會增加結(jié)點的，當關(guān)鍵字數(shù)超過結(jié)點可容納的數(shù)目時，葉結(jié)點就時，才能引起樹高增加，此時產(chǎn)生一個新的根結(jié)點。所以說B 樹長高時，新結(jié)點總是根。顯然，后一種長高總能保證樹的平衡。18. 已知關(guān)鍵字序列為 (PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT) 試為它們設(shè)計一個散列函數(shù)，將其映射到區(qū)間0.n-1 上，要求碰撞盡可能的少。這里 n=11,13,17,19.解：我的設(shè)計的散列函數(shù)是這樣的，把關(guān)鍵字串中的每一個字符按其所在位置分別將其 ASCII 值乘以一個不同的數(shù)，然后把這些值相加的和去對 n 求余，余數(shù)即為散列表中的位置。函數(shù)如下：int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;我們可以設(shè)計一個程序來看看用這個散列函數(shù)得到的所有關(guān)鍵字映射到區(qū)間的位置：#include <stdio.h>#define n 11 file&#58/ 先用 11 來代入，我們可以用13， 17，19 依次代入驗證int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;file&#58/ 此處我用了系數(shù) 1， 0.618 和 10，你也可以用其他的數(shù)代入看有沒有更好的系數(shù)void main()chars104="PAL","LAP","PAM","MAP","PAT","PET","SET","SAT","TAT","BAT"/ 以上用一個二維數(shù)組來存放關(guān)鍵字序列int i;for(i=0; i<10;i+)printf("%d ",Hash(s );19. 對于一組給定的、固定不變的關(guān)鍵字序列，有可能設(shè)計出無沖突的散列函數(shù)H,此時稱H為完備的散列函數(shù)(perfecthashing function)，若H能無沖突地將關(guān)鍵字完全填滿散列表，則稱H是最小完備(minimalperfect) 的散列函數(shù)。通常找完備的散列函數(shù)非常困難，找最小完備的散列函數(shù)就更困難。請問：(1)若h是已知關(guān)鍵字集合K的完備的散列函數(shù)，若要增加一個新的關(guān)鍵字到集合K 一般情況下H還是完備的嗎？已知關(guān)鍵字集合為(81 ,129, 301，38, 434, 216, 412, 487, 234)，散列函數(shù)為H(x)=(x+18)/63,請問H是完備的嗎？它是最小完備的嗎？(3) 考慮由字符串構(gòu)成的關(guān)鍵字集合 (Bret,Jane,Shirley,Bryce,Michelle,Heather)，試為散列表 0.6 設(shè)計一個完備的散列函數(shù)。 (提示：考慮每個字符串的第 3 個字符，即 s2)答：(1)一般情況下H不是完備的，如果說插入一個新的關(guān)鍵字它還是完備的，那么再插入一個呢？它豈不是永遠是完備的散列函數(shù)了 ？所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。這個H是完備的，其函數(shù)值依次為：1, 2，5，0, 7，3，6, 8, 4。如果散列表長m=90寸，它就是最小完備的。(3) 這個函數(shù)如下：int Hash (char key) return key2%7;20. 設(shè)散列函數(shù)為h(key)=key%101,解決沖突的方法為線性探查，表中用"-1"表示空單元。若刪去散列表HT中的304(即令HT1=-1)之后，在表HT中查找 70 7將會發(fā)生什么 ？若將刪去的表項標記為 "-2", 查找時探查到 -2 繼續(xù)向前搜索，探查到 -1 時終止搜索。請問用這種方法刪 304后能否正確地查找到 707？0123100HT | 202 | 304 | 507 | 707 |答：查找 707時，首先根據(jù)散列函數(shù)計算得出該元素應在散列表中的 0單元，但是在 0單元沒有找到，因此將向下一單元探查，結(jié)果發(fā)現(xiàn)該單元是-1( 為空單元)，所以結(jié)束查找，這將導致 707無法找到。如果改用"-2" 作為刪除標記，則可以正確找到 707所在的結(jié)點。21. 設(shè)散列表長度為11,散列函數(shù)h(x)=x%11,給定的關(guān)鍵字序列為：1，13，13, 34, 38, 33, 27，22.試畫出分別用拉鏈法和線性探查法解決沖突 時所構(gòu)造的散列表，并求出在等概率情況下，這兩咱方法查找成功和失敗時的平均查找長度。請問裝填因子的值是什么 ？ 答：拉鏈法如下圖： (后面的框框就不畫了 )T0.101 | f 1 f 12 f 34 人2 | f 13 人下標6 I 卜' I7 I 卜' I8 I 卜' I9 I 卜' I10 I 卜' I線性探查法如下圖：012345678910T0.10 I 33I 1 I 13I 12I 34I 38I 27I 22I探查次數(shù) 11134178用拉鏈法的查找成功平均查找長度為：ASLscuu=(1*4+2*3+3*1)/8=1.625查找失敗時平均查找長度為：ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73用線性探查法查找成功時平均查找長度為：查找失敗時平均查找長度為：ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3裝填因子a拉鏈=4/1仁0.36 a線性探查=8/11=0.7322. 假定有k個關(guān)鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進行多少次探查?答：至少要進行 1+2+3.+k-1+k 次探查。也就是說，在散列表的一連串連續(xù)空間內(nèi)，第一個關(guān)鍵字只需探查一次，第二個就要探查2次，如此這般，第k個關(guān)鍵字就要探查k次才能找到位置存放。所以至少要把它們?nèi)悠饋聿艍颉?3. 為什么說當裝填因子非常接近 1 時，線性探查類似于順序查找 ?為什么說當裝填因子比較小 (比如 a=0.7 左右)時，散列查找的平均查找時間為O(1)?答：當 a 非常接近 1 時，整個散列表幾乎被裝滿。由于線性探查法在關(guān)鍵字同義時解決沖突的辦法是線性地向后查找，當整個表幾乎裝滿時，它 就很類似于順序查找了。當 a 比較小時，關(guān)鍵字碰撞的幾率比較小，一般情況下只要按照散列函數(shù)計算出的結(jié)果能夠 1 次性就找到相應結(jié)點，因此它的平均查找時間接近于1.