中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法第9章查找課后作業(yè)答案..

1、第 9 章查找習(xí)題練習(xí)答案1.對含有 n 個互不相同元素的集合，同時找最大元和最小元至少需進(jìn)行多少次比較?答：2 次開始，每次取一個元素先和 max 比較，如果大于 max 若小于 max 則再與 min 相比較，在最好的情況下，一 所以這種情況下， 至少要進(jìn)行 n-1 次比較就能找到最大元設(shè)變量 max 和 min 用于存放最大元和最小元 (的位置 )，第一次取兩個元素進(jìn)行比較， 大 的放入max，小的放入min。從第 則以它替換max，并結(jié)束本次比較； 路比較下去都不用和 min 相比較， 和最小元。2. 若對具有 n 個元素的有序的順序表和無序的順序表分別進(jìn)行順序查找，試在下述兩種情況下

2、分別討論兩 者在等概率時的平均查找長度：(1) 查找不成功，即表中無關(guān)鍵字等于給定值K 的記錄；(2) 查找成功，即表中有關(guān)鍵字等于給定值K 的記錄。答：查找不成功時，需進(jìn)行 n+1 次比較才能確定查找失敗。因此平均查找長度為n+1 ，這時有序表和無序 表是一樣的。查找成功時，平均查找長度為 (n+1)/2, 有序表和無序表也是一樣的。因為順序查找與表的初始序列狀態(tài) 無關(guān)。3. 畫出對長度為 18 的有序的順序表進(jìn)行二分查找的判定樹，并指出在等概率時查找成功的平均查找長度， 以及查找失敗時所需的最多的關(guān)鍵字比較次數(shù)。答：4662區(qū)禹丙117引I 5-6l6-7137-85第一次比較:a b c

3、 d(g)q第二次比較:a b (c) df第三次比較:a (b)c d經(jīng)過三次比較,查找成功。等概率情況下，查找成功的平均查找長度為:ASL=(1+2*2+3*4+4*8+5*3)/18=3.5565.查找失敗時，最多的關(guān)鍵字比較次樹不超過判定樹的深度，此處為4. 為什么有序的單鏈表不能進(jìn)行折半查找答:因為鏈表無法進(jìn)行隨機訪問，如果要訪問鏈表的中間結(jié)點，就必須先從頭結(jié)點開始進(jìn)行依次訪問，這 就要浪費很多時間，還不如進(jìn)行順序查找，而且，用鏈存儲結(jié)構(gòu)將無法判定二分的過程是否結(jié)束，因此無 法用鏈表實現(xiàn)二分查找。5.設(shè)有序表為(a,b,c,e,f,g,i,j,k,p,q),請分別畫出對給定值b,g和

4、n進(jìn)行折半查找的過程。解:(1)查找b的過程如下(其中方括號表示當(dāng)前查找區(qū)間，圓括號表示當(dāng)前比較的關(guān)鍵字下標(biāo):8 9 10 11 12 13(2)g的查找過程如下:a b c d e f (g) h i j k p q一次比較成功。(3) n的查找過程如下:下標(biāo)：12 3 4 5 6 7 8 9 10 1112 13第一次比較:a b c d e f (g) h i jk P q第二次比較:hi (j) kp q第三次比較:i j k (P) q第四次比較:i j k P q經(jīng)過四次比較,查找失敗。6.將(for, case, while, class, p rotected, virtual

5、, p ublic, p rivate, do, temp late, const ,if, int)中的關(guān)鍵字依次插入初態(tài)為空的二叉排序樹中，請畫出所得到的樹T。然后畫出刪去for之后的二叉排序樹T',若再將for插入T'中得到的二叉排序樹 T”是否與T相同？最后給出T"的先序、中序和后序序列。答:二叉排序樹刪去for后的二叉排序樹如下圖:二叉排序樹T"與 T不同T"的先序序列是:do case class const while p rotected p rivate if for int virtual p ublic tempi ateT&

6、quot;的中序序列是:case class const do for if int p rivate p rotected p ublic tempi ate virtual whileT"的后序序列是:const class case for int if p rivate tempi ate p ublic virtual p rotected while do7.對給定的關(guān)鍵字集合,以不同的次序插入初始為空的樹中，是否有可能得到同一棵二叉排序樹答:有可能。如有兩個序列：3，1, 2，4和3，4，1，2,它們插入空樹所得的二叉排序樹是相同的。8.將二叉排序樹 T 的先序序列中的

7、關(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；(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)是不可能查找到的序列。

8、把這四個序列各插入到一個初始為空的二叉排序樹中，結(jié)果可以發(fā)現(xiàn),(c)序列所形成的不是一條路徑，而是有分支的，可見它是不可能在查找過程中訪問到的序列。10.設(shè)二叉排序樹中關(guān)鍵字互不相同，則其中最小元必?zé)o左孩子，最大元必?zé)o右孩子。此命題是否正確?最小元和最大元一定是葉子嗎 ?一個新結(jié)點總是插在二叉排序樹的某葉子上嗎答：此命題正確。假設(shè)最小元有左孩子，則根據(jù)二叉排序樹性質(zhì)，此左孩子應(yīng)比最小元更小，如此一來就產(chǎn)生矛盾了，因此最小元不可能有左孩子，對于最大元也是這個道理。但最大元和最小元不一定是葉子，它也可以是根、內(nèi)部結(jié)點(分支結(jié)點 )等，這得根據(jù)插入結(jié)點時的次序而定。新結(jié)點總是作為葉子插入在二叉排序樹

