《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找

《《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找（20頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第九章 查找 9.25 int Search_Sq(SSTable ST,int key)// 在有序表上順序查找的算法 , 監(jiān)視哨設(shè)在 高下標(biāo)端 { ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++); if(i>ST.length||ST.elem[i].key

2、ursive(SSTable ST,int key,int low,int high)// 折半查 找的遞歸算法 { if(low>high) return 0; // 查找不到時(shí)返回 0 mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST,key,low,mid-1); else return Search_Bin_Recursive(ST,key,mid+1,high); } }//Searc

3、h_Bin_Recursive 9.27 int Locate_Bin(SSTable ST,int key)// 折半查找 , 返回小于或等于待查元素的 最后一個(gè)結(jié)點(diǎn)號(hào) { int *r; r=ST.elem; if(key=r[ST.length].key) return ST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key>=r[mid].key&&key

4、eturn mid; else if(key

5、m; // 塊的數(shù)目 } IdxSqList; // 索引順序表類型 int Search_IdxSeq(IdxSqList L,int key)// 分塊查找 , 用折半查找法確定記錄 所在塊 , 塊內(nèi)采用順序查找法 { if(key>L.idx[L.blknum].maxkey) return ERROR; // 超過(guò)最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found) // 折半查找記錄所在塊號(hào) mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.i

6、dx[mid-1].maxkey) found=1; else if(key>L.idx[mid].maxkey) low=mid+1; else high=mid-1; } i=L.idx[mid].firstloc; // 塊的下界 j=i+blksize-1; // 塊的上界 temp=L.elem[i-1]; // 保存相鄰元素 L.elem[i-1]=key; // 設(shè)置監(jiān)視哨 for(k=j;L.elem[k]!=key;k--); // 順序查找 L.elem[i-1]=temp; // 恢復(fù)元素 if(k

7、k; }//Search_IdxSeq 分析: 在塊內(nèi)進(jìn)行順序查找時(shí) , 如果需要設(shè)置監(jiān)視哨 , 則必須先保存相鄰塊的相鄰 元素, 以免數(shù)據(jù)丟失 . 9.29 typedef struct { LNode *h; //h 指向最小元素 LNode *t; //t 指向上次查找的結(jié)點(diǎn) } CSList; LNode *Search_CSList(CSList &L,int key)// 在有序單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上的 查找算法 , 假定每次查找都成功 { if(L.t->data==key) return L.t; else if(L.t->data>key) for(p=L

8、.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 分析: 由于題目中假定每次查找都是成功的 , 所以本算法中沒(méi)有關(guān)于查找失敗的 處理. 由微積分可得 , 在等概率情況下 , 平均查找長(zhǎng)度約為 n/3. 9.30 typedef struct { DLNode *pre; int data; DLNode *next; } DLNode; typedef str

9、uct { DLNode *sp; int length; } DSList; // 供查找的雙向循環(huán)鏈表類型 DLNode*Search_DSList(DSList &L,int key)// 在有序雙向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上 的查找算法 , 假定每次查找都成功 { p=L.sp; if(p->data>key) { while(p->data>key) p=p->pre; L.sp=p; } else if(p->datadatanext; L.sp=p; } return p; }//Search_

10、DSList 分析: 本題的平均查找長(zhǎng)度與上一題相同 , 也是 n/3. 9.31 int last=0,flag=1; int Is_BSTree(Bitree T)// 判斷二叉樹(shù) T 是否二叉排序樹(shù) , 是則返回 1, 否則返 回0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->datadata; if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree 9.32

11、int last=0; void MaxLT_MinGT(BiTree T,int x)// 找到二叉排序樹(shù) T 中小于 x 的最大元素和 大于 x 的最小元素 { if(T->lchild) MaxLT_MinGT(T->lchild,x); // 本算法仍是借助中序遍歷來(lái) 實(shí)現(xiàn) if(lastdata>=x) // 找到了小于 x 的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x) // 找到了大于 x 的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rc

12、hild) MaxLT_MinGT(T->rchild,x); }//MaxLT_MinGT 9.33 從大到小輸出二叉排序樹(shù) T 中所有不小于 x void Print_NLT(BiTree T,int x)// 的元素 if(T->rchild) Print_NLT(T->rchild,x); if(T->datadata); if(T->lchild) Print_NLT(T->lchild,x); // 先右后左的中序遍歷 }//Print_NLT 9.34 vo

13、id Delete_NLT(BiTree &T,int x)// 刪除二叉排序樹(shù) T 中所有不小于 x 元素結(jié) 點(diǎn), 并釋放空間 { if(T->rchild) Delete_NLT(T->rchild,x); if(T->datalchild; free(q); // 如果樹(shù)根不小于 x, 則刪除樹(shù)根 , 并以左子樹(shù)的根作為新的樹(shù)根 if(T) Delete_NLT(T,x); // 繼續(xù)在左子樹(shù)中執(zhí)行算法 }//Delete_NLT 9.35 void Print_Between(Bi

