《《數據結構題集》答案 第9章 查找》由會員分享，可在線閱讀，更多相關《《數據結構題集》答案 第9章 查找（21頁珍藏版）》請在裝配圖網上搜索。

1、第九章查找9.25int Search_Sq(SSTable ST,int key)/在有序表上順序查找的算法，監(jiān)視哨設在高下標端ST.elemST.length+1.key=key;for(i=1;ST.elemi.keykey;i+);if(iST.lengthllST.elemi.keyhigh) return 0; 查找不到時返回 0mid=(low+high)/2;if(ST.elemmid.key=key) return mid;else if(ST.elemmid.keykey)return Search_Bin_Recursive(ST,key,low,mid-1);else

2、return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive9.27 int Locate_Bin(SSTable ST,int key)/折半查找，返回小于或等于待查元素的最后一個結點號int *r;r=ST.elem;if(keyvrA.key) return 0;else if(key=rST.length.key) return ST.length;low=1;high=ST.length;while(lowv=high) mid=(low+high)/2;if(key=rmid.key&keyvrmid+1.

3、key) 查找結束的條件 return mid;else if(keyL.idxL.blknum.maxkey) return ERROR; /超 過最大元素low=1;high=L.blknum;found=0;while(low=high&!found) /折半查找記錄所在塊號midmid=(low+high)/2;if(keyL.idxmid-1.maxkey)found=1;else if(keyL.idxmid.maxkey)low=mid+1;else high=mid-1;i=L.idxmid.firstloc; /塊的下界j=i+blksize-1; /塊的上界temp=L.e

4、lemi-1; /保存相鄰元素L.elemi-1=key; /設置監(jiān)視哨for(k=j;L.elemk!=key;k-); /順序查找L.elemi-1=temp; /恢復元素if(kdata=key) return L.t;else if(L.t-datakey)for(p=L.h,i=1;p-data!=key;p=p-next,i+);elsefor(p=L.t,i=L.tpos;p-data!=key;p=p-next,i+);L.t=p;/更新t指針return p;/Search_CSList分析:由于題目中假定每次查找都是成功的，所以本算法中沒有關于查找失敗的處 理.由微積分可得