9、中的。11.在一棵m階的B-樹中，當(dāng)將一關(guān)鍵字插入某結(jié)點而引起該結(jié)點的分裂時，此結(jié)點原有多少個關(guān)鍵字若刪去某結(jié)點中的一個關(guān)鍵字，而導(dǎo)致結(jié)點合并時，該結(jié)點中原有幾個關(guān)鍵字答：在一棵m階的B-樹中，若由于一關(guān)鍵字的插入某結(jié)點而引起該結(jié)點的分裂時，則該結(jié)點原有m-1 個關(guān)鍵字。若刪去某結(jié)點中一個關(guān)鍵字而導(dǎo)致結(jié)點合并時，該結(jié)點中原有廠m/2n-1個關(guān)鍵字。12.在一棵B-樹中，空指針數(shù)總是比關(guān)鍵字?jǐn)?shù)多一個，此說法是否正確？請問包含8個關(guān)鍵字的3階B-樹(即2-3樹)最多有幾個結(jié)點?最少有幾個結(jié)點？畫出這兩種情況的 B-樹。答:這個說法是正確的。8個關(guān)鍵字的3階B-樹最多有7個結(jié)點，最少有4個結(jié)點。包含

10、13.從空樹開始，依次輸入20，30，50，52，60，68，70，畫出建立2-3樹的過程。并畫出刪除50和68后的B-樹狀態(tài)。答：過程如下:(1)插入 20，30：20 30插入50：50插入52：插入60：插入68：插入70:527C(7)刪去50 :52 63£0 30 I I 60 詞(8)刪去68I S2 III 3030 I I 旳加 I14.畫出依次插入 z,v,o,P,w,y到圖9.12(h)所示的5階B-樹的過程。解:(1)插入z后:b b |d e| |g h “FTI|s t|p插入V,0后vxzb b I d e|g h(3)插入p,w,y后16.為什么在內(nèi)存

11、中使用的B-樹通常是3階的，而不使用更高階的B-樹？答:因為查找等操作的cpu時間在B-樹上是O(lgn (m/Igt),而m/lgt>1,所以m較大時它所費時間比平衡的二叉排序樹上相應(yīng)操作時間大得多，因此，僅在內(nèi)存中使用的B-樹通常取最小17.為什么二叉排序樹長高時，新結(jié)點總是一個葉子，而B-樹長高時，新結(jié)點總是根 ？哪一種長高能保證樹平衡？答:因為在二叉排序樹中，關(guān)鍵字總是作為一個葉子結(jié)點插入以原來的樹中，所以當(dāng)樹增高時，新結(jié)點總是一個葉子；而B-樹中關(guān)鍵字插入總是插入到葉子結(jié)點內(nèi)部，在葉結(jié)點中的關(guān)鍵字?jǐn)?shù)目尚未超過它能夠容納的數(shù)目之前是不會增加結(jié)點的,當(dāng)關(guān)鍵字?jǐn)?shù)超過結(jié)點可容納的數(shù)目時

12、，葉結(jié)點就會發(fā)生分裂，產(chǎn)生一個新結(jié)點(但不一定引起樹增高)，并且將其中的中間結(jié)點傳至上一層，只有當(dāng)這種分裂操作傳遞至根結(jié)點并引起根結(jié)點的分裂時,才能引起樹高增加，此時產(chǎn)生一個新的根結(jié)點。所以說B樹長高時，新結(jié)點總是根。顯然，后一種長高總能保證樹的平衡。佃.對于一組給定的、固定不變的關(guān)鍵字序列，有可能設(shè)計出無沖突的散列函數(shù)H，此時稱H為完備的散列函數(shù)(Perfect hashing function)，若H能無沖突地將關(guān)鍵字完全填滿散列表,則稱H是最小完備(minimal perfect)的散列函數(shù)。通常找完備的散列函數(shù)非常困難，找最小完備的散列函數(shù)就更困難。請問:(1)若h是已知關(guān)鍵字集合K的