14、ThrTree T,int a,int b)// 打印輸出后繼線索二叉排序 樹(shù) T 中所有大于 a 且小于 b 的元素 { p=T; while(!p->ltag) p=p->lchild; // 找到最小元素 while(p&&p->datadata>a) printf("%d\n",p->data); // 輸出符合條件的元素 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } // 轉(zhuǎn)到中序后繼 }//while }//Print_Between

15、 9.36 void BSTree_Insert_Key(BiThrTree &T,int x)// 在后繼線索二叉排序樹(shù) T 中插 入元素 x { if(T->datartag) //T 沒(méi)有右子樹(shù)時(shí) , 作為右孩子插入 { 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);

16、//T 有右子樹(shù)時(shí) , 插入右子樹(shù) 中 }//if else if(T->data>x) // 插入到左子樹(shù)中 { if(!T->lchild) //T 沒(méi)有左子樹(shù)時(shí) , 作為左孩子插入 { 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 有左子樹(shù)時(shí) , 插入左子樹(shù) 中 }//if }//BSTree_Insert_Key 9.37 S

17、tatus BSTree_Delete_key(BiThrTree &T,int x)// 在后繼線索二叉排序樹(shù) T 中刪除元素 x { BTNode*pre,*ptr,*suc;//ptr 為 x 所在結(jié)點(diǎn) ,pre 和 suc 分別指向 ptr 的前 驅(qū)和后繼 p=T;last=NULL; //last 始終指向當(dāng)前結(jié)點(diǎn) p 的前一個(gè) ( 前驅(qū) ) while(!p->ltag) p=p->lchild; // 找到中序起始元素 while(p) { if(p->data==x) // 找到了元素 x 結(jié)點(diǎn) { pre=last; ptr=p; } else if

18、(last&&last->data==x) suc=p; // 找到了 x 的后繼 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } // 轉(zhuǎn)到中序后繼 last=p; }//while // 借助中序遍歷找到元素 x 及其前驅(qū)和后繼結(jié)點(diǎn) if(!ptr) return ERROR; // 未找到待刪結(jié)點(diǎn) Delete_BSTree(ptr); // 刪除 x 結(jié)點(diǎn) if(pre&&pre->rtag) pre->rchild=suc; // 修改線索 return OK

19、; }//BSTree_Delete_key void Delete_BSTree(BiThrTree &T)// 課本上給出的刪除二叉排序樹(shù)的子樹(shù) T 的算法 , 按照線索二叉樹(shù)的結(jié)構(gòu)作了一些改動(dòng) { q=T; if(!T->ltag&&T->rtag) // 結(jié)點(diǎn)無(wú)右子樹(shù) , 此時(shí)只需重接其左子樹(shù) T=T->lchild; else if(T->ltag&&!T->rtag) // 結(jié)點(diǎn)無(wú)左子樹(shù) , 此時(shí)只需重接其右子樹(shù) T=T->rchild; else if(!T->ltag&&!T->rtag) // 結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù) { p=T;r=T->lchild