5、，在等概率情況下，平均查找長度約為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)鏈表存儲結構上的查找算法,假定每次查找都成功p=L.sp;if(p-datakey)while(p-datakey) p=p-pre;L.sp=p;else if(p-datadatanext;L.sp=p;return

6、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-datadata;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

7、(T-lchild) MaxLT_MinGT(T-lchild,x); 本算法仍是借助中序遍歷來實現if(lastdata=x) /找到了小于x的最大元素printf(a=%dn,last);if(lastdatax) /找到了大于x的最小元素printf(b=%dn”,T-data);last=T-data;if(T-rchild) MaxLT_MinGT(T-rchild,x);/MaxLT_MinGT9.33void Print_NLT(BiTree T,int x)/從大到小輸出二叉排序樹T中所有不小于x的元素if(T-rchild) Print_NLT(T-rchild,x);if(

8、T-datadata);if(T-lchild) Print_NLT(T-lchild,x); /先右后左的中序遍歷/Print_NLT9.34void Delete_NLT(BiTree &T,int x)/刪除二叉排序樹T中所有不小于x元素結點，并釋放空間if(T-rchild) Delete_NLT(T-rchild,x);if(T-datalchild;free(q); /如果樹根不小于x,則刪除樹根，并以左子樹的根作為新的樹根if(T) Delete_NLT(T,x); /繼續(xù)在左子樹中執(zhí)行算法/Delete_NLT9.35void Print_Between(BiThrTree T

9、,int a,int b)/打印輸出后繼線索二叉排序樹 T 中所 有大于a且小于b的元素P=T;while(!p-ltag) p=p-lchild; /找到最小元素while(p&p-datadataa) printf(%dn,p-data); /輸出符合條件的元素if(p-rtag) p=p-rtag;elsep=p-rchild;while(!p-ltag) p=p-lchild; 轉到中序后繼/while/Print_Between9.36void BSTree_Insert_Key(BiThrTree &T,int x)/在后繼線索二叉排序樹 T 中插入元 素xif(T-datarta

10、g) /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-datax) /插入到左子樹中if(!T-lchild) /T沒有左子樹時，作為左孩子插入q=(BiThrNode*)malloc(sizeof(BiThrNode);q-data=x;T-lchild=q;q-rtag=1

11、;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所在結點,pre和suc分別指向ptr的前驅和后繼p=T;last=NULL; /last始終指向當前結點p的前一個(前驅)while(!p-ltag) p=p-lchild; /找到中序起始元素while(p)if(p-

12、data=x) /找到了元素x結點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; 轉到中序后繼last=p;/while /借助中序遍歷找到元素x及其前驅和后繼結點if(!ptr) return ERROR; /未找到待刪結點Delete_BSTree(ptr); /刪除 x 結點if(pre&pre-rtag)pre-rchild=suc; /修改線索return OK;/BSTree_Delete_k

13、eyvoid Delete_BSTree(BiThrTree &T)/課本上給出的刪除二叉排序樹的子樹T的算 法，按照線索二叉樹的結構作了一些改動q=T;if(!T-ltag&T-rtag) /結點無右子樹，此時只需重接其左子樹T=T-lchild;else if(T-ltag&!T-rtag) 結點無左子樹，此時只需重接其右子樹T=T-rchild;else if(!T-ltag&!T-rtag) 結點既有左子樹又有右子樹p=T;r=T-lchild;while(!r-rtag)s=r;r=r-rchild; /找到結點的前驅r和r的雙親sT-data=r-data; /用 r 代替 T 結

14、點if(s!=T)s-rchild=r-lchild;else s-lchild=r-lchild; /重接r的左子樹到其雙親結點上q=r;/elsefree(q); /刪除結點/Delete_BSTree分析:本算法采用了先求出x結點的前驅和后繼,再刪除x結點的辦法，這樣修改線 索時會比較簡單，直接讓前驅的線索指向后繼就行了 .如果試圖在刪除x結點的同 時修改線索，則問題反而復雜化了.9.38void BSTree_Merge(BiTree &T，BiTree &S)/把二叉排序樹 S 合并到 T 中if(S-lchild) BSTree_Merge(T，S-lchild);if(S-rch

15、ild) BSTree_Merge(T，S-rchild); /合并子樹Insert_Key(T，S); /插入元素/BSTree_Mergevoid Insert_Node(Bitree &T,BTNode *S)/把樹結點S插入到T的合適位置上if(S-dataT-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; /插入的新結點必須和原來的左右子樹斷

16、絕關系S-rchild=NULL; /否則會導致樹結構的混亂/Insert_Node分析:這是一個與課本上不同的插入算法.在合并過程中，并不釋放或新建任何結 點，而是采取修改指針的方式來完成合并.這樣，就必須按照后序序列把一棵樹中 的元素逐個連接到另一棵樹上，否則將會導致樹的結構的混亂.9.39void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)/把 二叉排序樹 T 分裂為 兩棵二叉排序樹A和B,其中A的元素全部小于等于x,B的元素全部大于xif(T-lchild) BSTree_Split(T-lchild,A,B,x);if(T-rc

17、hild) BSTree_Split(T-rchild,A,B,x); /分裂左右子樹if(T-datadataT-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;S-rchild=NULL;/Insert_Key 9.40typedef struct int data;int bf;int lsize; /lsize域表示該結點的

18、左子樹的結點總數加1BlcNode *lchild,*rchild; BlcNode,*BlcTree; /含lsize域的平衡二叉排序樹類型BTNode *Locate_BlcTree(BlcTree T,int k)/在含 lsize 域的平衡二叉排序樹 T 中確 定第k小的結點孑指針if(!T) return NULL; /k小于1或大于樹結點總數if(T-lsize=k) return T; /就是這個結點else if(T-lsizek)return Locate_BlcTree(T-lchild,k); /在左子樹中尋找else return Locate_BlcTree(T-rc

19、hild,k-T-lsize); /在右子樹中尋找，注意要修改 k 的值/Locate_BlcTree9.41typedef struct enum LEAF,BRANCH tag; / 結點類型標識int keynum;BPLink parent; /雙親指針int keyMAXCHILD; /關鍵字union BPLink childMAXCHILD;/非 葉結點的孩子指針 struct rectype *infoMAXCHILD;/葉子結點的信息指針BPNode *next; /指向下一個葉子結點的鏈接 leaf; BPNode,*BPLink,*BPTree;/B+樹及其結點類型Sta

20、tus BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)/B+樹中按關鍵字隨 機查找的算法，返回包含關鍵字的葉子結點的指針ptr以及關鍵字在葉子結點中 的位置posp=T;while(p.tag=BRANCH) /沿分支向下查找for(i=0;ikeynum&keyp-keyi;i+); /確定關鍵字所在子樹if(i=p-keynum) return ERROR; 關鍵字太大 p=p-childi;for(i=0;ikeynum&key!=p-keyi;i+); /在葉子結點中查找if(i=p-keynum) return ERROR; /

21、找 不到關鍵字ptr=p;pos=i;return OK;/BPTree_Search9.42void TrieTree_Insert_Key(TrieTree &T,StringType key)/在 Trie 樹 T 中插入字符串 key,StringType的結構見第四章q=(TrieNode*)malloc(sizeof(TrieNode);q-kind=LEAF;q-lf.k=key; /建葉子結點klen=key0;p=T;i=1;while(p&ibh.ptrord(keyi)last=p;p=p-bh.ptrord(keyi);i+;/自上而下查找if(p-kind=BRANC

22、H) /如果最后落到分支結點(無同義詞):p-bh.ptrord(keyi)=q; /直接連上葉子 p-bh.num+;else /如果最后落到葉子結點(有同義詞):r=(TrieNode*)malloc(sizeof(TrieNode); /建立新的分支結點last-bh.ptrord(keyi-1)=r; /用新分支結點取代老葉子結點和上一層的聯系r-kind=BRANCH;r-bh.num=2;r-bh.ptrord(keyi)=q;r-bh.ptrord(p-lf.ki)=p; /新分支結點與新老兩個葉子結點相連/TrieTree_Insert_Key分析:當自上而下的查找結束時,存在

23、兩種情況.一種情況，樹中沒有待插入關鍵字的同義詞，此時只要新建一個葉子結點并連到分支結點上即可.另一種情況，有同 義詞，此時要把同義詞的葉子結點與樹斷開，在斷開的部位新建一個下一層的分支 結點，再把同義詞和新關鍵字的葉子結點連到新分支結點的下一層.9.43Status TrieTree_Delete_Key(TrieTree &T,StringType key)/在 Trie 樹 T 中刪除字符 串keyp=T;i=1;while(p&p-kind=BRANCH&iv=key0) 查找待刪除元素last=p;p=p-bh.ptrord(keyi);i+；if(p&p-kind=LEAF&p-l

24、f.k=key) /找到了待刪除元素last-bh.ptrord(keyi-1)=NULL;free(p);return OK;else return ERROR; /沒找到待刪除元素/TrieTree_Delete_Key9.44void Print_Hash(HashTable印/按第一個字母順序輸出Hash表中的所有關鍵字，其中處理沖突采用線性探測開放定址法for(i=1;iv=26;i+)for(j=i;H.elemj.key;j=(j+1)%hashsizesizeindex) 線性探測 if(H(H.elemj.key)=i) printf(%sn,H.elemj);/Print_

25、Hashint H(char *s)/求 Hash 函數if(s) return s0-96; /求關鍵字第一個字母的字母序號(小寫)else return 0;/H9.45typedef *LNodeMAXSIZE CHashTable; 鏈地址 Hash 表類型Status Build_Hash(CHashTable &T,int m/輸入一組關鍵字，建立 Hash 表,表長為 m用鏈地址法處理沖突.if(m1) return ERROR;T=malloc(m*sizeof(WORD); / 建立表頭指針向量for(i=0;idata=key;q-next=NULL;n=H(key);if

26、(!Tn) Tn=q; /作為鏈表的第一個結點elsefor(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)/根 據行列值在Hash表表示的稀疏矩陣中確定元素key的位置kh=2*(100*(row/10)+col/10); /作者設計的 Hash 函數while(H.elemh.key&!EQ(H.elemh.key,key)h=(h+1)%20

27、000;if(EQ(H.elemh.key,key) k=h;else k=NULL;/Locate_Hash分析:本算法所使用的Hash表長20000，裝填因子為50%,Hash函數為行數前兩位 和列數前兩位所組成的四位數再乘以二，用線性探測法處理沖突.當矩陣的元素是 隨機分布時,查找的時間復雜度為0(1).另解：第九章查找習題及答案題號：1 2 3 4 5 6 7 8 9 10 11 12 13 1419 20 21 22 23 一、基礎知識題1. 對含有n個互不相同元素的集合，同時找最大元和最小元至少需進行多少次比較答：我們可以設立兩個變量max和min用于存放最大元和最小元的位置，第一

28、次取兩個元素進行比較，大的放而ax，小的放入min，從第2次 開始，每次取一個元素先和max比較，如果大于max則以它替換max，并結束本次比較；若小于nax則再與min相比較，在最好的情況下，一路比 較下去都不用和min相比較，所以這種情況下，至少要進行V1次比較就能找到最大元和最小元。(順便說一下，最壞情況下，要進行!n-3次比較才能得到結果)2. 若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度)查找不成功，即表中無關鍵字等于給定值:的記錄；(2)查找成功，即表中有關鍵字等于給定值的記錄。答：查找不成功時，需進行n+1次

29、比較才能確定查找失敗。因此平均查找長度為+1，這時有序表和無序表是一樣的。查找成功時，平均查找長度為n+1)/2，有序表和無序表也是一樣的。因為順序查找對表的原始序列的有序性不感興趣。3. 畫出對長度為18的有序的順序表進行二分查找的判定樹，并指出在等概率時查找成功的平均查找長度，以及查找失敗時所需的最多的關鍵字比較次數。答：請看題圖。等概率情況下，查找成功的平均查找長度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556也可以用公式代，大約為：ASL=(18+1)lg(18+1)/18-1=3.346查找失敗時，最多的關鍵字比較次樹不超過判定樹的深度，此處為如圖：4. 為什么

30、有序的單鏈表不能進行折半查找答：因為鏈表無法進行隨機訪問，如果要訪問鏈表的中間結點就必須先從頭結點開始進行依次訪問，這就要浪費很多時間還不如進行順序查找，而且，用鏈存儲結構將無法判定二分的過程是否結束，因此無法用鏈表實現二分查找。5. 設有序表為(a,b,c,e,f,g,i,j,k,p,q),請分別畫出對給定值b,g和n進行折半查找的過程。解：b的查找過程如下 (其中括號表示當前查找區(qū)間，圓括號表示當前比較的關鍵字下標： 1 2 345 678910111213第一次比較：a bcd ef (g)hijkpq第二次比較：a b(c)d efghijkpq第三次比較：a(b)cd efghijk

31、pq經過三次比較，查找成功。g的查找過程如下：a b c d e f (g) h i j k p q一次比較成功。n的查找過程如下：下標：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 bc d e fgh ijk (p) q第四次比較：a bc d e fgh ijk p q經過四次比較，查找失敗。6. 將(for, case, while, class, protected, virtual, public,private, do

32、, template, const ,if,int)中的關鍵字依次插入初態(tài)為空的二叉排序樹中，請畫出所得到的楸然后畫出刪去for之后的二叉排序樹T,若再將for插入T中得到的二叉排序樹T是否與T相同?最后給出T”的先序、中序和后序序列。答：見題圖：T”的先序序列是：do case class const while protected private iffor int virtual public templateT”的中序序列是： case class const do for if int privateprotected public template virtual whileT”的

33、后序序列是：const class case for int if private templatepublic virtual protected while do二叉排序樹T如下圖：刪去for后的二叉排序樹如下圖：圈內的for表示再插入后的結點：7. 對給定的關鍵字集合，以不同的次序插入初始為空的樹中，是否有可能得到同一棵二叉排序樹答：有可能。如有兩個序列：3, 1，2, 4和3, 4, 1，2,它們插入空樹所得的二叉排序樹是相同的。8. 將二叉排序樹T的先序序列中的關鍵字依次插入一空樹中，所得和二叉排序樹與T是否相同?為什么？答：這兩棵二叉樹完全相同。9. 設二叉排序樹中關鍵字由1至10

34、00的整數構成，現要查找關鍵字為63的結點，下述關鍵字序列哪一個不可能是在二叉排序樹上查找到的序列(a) 2，252, 401，398，330, 344, 397，363；(b) 924, 220, 911, 244, 898, 258, 362, 363;(c) 925, 202, 911, 240, 912, 245, 363;(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.答：(c)是不可能查找到的序列。我們可以把這四個序列各插入到一個初始為空的二叉排序樹中，結果可以發(fā)現c)序列所形成的不是一條路徑，而是有分支的，可見它是不可能在查找過程中訪問

35、到的序列。10. 設二叉排序樹中關鍵字互不相同，則其中最小元必無左孩子，最大元必無右孩子。此命題是否正最小元和最大元一定是葉子嗎一個新結點總是插在二叉排序樹的某葉子上嗎答：此命題正確。假設最小元有左孩子，則根據二叉排序樹性質，此左孩子應比最小元更小，如此一來就產生矛盾了此最小元不可能有左孩子， 對于最大元也是這個道理。但最大元和最小元不一定是葉子，它也可以是根、內部結點分支結點)等，這得根據插入結點時的次序而定。如，1，2, 4這個集合，根據不同的插入次序可以得到不同的二叉排序樹：/ O1 040202/ O1 03040403020102/ 01 04/03新結點總是插入在二叉排序樹的某個葉

36、子上的。11. 在一棵m階的B-樹中，當將一關鍵字插入某結點而引起該結點的分裂時此結點原有多少個關鍵字若刪去某結點中的一個關鍵字，而導致結點合并時，該結點中原有幾個關鍵字答：在此樹中，若由于一關鍵字的插入某結點而引起該結點的分裂時，則該結點原有1個關鍵字。若刪去某結點中一個關鍵字而導致結點合并時，該結點中原有rm/2-il個關鍵字。12. 在一棵B-樹中，空指針數總是比關鍵字數多一個，此說法是否正礴問包含8個關鍵字的3階B-樹（即2-3樹）最多有幾個結點?最少有幾個結點？畫出這兩種情況的B-樹。答：這個說法是正確的。包含8個關鍵字的3階B-樹最多有7個結點，最少有4個結點。見題圖。：圖如下：1

37、3. 從空樹開始，依次輸入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個關鍵字的m階B-樹中進行查找，至多讀盤多少次完全平衡的二叉排序樹的讀盤次數大約比它大多少倍答：在含有n個關鍵字的m階B-樹中進行查找至多讀盤

38、次數不超過5-樹高h，即logt(n+1)/2)+1，(注，此處t為底，值是除根外的每個內部結點的最小度數m/2r).完全平衡的二叉樹高為lgn，所以它的讀盤次數至多也是lgn，它與上述B-樹的讀盤次數的比值約為lgt倍(此處底是2).16. 為什么在內存中使用的3-樹通常是3階的，而不使用更高階的3-樹？答：因為查找等操作的cpu時間在B-樹上是O(lgn(m/lgt),而m/lgt1,所以m較大時它所費時間比平衡的二叉排序樹上相應操作時間大得多因此，僅在內存中使用的B-樹通常取最小值3.17. 為什么二叉排序樹長高時，新結點總是一個葉子，而-樹長高時，新結點總是根哪一種長高能保證樹平衡答：

39、因為在二叉排序樹中，關鍵字總是作為一個葉子結點插入以原來的樹中，所以當樹增高時新結點總是一個葉子；而B-樹中關鍵字插入總是插入到葉子結點內部，在葉結點中的關鍵字數目尚未超過它能夠容納的數目之前是不會增加結點的，當關鍵字數超過結點可容納的數目時，葉結點就會發(fā)生分裂，產生一個新結點但不一定引起樹增高，并且將其中的中間結點傳至上一層，只有當這種分裂操作傳遞至根結點并引起根結點的分裂時，才能引起樹高增加，此時產生一個新的根結點。所以說樹長高時，新結點總是根。顯然，后一種長高總能保證樹的平衡。18. 已知關鍵字序列為(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BATM為它們

40、設計一個散列函數，將其映射到區(qū)畫.n-1上，要求碰撞盡可能的少。這里 n=11,13,17,19.解：我的設計的散列函數是這樣的，把關鍵字串中的每一個字符按其所在位置分別將其CII值乘以一個不同的數，然后把這些值相加的和去對求余，余數即為散列表中的位置。函數如下：int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;我們可以設計一個程序來看看用這個散列函數得到的所有關鍵字映射到區(qū)間的位置:#include #define n 11 file:/先用11來代入，我們可以用13, 17, 19依次代入驗證int Hash (ch

41、ar key)return (int)(key0+key1*0.618+key2*10)%n;file:/此處我用了系數1，0.618和10，你也可以用其他的數代入看有沒有更好的系數void main()chars104 = PAL”,LAP”,PAr,MAP”,PAT,PET,SET,SAT,TAT,BAT;/以上用一個二維數組來存放關鍵字序列int i;for(i=0; i10;i+)printf(%d ”,Hash(3);19. 對于一組給定的、固定不變的關鍵字序列，有可能設計出無沖突的散列，函數時稱H為完備的散列函數perfecthashing function,)若H能無沖突地

42、將關鍵字完全填滿散列表，貝H是最小完備minimalperfect)的散列函數。通常找完備的散列函數非常困難，找最小完備的散列函數就更困難。請問：(1)若h是已知關鍵字集合的完備的散列函數，若要增加一個新的關鍵字到集合一般情況下!還是完備的嗎(2) 已知關鍵字集合為81，129, 301，38, 434, 216, 412, 487, 234)，散列函數為i(x) = (x+18)/63請問H是完備的嗎它是最小完備的嗎(3) 考慮由字符串構成的關鍵字集合ret,Jane,Shirley,Bryce,Michelle,Heather試為散列表0.6設計一個完備的散列函數。提示：考慮每個字符串的第

43、3個字符，即s2)答：一般情況下H不是完備的，如果說插入一個新的關鍵字它還是完備的，那么再插入一個不是永遠是完備的散列函數了所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。這個H是完備的，其函數值依次為：2, 5, 0, 7, 3, 6, 8, 4。如果散列表詢=9時，它就是最小完備的。(3)這個函數如下：int Hash (char key) return key2%7;20. 設散列函數為i(key)=key%101解決沖突的方法為線性探查，表中用”表示空單元。若刪去散列度中的304即令HT1=-1)之后，在表1T 中查找707將會發(fā)生什么若將刪去的表項標記為2”，查

44、找時探查到2繼續(xù)向前搜索，探查到時終止搜索。請問用這種方法刪4后能否正確 地查找到707?0123100HT |202 |304 |507 |707 |.|答：查找707時，首先根據散列函數計算得出該元素應在散列表中單元，但是在)單元沒有找到，因此將向下一單元探查，結果發(fā)現該單元是 -1(為空單元，所以結束查找，這將導致07無法找到。如果改用-2作為刪除標記，則可以正確找到7所在的結點。21. 設散列表長度為1，散列函數!(x)=x%11,給定的關鍵字序列為1，13, 13, 34, 38, 33, 27, 22,試畫出分別用拉鏈法和線性探查法解決沖突 時所構造的散列表，并求出在等概率情況下，

45、這兩咱方法查找成功和失敗時的平均查找長度。請問裝填因子的值是什么答：拉鏈法如下圖：(后面的框框就不畫了T0.100| 33 22 A1| 1 12 34 A2| 13 A3| A |4| A |5| 38 27 A6| A |7| A |8| A |10| A I線性探查法如下圖：下標 0123 45678910T0.10|33|1 |13|12|34|38|27|22 |探查次數1113417 8用拉鏈法的查找成功平均查找長度為：ASLscuu=(1*4+2*3+3*1)/8=1.625查找失敗時平均查找長度為：ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.7

46、3用線性探查法查找成功時平均查找長度為：ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25查找失敗時平均查找長度為：ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3裝填因子a拉鏈=4/11=0.36 a線性探查=8/11=0.7322 .假定有k個關鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進行多少次探查答：至少要進行1+2+3.+k-1+次探查。也就是說，在散列表的一連串連續(xù)空間內，第一個關鍵字只需探查一次，第二個就2要探查如此這般，第個關鍵字就要探查次才能找到位置存放。所以至少要把它們全加起來才夠。23.為什么說當裝填因子非常接近時，線性探查類似于順序查?為什么說當裝填因子比較小比如a =0.7左右)時，散列查找的平均查找時間為。？答：當a非常接近1時，整個散列表幾乎被裝滿。由于線性探查法在關鍵字同義時解決沖突的辦法是線性地向后查找，當整個表幾乎裝滿時，它 就很類似于順序查找了。當a比較小時，關鍵字碰撞的幾率比較小，一般情況下只要按照散列函數計算出的結果能性就找到相應結點，因此它的平均查找時間接近 于1.