13、完備的散列函數(shù)，若要增加一個新的關(guān)鍵字到集合K，般情況下 H 還是完備的嗎 ?(2)已知關(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)鍵字它還是完備的，那么再插入一個呢 ?它豈不是永遠(yuǎn)是完備的散列函數(shù)了

14、? 所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。(2)這個 H 是完備的，其函數(shù)值依次為：1， 2， 5， 0， 7， 3， 6， 8， 4。如果散列表長 m=9時，它就是最小完備的。(3) 這個函數(shù)如下：int Hash (char key) return key2%7;20.設(shè)散列函數(shù)為 h(key)=key%101, 解決沖突的方法為線性探查，表中用 "-1" 表示空單元。若刪去散列表 HT 中的 304(即令 HT1=-1) 之后，在表 HT 中查找 707 將會發(fā)生什么 ?若將刪去的表項標(biāo)記為 "-2", 查找時探查到

15、 -2繼續(xù)向前搜索，探查到 -1時終止搜索。請問用這種方法刪 304 后能否正確地查找到 707?100HT| 202 I 304 | 507 | 707 |答：查找 707 時，首先根據(jù)散列函數(shù)計算得出該元素應(yīng)在散列表中的0 單元，但是在 0 單元沒有找到，因此將向下一單元探查，結(jié)果發(fā)現(xiàn)該單元是-1 (為空單元 )，所以結(jié)束查找，這將導(dǎo)致 707 無法找到。如果改用 "-2"作為刪除標(biāo)記，則可以正確找到 707 所在的結(jié)點。21.設(shè)散列表長度為 11，散列函數(shù) h(x)=x%11, 給定的關(guān)鍵字序列為： 1，13，13，34，38，33，27，22.試畫出分別用拉鏈法和線

16、性探查法解決沖突時所構(gòu)造的散列表，并求出在等概率情況下，這兩種方法查找成 功和失敗時的平均查找長度。請問裝填因子的值是什么 答：(1)拉鏈法如下圖：T0.1033 T 22 AT1I1 T 12 T 347VI12I13 T4| A II15I38 T 27 AT6I AI7I AI8I AII19I AI10 I A I(2)線性探查法如下圖：下標(biāo) 0 1 2 3 4 5 6 7 8 9 10T0.10I33I1 I13I12I34I38I27III22 I探查次數(shù) 1113417 8用拉鏈法的查找成功平均查找長度為：ASLsucc=(1*4+2*3+3*1)/8=1.625查找失敗時平均查

17、找長度為：ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73用線性探查法查找成功時平均查找長度為：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 線性探查=8/11=0.7322.假定有 k 個關(guān)鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進(jìn)行多少次探查 答：至少要進(jìn)行 1+2+3.+k-1+k 次探查。般，第 k 個關(guān)鍵字就要探查 k 次才能找到位置存放。所以至少要把它們?nèi)悠饋聿艍颉?/p>

18、23.為什么說當(dāng)裝填因子非常接近1時，線性探查類似于順序查找 ?為什么說當(dāng)裝填因子比較小(比如 a =0.7左右 )時，散列查找的平均查找時間為 O(1)?答：當(dāng)a非常接近1時，整個散列表幾乎被裝滿。由于線性探查法在關(guān)鍵字同義時解決沖突的辦法是線性地 向后查找，當(dāng)整個表幾乎裝滿時，它就很類似于順序查找了。1 次性就找當(dāng)a比較小時，關(guān)鍵字碰撞的幾率比較小，一般情況下只要按照散列函數(shù)計算出的結(jié)果能夠 到相應(yīng)結(jié)點，因此它的平均查找時間接近于 1.24.設(shè)順序表中關(guān)鍵字是遞增有序的，試寫一順序查找算法，將哨兵設(shè)在表的高下標(biāo)端。然后求出等概率情況下查找成功與失敗時的 ASL.答:typedef stru