20、; while(!r->rtag) { s=r; r=r->rchild; // 找到結(jié)點(diǎn)的前驅(qū) r 和 r 的雙親 s } T->data=r->data; // 用 r 代替 T 結(jié)點(diǎn) if(s!=T) s->rchild=r->lchild; else s->lchild=r->lchild; // 重接 r 的左子樹(shù)到其雙親結(jié)點(diǎn)上 q=r; }//else free(q); // 刪除結(jié)點(diǎn) }//Delete_BSTree 分析: 本算法采用了先求出 x 結(jié)點(diǎn)的前驅(qū)和后繼 , 再刪除 x 結(jié)點(diǎn)的辦法 , 這樣修改 線索時(shí)會(huì)比較簡(jiǎn)單 , 直接讓前驅(qū)的線索指向后

21、繼就行了 . 如果試圖在刪除 x 結(jié)點(diǎn) 的同時(shí)修改線索 , 則問(wèn)題反而復(fù)雜化了 . 9.38 void BSTree_Merge(BiTree &T,BiTree &S)〃 把二叉排序樹(shù) S合并至U T 中 { if(S->lchild) BSTree_Merge(T,S->lchild); if(S->rchild) BSTree_Merge(T,S->rchild); // 合并子樹(shù) Insert_Key(T,S); // 插入元素 }//BSTree_Merge void Insert_Node(Bitree &T,BTNode *S)// 把樹(shù)結(jié)點(diǎn) S 插入至 T 的合適

22、位置上 { if(S->data>T->data) { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S); } else if(S->datadata) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL; // 插入的新結(jié)點(diǎn)必須和原來(lái)的左右子樹(shù)斷絕關(guān)系 S->rchild=NULL; // 否則會(huì)導(dǎo)致樹(shù)結(jié)構(gòu)的混亂 }//Insert_Node 分析: 這是一個(gè)與課本上不同的插入算法 . 在

23、合并過(guò)程中 , 并不釋放或新建任何結(jié) 點(diǎn), 而是采取修改指針的方式來(lái)完成合并 . 這樣, 就必須按照后序序列把一棵樹(shù)中 的元素逐個(gè)連接至另一棵樹(shù)上 , 否則將會(huì)導(dǎo)致樹(shù)的結(jié)構(gòu)的混亂 . 9.39 void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)// 把二叉排序樹(shù) T 分裂為兩棵二叉排序樹(shù) 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); /

24、/ 分裂左右子樹(shù) if(T->data<=x) Insert_Node(A,T); else Insert_Node(B,T); // 將元素結(jié)點(diǎn)插入合適的樹(shù)中 }//BSTree_Split void Insert_Node(Bitree &T,BTNode *S)// 把樹(shù)結(jié)點(diǎn) S 插入至 T 的合適位置上 { if(!T) T=S; // 考慮到剛開(kāi)始分裂時(shí)樹(shù) A和樹(shù)B為空的情況 else if(S->data>T->data) // 其余部分與上一題同 { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S)

25、; else if(S->datadata) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key 9.40 typedef struct { int data; int bf; int lsize; //lsize 域表示該結(jié)點(diǎn)的 左子樹(shù)的結(jié)點(diǎn)總數(shù)加 1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; // 含 lsize 域的平衡 二叉排序樹(shù)類型

26、 BTNode *Locate_BlcTree(BlcTree T,int k)// 在含 lsize 域的平衡二叉排序樹(shù) T中確定第k小的結(jié)點(diǎn)指針 { if(!T) return NULL; //k 小于 1 或大于樹(shù)結(jié)點(diǎn)總數(shù) if(T->lsize==k) return T; // else if(T->lsize>k) 就是這個(gè)結(jié)點(diǎn) return Locate_BlcTree(T->lchild,k); // 在左子樹(shù)中尋找 else return Locate_BlcTree(T->rchild,k-T->lsize); // 在右子樹(shù)中尋找 , 注意要修改 k 的

27、值 }//Locate_BlcTree 9.41 typedef struct { enum {LEAF,BRANCH} tag; // 結(jié)點(diǎn)類 型標(biāo)識(shí) int keynum; BPLink parent; // 雙親指針 int key[MAXCHILD]; // 關(guān)鍵字 union { BPLink child[MAXCHILD];// 非葉結(jié)點(diǎn)的孩子指針 struct { rectype *info[MAXCHILD];// 葉子結(jié)點(diǎn)的信息指針 BPNode *next; // 指向下一個(gè)葉子結(jié)點(diǎn)的鏈接 } leaf; } } BPNode,*B

28、PLink,*BPTree;//B+ 樹(shù)及其結(jié)點(diǎn) 類型 Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+ 樹(shù)中按關(guān) 鍵字隨機(jī)查找的算法 , 返回包含關(guān)鍵字的葉子結(jié)點(diǎn)的指針 ptr 以及關(guān)鍵字在葉子 結(jié)點(diǎn)中的位置 pos { p=T; while(p.tag==BRANCH) // 沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++); // 確定關(guān)鍵字所在子樹(shù) if(i==p->keynum) return ERROR; // 關(guān)鍵字太大 p=p->child

29、[i]; } for(i=0;ikeynum&&key!=p->key[i];i++); // 在葉子結(jié)點(diǎn)中查找 if(i==p->keynum) return ERROR; // 找不到關(guān)鍵字 ptr=p;pos=i; return OK; }//BPTree_Search 9.42 void TrieTree_Insert_Key(TrieTree &T,StringType key)// 在 Trie 樹(shù) T 中插 入字符串 key,StringType 的結(jié)構(gòu)見(jiàn)第四章 { q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind

30、=LEAF; q->lf.k=key; // 建葉子結(jié)點(diǎn) klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; } // 自上而下查找 if(p->kind==BRANCH) // 如果最后落到分支結(jié)點(diǎn) ( 無(wú)同義詞 ): 直接連上葉子 { p->bh.ptr[ord(key[i])]=q; // p->bh.num++; } else // 如果最后落到葉子結(jié)點(diǎn) ( 有同義詞 ): { r=(TrieNode*)mal

31、loc(sizeof(TrieNode)); // 建立新的分支結(jié)點(diǎn) last->bh.ptr[ord(key[i-1])]=r; // 用新分支結(jié)點(diǎn)取代老葉子結(jié)點(diǎn)和 上一層的聯(lián)系 r->kind=BRANCH;r->bh.num=2; r->bh.ptr[ord(key[i])]=q; r->bh.ptr[ord(p->lf.k[i])]=p; // 新分支結(jié)點(diǎn)與新老兩個(gè)葉子結(jié)點(diǎn) 相連 } }//TrieTree_Insert_Key 分析: 當(dāng)自上而下的查找結(jié)束時(shí) , 存在兩種情況 . 一種情況 , 樹(shù)中沒(méi)有待插入關(guān)鍵 字的同義詞 , 此時(shí)只要新建一個(gè)葉子結(jié)點(diǎn)并連到分支結(jié)點(diǎn)上

32、即可 . 另一種情況 , 有 同義詞 , 此時(shí)要把同義詞的葉子結(jié)點(diǎn)與樹(shù)斷開(kāi) , 在斷開(kāi)的部位新建一個(gè)下一層的 分支結(jié)點(diǎn) , 再把同義詞和新關(guān)鍵字的葉子結(jié)點(diǎn)連到新分支結(jié)點(diǎn)的下一層 . 9.43 Status TrieTree_Delete_Key(TrieTree &T,StringType key)// 在 Trie 樹(shù) T 中 刪除字符串 key { p=T;i=1; while(p&&p->kind==BRANCH&&i<=key[0]) // 查找待刪除元素 { last=p; p=p->bh.ptr[ord(key[i])]; i++; } if(p&&p->kind

33、==LEAF&&p->lf.k=key) // 找到了待刪除元素 { last->bh.ptr[ord(key[i-1])]=NULL; free(p); return OK; } else return ERROR; // 沒(méi)找到待刪除元素 }//TrieTree_Delete_Key 9.44 void Print_Hash(HashTable H)// 按第一個(gè)字母順序輸出 Hash 表中的所有關(guān)鍵 字, 其中處理沖突采用線性探測(cè)開(kāi)放定址法 { for(i=1;i<=26;i++) for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeind

34、ex]) // 線性探測(cè) if(H(H.elem[j].key)==i) printf("%s\n",H.elem[j]); }//Print_Hash int H(char *s)// 求 Hash 函數(shù) { if(s) return s[0]-96; // 求關(guān)鍵字第一個(gè)字母的字母序號(hào) ( 小寫(xiě) ) else return 0; }//H 9.45 typedef *LNode[MAXSIZE] CHashTable; // 鏈地址 Hash 表類型 Status Build_Hash(CHashTable &T,int m)〃 輸入一組關(guān)鍵字,建立 Hash表,表 長(zhǎng)為

35、m,用鏈地址法處理沖突. { if(m<1) return ERROR; T=malloc(m*sizeof(WORD)); // 建立表頭指針向量 for(i=0;idata=key;q->next=NULL; n=H(key); if(!T[n]) T[n]=q; // 作為鏈表的第一個(gè)結(jié)點(diǎn) else { for(p=T[n];p->next;

36、p=p->next); p->next=q; // 插入鏈表尾部 . 本算法不考慮排序問(wèn)題 . } }//while return OK; }//Build_Hash 9.46 Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)// 根據(jù)行列值在Hash表表示的稀疏矩陣中確定元素 key的位置k { h=2*(100*(row/10)+col/10); // 作者設(shè)計(jì)的 Hash 函數(shù) while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1)%2000

37、0; if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash 分析：本算法所使用的Hash表長(zhǎng)20000,裝填因子為50%,Hash函數(shù)為行數(shù)前兩位 和列數(shù)前兩位所組成的四位數(shù)再乘以二 , 用線性探測(cè)法處理沖突 . 當(dāng)矩陣的元素 是隨機(jī)分布時(shí) , 查找的時(shí)間復(fù)雜度為 O(1). 另解： 第九章 查找 習(xí)題及答案 題號(hào)： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 一、基礎(chǔ)知識(shí)題 1. 對(duì)含有 n 個(gè)互不相同元素的集合，同時(shí)找最大元和最

38、小元至少需進(jìn)行多少次比較 ? 答：我們可以設(shè)立兩個(gè)變量 max和min用于存放最大元和最小元 (的位置)，第一次取兩個(gè)元素進(jìn)行比較，大的放入 max，小的放入 min，從第2次 開(kāi)始，每次取一個(gè)元素先和 max比較，如果大于 max則以它替換 max并結(jié)束本次比較；若小于 max則再與min相比較，在最好的情況下，一路比 較下去都不用和 min 相比較，所以這種情況下，至少要進(jìn)行 n-1 次比較就能找到最大元和最小元。 (順便說(shuō)一下，最壞情況下，要進(jìn)行 2n-3 次比較 才能得到結(jié)果 ) 2. 若對(duì)具有 n 個(gè)元素的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討