19、ctKeyType key ；InfoType otherinfo ； /此類型依賴于應(yīng)用NodeType ；typedef NodeType SeqListn+1 ； /n 號單元用作哨兵int SeqSearch(Seqlist R， KeyType K) /在關(guān)鍵字遞增有序的順序表R0.n-1中順序查找關(guān)鍵字為K的結(jié)點,/成功時返回找到的結(jié)點位置，失敗時返回-1 int i ；Rn.key=K ； /設(shè)置哨兵 for(i=0 ；Ri.key<=K;i-) ； /從表前往后找 if (i<n&&Ri.key=K) return i; /Ri 是要找的結(jié)點else

20、 return -1 /SeqSearch等概率情況下查找成功 ASL=(1+2+3+ +n)/n等概率情況下查找失敗時的ASL=(1+2+3+-+n+n+1)/(n+1)25試寫出二分查找的遞歸算法。解：int BinSearch(SeqList R ，KeyType K，int low ，int high) / 在有序表 Rlow.high 中進(jìn)行二分查找，成功時返回結(jié)點的位置，失敗時返回零int mid ； /置當(dāng)前查找區(qū)間上、下界的初值if (low<=high) / 當(dāng)前查找區(qū)間 Rlow.high 非空mid=(low+high)/2 ；if(Rmid.key=K) retu

21、rn mid ； /查找成功返回 if(Rmid.kdy>K)return BinSearch( R ，K,low ，mid-1)/ 在 Rlow.mid-1 中查找elsereturn BinSearch( R , K,mid+1 , high) ；/在 Rmid+1.high中查找return 0；/當(dāng) low>high 時表示查找區(qū)間為空，查找失敗 /BinSeareh26試寫一算法判別給定的二叉樹是否為二叉排序樹，設(shè)此二叉樹以二叉鏈表為存儲結(jié)構(gòu)， 且樹中結(jié)點的關(guān)鍵字均不相同。解：由二叉排序樹的定義可得：二叉排序樹中左子樹的所有結(jié)點的值都小于根結(jié)點的值，所有右子樹中結(jié) 點的值