39、論兩者在等概率時(shí)的平均查找長(zhǎng)度： (1) 查找 不成功，即表中無(wú)關(guān)鍵字等于給定值 K 的記錄； (2) 查找成功，即表中有關(guān)鍵字等于給定值 K 的記錄。 答：查找不成功時(shí)，需進(jìn)行 n+1次比較才能確定查找失敗。因此平均查找長(zhǎng)度為 n+1，這時(shí)有序表和無(wú)序表是一樣的。 查找成功時(shí)，平均查找長(zhǎng)度為 (n+1)/2, 有序表和無(wú)序表也是一樣的。因?yàn)轫樞虿檎覍?duì)表的原始序列的有序性不感興趣。 3. 畫(huà)出對(duì)長(zhǎng)度為 18的有序的順序表進(jìn)行二分查找的判定樹(shù)，并指出在等概率時(shí)查找成功的平均查找長(zhǎng)度，以及查找失敗時(shí)所需的最多的關(guān)鍵字比 較次數(shù)。 答：請(qǐng)看題圖。 等概率情況下，查找成功的平均查找長(zhǎng)度為

40、： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 也可以用公式代，大約為： ASL=(18+1)lg(18+1)/18-1=3.346 查找失敗時(shí)，最多的關(guān)鍵字比較次樹(shù)不超過(guò)判定樹(shù)的深度，此處為 5. 如圖： 4. 為什么有序的單鏈表不能進(jìn)行折半查找 ? 答： 因?yàn)殒湵頍o(wú)法進(jìn)行隨機(jī)訪問(wèn)，如果要訪問(wèn)鏈表的中間結(jié)點(diǎn)， 就必須先從頭結(jié)點(diǎn)開(kāi)始進(jìn)行依次訪問(wèn)， 這就要浪費(fèi)很多時(shí)間， 還不如進(jìn)行順序查找， 而且，用鏈存儲(chǔ)結(jié)構(gòu)將無(wú)法判定二分的過(guò)程是否結(jié)束，因此無(wú)法用鏈表實(shí)現(xiàn)二分查找。 5. 設(shè)有序表為 (a,b,c,e,f,g,i,j,k,p,q), 請(qǐng)分別畫(huà)出對(duì)給定值 b,

41、g 和 n 進(jìn)行折半查找的過(guò)程。 解： b 的查找過(guò)程如下 (其中括號(hào)表示當(dāng)前查找區(qū)間，圓括號(hào)表示當(dāng)前比較的關(guān)鍵字 ) 下標(biāo)： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比較： [a b c d e f (g) h i j k p q] 第二次比較： [a b (c)d e f] g h i j k p q 第三次比較： [a(b)]c d e f g h i j k p q 經(jīng)過(guò)三次比較，查找成功。 g 的查找過(guò)程如下： [a b c d e f (g) h i j k p q] 一次比較成功。 n 的查找過(guò)程如下： 下標(biāo)： 1 2 第

42、一次比較： [a b 第二次比較： a b 第三次比較： a b 第四次比較： a b 3 4 5 6 7 8 9 10 c d e f (g) h i j c d e f g [h i (j) c d e f g h i c d e f g h i 11 12 13 k p q] k p q] j [k (p) q] j [k] p q] 經(jīng)過(guò)四次比較，查找失敗。 6. 將(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)

43、中的關(guān)鍵字依次插入初態(tài)為空的二叉排序樹(shù)中，請(qǐng)畫(huà)岀所得到的樹(shù) T。然后畫(huà)岀刪去for之后的二叉排序樹(shù) T',若再將for 插入T'中得到的二叉排序樹(shù) T''是否與T相同？最后給岀T"的先序、中序和后序序列。 答：見(jiàn)題圖 : T"的先序序列是： do case class const while protected private if for int virtual public template T"的中序序列是： case class const do for if int private protected public template virtual while T"的后

44、序序列是： const class case for int if private template public virtual protected while do 二叉排序樹(shù) T 如下圖： 刪去 for 后的二叉排序樹(shù)如下圖：圈內(nèi)的 for 表示再插入后的結(jié)點(diǎn)： 7. 對(duì)給定的關(guān)鍵字集合，以不同的次序插入初始為空的樹(shù)中，是否有可能得到同一棵二叉排序樹(shù) ？ 答：有可能。如有兩個(gè)序列： 3， 1， 2， 4 和 3 ， 4， 1， 2，它們插入空樹(shù)所得的二叉排序樹(shù)是相同的。 8. 將二叉排序樹(shù) T的先序序列中的關(guān)鍵字依次插入一空樹(shù)中，所得和二叉排序樹(shù) T'與T"是否相同？為什么？

45、 答：這兩棵二叉樹(shù)完全相同。 9. 設(shè)二叉排序樹(shù)中關(guān)鍵字由 1至1000 的整數(shù)構(gòu)成，現(xiàn)要查找關(guān)鍵字為 363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹(shù)上查找到的序列 (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) 是不可能查找到的序列。我們可以把這四個(gè)序列各插入到一個(gè)初始為空的二叉排序樹(shù)中，結(jié)果可以發(fā)現(xiàn)， (c) 序列所形成的不是一條路徑， 而是有

46、分支的，可見(jiàn)它是不可能在查找過(guò)程中訪問(wèn)到的序列。 10. 設(shè)二叉排序樹(shù)中關(guān)鍵字互不相同，則其中最小元必?zé)o左孩子，最大元必?zé)o右孩子。此命題是否正確 ?最小元和最大元一定是葉子嗎 ?一個(gè)新結(jié)點(diǎn) 總是插在二叉排序樹(shù)的某葉子上嗎 ? 答：此命題正確。假設(shè)最小元有左孩子，則根據(jù)二叉排序樹(shù)性質(zhì)，此左孩子應(yīng)比最小元更小，如此一來(lái)就產(chǎn)生矛盾了，因此最小元不可能有左孩子， 對(duì)于最大元也是這個(gè)道理。 但最大元和最小元不一定是葉子，它也可以是根、內(nèi)部結(jié)點(diǎn) ( 分支結(jié)點(diǎn) ) 等，這得根據(jù)插入結(jié)點(diǎn)時(shí)的次序而定。如 3，1， 2，4 這個(gè)集合，根據(jù)不同的插入次序可以得到不同的二叉排序樹(shù)： 03 / \

47、01 04 \ 02 02 / \ 01 03 \ 04 04 \ 03 \ 02 \ 01 02 / \ 03 新結(jié)點(diǎn)總是插入在二叉排序樹(shù)的某個(gè)葉子上的。 ?若刪去某結(jié)點(diǎn)中的一個(gè)關(guān)鍵字，而導(dǎo)致結(jié)點(diǎn) 11. 在一棵m階的B-樹(shù)中，當(dāng)將一關(guān)鍵字插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí)，此結(jié)點(diǎn)原有多少個(gè)關(guān)鍵字 合并時(shí)，該結(jié)點(diǎn)中原有幾個(gè)關(guān)鍵字 答：在此樹(shù)中，若由于一關(guān)鍵字的插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí)，則該結(jié)點(diǎn)原有 m-1 個(gè)關(guān)鍵字。 若刪去某結(jié)點(diǎn)中一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并時(shí)，該結(jié)點(diǎn)中原有廠 m/2q -1個(gè)關(guān)鍵字。 12. 在一棵B-樹(shù)中，空指針數(shù)總

48、是比關(guān)鍵字?jǐn)?shù)多一個(gè)，此說(shuō)法是否正確 ？請(qǐng)問(wèn)包含8個(gè)關(guān)鍵字的3階B-樹(shù)(即2-3樹(shù))最多有幾個(gè)結(jié)點(diǎn)？最少有幾個(gè)結(jié) 點(diǎn)？畫(huà)出這兩種情況的 B-樹(shù)。 答：這個(gè)說(shuō)法是正確的。 包含8個(gè)關(guān)鍵字的3階B-樹(shù)最多有7個(gè)結(jié)點(diǎn)，最少有 4個(gè)結(jié)點(diǎn)。 見(jiàn)題圖。 : 圖如下： 13. 從空樹(shù)開(kāi)始，依次輸入 20 , 30, 50 , 52 ,60 , 68, 70，畫(huà)出建立2-3樹(shù)的過(guò)程。并畫(huà)出刪除 50和68后的B-樹(shù)狀態(tài)。 答：過(guò)程如下： (1) 插入 20, 30： (2) 插入 50： (3) 插入 52： (4) 插入 60： (5) 插入 68： (6) 插入 70： (7) 刪去 5

49、0： (8) 刪去 68 14。畫(huà)出依次插入 z,v,o,p,w,y 到圖9.12(h)所示的5階B-樹(shù)的過(guò)程。 答：如圖：第一步,插入 z: 第二、三步 , 插入 v,o ： 第四五六步,插入 p,w,y: 15. 在含有n個(gè)關(guān)鍵字的m階B-樹(shù)中進(jìn)行查找，至多讀盤(pán)多少次 ？完全平衡的二叉排序樹(shù)的讀盤(pán)次數(shù)大約比它大多少倍 ？ 答：在含有n個(gè)關(guān)鍵字的 m階B-樹(shù)中進(jìn)行查找至多讀盤(pán)次數(shù)不超過(guò) B-樹(shù)高h(yuǎn),即logt((n+1)/2)+1 ,(注，此處t為底，值是除根外的每個(gè)內(nèi)部結(jié)點(diǎn)的最小度數(shù)廠m/2n ). 完全平衡的二叉樹(shù)高為 lgn,所以它的讀盤(pán)次數(shù)至多也是 lgn，它與上述B