22、都大于根結(jié)點的值。那么只要對待判定的二叉樹中的結(jié)點按層遍歷并判斷即可。在該算法中要用到 隊列保存已遍歷的結(jié)點指針。typedef BinTNode *DataType;/ 循環(huán)隊列中元素為二叉樹結(jié)點指針int BinSortStree(BinTree T)CirQueue Q;BinTNode *p;if (!T) return 1;/ 空樹為二叉排序樹InitQueue(&Q);EnQueue(&Q,T);while(!QueueEmpty(&Q)p=DeQueue(&Q);if (p->lchild)if (p->data<p->lc

23、hild->data) return -1;/ 不是二叉排序樹else EnQueue(&Q,p->lchild);if (p->rchild)if (p->data>p->rchild->data) return -1;/ 不是二叉排序樹else EnQueue(&Q,p->rchild);return 1;/ 是二叉排序樹27.試寫一遞歸算法， 從大到小輸出二叉排序樹中所有其值不小于x 的關(guān)鍵字。要求算法的時間為 O(lgn+m) ，n 為樹中結(jié)點數(shù)， m 為輸出關(guān)鍵字個數(shù) (提示：先遍歷右子樹，后遍歷左子樹)。答：typed

24、ef int KeyType ； /假定關(guān)鍵字類型為整數(shù)typedef struct node / 結(jié)點類型KeyType key ； / 關(guān)鍵字項InfoType otherinfo ； / 其它數(shù)據(jù)域， InfoType 視應(yīng)用情況而定，下面不處理它struct node *lchild ， *rchild ； /左右孩子指針 BSTNode ；typedef BSTNode *BSTree ；void OUTPUTNODE(BSTree T,KeyType x)if (T)OUTPUTNODE( T->rchild,x);if (T->key>=x) printf(&q

25、uot;%d",T->key);OUTPUTNODE( T->Lchild,x);DiskRead 。28.寫一個遍歷B-樹的算法，使輸出的關(guān)鍵字序列遞增有序。算法中的讀盤操作可假定為答：#define Max 1000 /結(jié)點中關(guān)鍵字的最大數(shù)目：Max=m-1，m是B-樹的階#define Min 500 /非根結(jié)點中關(guān)鍵字的最小數(shù)目： Min=m/2(-1typedef int KeyType ； /KeyType 應(yīng)由用戶定義typedef struct node / 結(jié)點定義中省略了指向關(guān)鍵字代表的記錄的指針int keynum ； /結(jié)點中當(dāng)前擁有的關(guān)鍵字的個數(shù)

26、， keynum<=MaxKeyType keyMax+1 ； /關(guān)鍵字向量為 key1.keynum ， key0 不用。struct node *parent ； /指向雙親結(jié)點struct node *sonMax+1 ；/ 孩子指針向量為 son0.keynumBTreeNode ；typedef BTreeNode *BTree ；void travelBtree(BTree T)/按關(guān)鍵字遞增序輸出B-樹序列int i;if (T)for(i=0;i<=T->keynum;i+)/T->keynum 個關(guān)鍵字的結(jié)點有 T->keynum+1 棵子樹if

27、 (T->soni)DiskRead(T->soni);/ 讀入根結(jié)點的第 i 棵子樹travelBtree(T->soni);/ 遍歷第 i 棵子樹if (i<T->keynmu)/ 若剛遍歷的子樹不是最后一棵子樹printf("%d",T->keyi+1;29若采用除余法作為散列函數(shù)，線性探查解決沖突，則9.4.4 節(jié)中通用的散列表查找算法可改寫為對線性探查專用的查找算法：int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/ 記錄探查次數(shù)*pos=K%m; / 散列函數(shù)值作為第

28、一個散列地址while(i+<m) / 最多探查 m 次if(T*pos.key=K) return 1;/ 查找成功返回if(T*pos.key=NIL) return 0;/ 查找失敗返回*pos=(*pos+1)%m;/ 用線性探查法求下一個探查地址return -1;/ 查找失敗，且表滿/HashSearch假設(shè)散列表上的刪除操作已將結(jié)點的關(guān)鍵字標(biāo)記為 DELETED( 例如，不妨設(shè) DELETED 為 -2)。請修改上述散列表上的查找算法及插入算法Hashinsert,使之能正確地查找和插入。解：(1) 查找算法#define DELETED -2#define NIL -1

29、/ 空結(jié)點標(biāo)記依賴于關(guān)鍵字類型，本節(jié)假定關(guān)鍵字均為非負(fù)整數(shù)#define M 997 /表長度依賴于應(yīng)用，但一般應(yīng)根據(jù)。確定 m 為一素數(shù)typedef struct / 散列表結(jié)點類型KeyType key ；InfoType otherinfo ； / 此類依賴于應(yīng)用NodeType ；typedef NodeType HashTablem ； / 散列表類型int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/ 記錄探查次數(shù)*pos=K%m; / 散列函數(shù)值作為第一個散列地址while(i+<m) / 最多探查 m 次if(T

30、*pos.key=K) return 1;/ 查找成功返回if(T*pos.key=NIL) return 0;/ 查找失敗返回*pos=(*pos+1)%m;/ 用線性探查法求下一個探查地址return -1;/ 查找失敗，且表滿/HashSearch(2) 插入算法 HashInsertint HashInsert(HashTable T,KeyType K)返回1表示表中已有k,返回0表示正常插入，返回-1表示插入失敗 int i=0;/ 記錄探查次數(shù)int j=-1;/ 記錄 DELETED 的位置int pos=K%m; / 散列函數(shù)值作為第一個散列地址while(i+<m)

31、/ 最多探查 m 次if(Tpos.key=K) return 1;/ 查找成功返回if(Tpos.key=NIL)if (j=-1) Tpos.key=K;/ 查找失敗 ,插入else Tj.key=K;/ 插入到被刪除元素留出的位置return 0;/正常插入if(Tpos.key=DELETED) if (j=-1) j=pos;pos=(pos+1)%m;/ 用線性探查法求下一個探查地址return -1;/ 查找失敗，且表滿30用拉鏈法解決沖突，有關(guān)的類型說明和插入算法如下，請據(jù)此寫出散列表的建表、查找及刪除算法。typedef struct nodeKeyType key;/ 關(guān)鍵

32、字InfoType Otherinfo;/ 以下不處理此域struct node *next;/ 鏈域CNodeType;typedef CNodeType *CHashTablem;/ 散列表類型是一個指針數(shù)組void ChainHashInsert(CHashTable T,KeyType K)/將關(guān)鍵字 K 插入表 T 中，設(shè)散列函數(shù)為 h(K)=K%mCNodeType *p;int addr;p=ChainHashSearch(T,K);/ 在 T 中查找有無關(guān)鍵字為 K 的結(jié)點if (p) printf("duplicate key!");/ 關(guān)鍵字已存在else /申請一個新結(jié)點，將其關(guān)鍵字置為K，并插入相應(yīng)鏈表的頭上addr=K%m;/ 求散列函數(shù)值作為散列地址p=(CNodeType *)malloc(sizeof(CNodeType);p->key=K;p->next=Taddr;Tadd