50、-樹(shù)的讀盤(pán)次數(shù)的比值約為 lgt倍(此處底是2). 16. 為什么在內(nèi)存中使用的 B-樹(shù)通常是3階的，而不使用更高階的 B-樹(shù)？ 答：因?yàn)椴檎业炔僮鞯?cpu時(shí)間在B-樹(shù)上是O(lgn ? (m/lgt)), 而m/lgt>1,所以m較大時(shí)它所費(fèi)時(shí)間比平衡的二叉排序樹(shù)上相應(yīng)操作時(shí)間大得多， 因此，僅在內(nèi)存中使用的 B-樹(shù)通常取最小值 3. 17. 為什么二叉排序樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是一個(gè)葉子，而 B-樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是根 ？哪一種長(zhǎng)高能保證樹(shù)平衡 ？ 答：因?yàn)樵诙媾判驑?shù)中，關(guān)鍵字總是作為一個(gè)葉子結(jié)點(diǎn)插入以原來(lái)的樹(shù)中，所以當(dāng)樹(shù)增高時(shí)，新結(jié)點(diǎn)總是一個(gè)葉子；而 B-樹(shù)中關(guān)鍵字插入總是插

51、 入到葉子結(jié)點(diǎn)內(nèi)部，在葉結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目尚未超過(guò)它能夠容納的數(shù)目之前是不會(huì)增加結(jié)點(diǎn)的，當(dāng)關(guān)鍵字?jǐn)?shù)超過(guò)結(jié)點(diǎn)可容納的數(shù)目時(shí)，葉結(jié)點(diǎn)就 時(shí)，才能引起樹(shù)高增加，此時(shí)產(chǎn)生一個(gè)新的根結(jié)點(diǎn)。所以說(shuō) B 樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)總是根。 顯然，后一種長(zhǎng)高總能保證樹(shù)的平衡。 18. 已知關(guān)鍵字序列為 (PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT) 試為它們?cè)O(shè)計(jì)一個(gè)散列函數(shù)，將其映射到區(qū)間 [0..n-1] 上，要求碰撞盡可能的 少。這里 n=11,13,17,19. 解：我的設(shè)計(jì)的散列函數(shù)是這樣的，把關(guān)鍵字串中的每一個(gè)字符按其所在位置分別將其 ASCII 值乘以一個(gè)不同的

52、數(shù)，然后把這些值相加的和去對(duì) n 求余，余數(shù)即為散列表中的位置。函數(shù)如下： int Hash (char key[]) { return (int)(key[0]+key[1]*0.618+key[2]*10)%n; } 我們可以設(shè)計(jì)一個(gè)程序來(lái)看看用這個(gè)散列函數(shù)得到的所有關(guān)鍵字映射到區(qū)間的位置： #include #define n 11 file:// 先用 11 來(lái)代入，我們可以用 13， 17，19 依次代入驗(yàn)證 int Hash (char key[]) { return (int)(key[0]+key[1]*0.618+key[2]*1

53、0)%n; file:// 此處我用了系數(shù) 1， 0.618 和 10，你也可以用其他的數(shù)代入看有沒(méi)有更好的系數(shù) } void main() { char s[10][4]={"PAL","LAP","PAM","MAP","PAT","PET","SET","SAT","TAT","BAT"}; // 以上用一個(gè)二維數(shù)組來(lái)存放關(guān)鍵字序列 int i; for(i=0; i<10;i++) { printf("%d ",Hash(s )); } } 19. 對(duì)于一組給定的、固定不變的關(guān)鍵字序列，有可能設(shè)計(jì)出無(wú)沖突的散列函數(shù) H,此時(shí)稱H為完備的散列函數(shù)(per

54、fect hashing function)，若H能無(wú)沖突地將關(guān)鍵字完全填滿散列表，則稱H是最小完備(minimal perfect) 的散列函數(shù)。通常找完備的散列函數(shù)非常困難，找最小完備的散列函數(shù)就更困難。請(qǐng)問(wèn)： (1)若h是已知關(guān)鍵字集合K的完備的散列函數(shù)，若要增加一個(gè)新的關(guān)鍵字到集合 K 一般情況下H還是完備的嗎？ ⑵已知關(guān)鍵字集合為(81 ,129, 301，38, 434, 216, 412, 487, 234)，散列函數(shù)為H(x)=(x+18)/63,請(qǐng)問(wèn)H是完備的嗎？它是最小完備的嗎？ (3) 考慮由字符串構(gòu)成的關(guān)鍵字集合 (Bret,Jane,Shirley,Bryc

55、e,Michelle,Heather) ，試為散列表 [0..6] 設(shè)計(jì)一個(gè)完備的散列函數(shù)。 (提示：考慮每 個(gè)字符串的第 3 個(gè)字符，即 s[2]) 答：(1) 一般情況下H不是完備的，如果說(shuō)插入一個(gè)新的關(guān)鍵字它還是完備的，那么再插入一個(gè)呢 ？它豈不是永遠(yuǎn)是完備的散列函數(shù)了 ？ 所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。 ⑵這個(gè)H是完備的，其函數(shù)值依次為：1, 2，5，0, 7，3，6, 8, 4。如果散列表長(zhǎng)m=90寸，它就是最小完備的。 (3) 這個(gè)函數(shù)如下： int Hash (char key[]) { return key[2]%7;}

56、 20. 設(shè)散列函數(shù)為h(key)=key%101,解決沖突的方法為線性探查，表中用"-1"表示空單元。若刪去散列表HT中的304(即令HT[1]=-1)之后，在表HT 中查找 70 7將會(huì)發(fā)生什么 ？若將刪去的表項(xiàng)標(biāo)記為 "-2", 查找時(shí)探查到 -2 繼續(xù)向前搜索，探查到 -1 時(shí)終止搜索。請(qǐng)問(wèn)用這種方法刪 304后能否正確 地查找到 707？ 0 1 2 3 100 HT | 202 | 304 | 507 | 707 | 答：查找 707時(shí)，首先根據(jù)散列函數(shù)計(jì)算得出該元素應(yīng)在散列表中的 0單元，但是在 0單元沒(méi)有找到，因此將向下一單元探查，結(jié)果發(fā)現(xiàn)該單元是 -1( 為空單元

57、)，所以結(jié)束查找，這將導(dǎo)致 707無(wú)法找到。 如果改用"-2" 作為刪除標(biāo)記，則可以正確找到 707所在的結(jié)點(diǎn)。 21. 設(shè)散列表長(zhǎng)度為11,散列函數(shù)h(x)=x%11,給定的關(guān)鍵字序列為：1，13，13, 34, 38, 33, 27，22.試畫(huà)出分別用拉鏈法和線性探查法解決沖突 時(shí)所構(gòu)造的散列表，并求出在等概率情況下，這兩咱方法查找成功和失敗時(shí)的平均查找長(zhǎng)度。請(qǐng)問(wèn)裝填因子的值是什么 ？ 答：拉鏈法如下圖： (后面的框框就不畫(huà)了 ) T[0..10] 1 | | f 1 f 12 f 34 人 2 | | f 13 人 下標(biāo) 6 I 卜' I 7 I 卜' I 8 I 卜'

58、 I 9 I 卜' I 10 I 卜' I 線性探查法如下圖： 0 1 2 3 4 5 6 7 8 9 10 T[0..10] I 33I 1 I 13I 12I 34I 38I 27I 22I 探查次數(shù) 1 1 1 3 4 1 7 8 用拉鏈法的查找成功平均查找長(zhǎng)度為： ASLscuu=(1*4+2*3+3*1)/8=1.625 查找失敗時(shí)平均查找長(zhǎng)度為： ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73 用線性探查法查找成功時(shí)平均查找長(zhǎng)度為： 查找失敗時(shí)平均查找長(zhǎng)度為： ASLunsucc=(9+8+7+6+5+4+3+2+1

59、+1+1)/11=4.3 裝填因子a拉鏈=4/1仁0.36 a線性探查=8/11=0.73 22. 假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進(jìn)行多少次探查 ? 答：至少要進(jìn)行 1+2+3...+k-1+k 次探查。 也就是說(shuō)，在散列表的一連串連續(xù)空間內(nèi)，第一個(gè)關(guān)鍵字只需探查一次，第二個(gè)就要探查 2次，如此這般，第k個(gè)關(guān)鍵字就要探查k次才能找到位 置存放。所以至少要把它們?nèi)悠饋?lái)才夠。 23. 為什么說(shuō)當(dāng)裝填因子非常接近 1 時(shí)，線性探查類似于順序查找 ?為什么說(shuō)當(dāng)裝填因子比較小 (比如 a=0.7 左右)時(shí)，散列查找的平均查找時(shí)間為 O(1)? 答：當(dāng) a 非常接近 1 時(shí)，整個(gè)散列表幾乎被裝滿。由于線性探查法在關(guān)鍵字同義時(shí)解決沖突的辦法是線性地向后查找，當(dāng)整個(gè)表幾乎裝滿時(shí)，它 就很類似于順序查找了。 當(dāng) a 比較小時(shí)，關(guān)鍵字碰撞的幾率比較小，一般情況下只要按照散列函數(shù)計(jì)算出的結(jié)果能夠 1 次性就找到相應(yīng)結(jié)點(diǎn)，因此它的平均查找時(shí)間接近 于1.