中南大學數據結構和算法第9章查找課后作業(yè)答案解析

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

2、平均查找長度：(1)查找不成功，即表中無關鍵字等于給定值K的記錄；(2)查找成功，即表中有關鍵字等于給定值K的記錄。答：查找不成功時，需進行n+1次比較才能確定查找失敗。因此平均查找長度為n+1，這時有序表和無序表是一樣的。查找成功時，平均查找長度為(n+1)/2,有序表和無序表也是一樣的。因為順序查找與表的初始序列狀態(tài)無關。3.畫出對長度為18的有序的順序表進行二分查找的判定樹，并指出在等概率時查找成功的平均查找長度，以及查找失敗時所需的最多的關鍵字比較次數。答： 等概率情況下，查找成功的平均查找長度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失敗時，最多的關鍵字

3、比較次樹不超過判定樹的深度，此處為5.4.為什么有序的單鏈表不能進行折半查找?答：因為鏈表無法進行隨機訪問，如果要訪問鏈表的中間結點，就必須先從頭結點開始進行依次訪問，這就要浪費很多時間，還不如進行順序查找，而且，用鏈存儲結構將無法判定二分的過程是否結束，因此無法用鏈表實現(xiàn)二分查找。5.設有序表為(a,b,c,e,f,g,i,j,k,p,q),請分別畫出對給定值b,g和n進行折半查找的過程。解：(1)查找b的過程如下(其中方括號表示當前查找區(qū)間，圓括號表示當前比較的關鍵字)下標： 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比較： a b c d e f (g) h i j

4、 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經過三次比較，查找成功。 (2)g的查找過程如下： a b c d e f (g) h i j k p q 一次比較成功。 (3)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 b c d e f g h i j k (p) q 第四次比較： a b c

5、d e f g h i j k p q 經過四次比較，查找失敗。6.將(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的關鍵字依次插入初態(tài)為空的二叉排序樹中，請畫出所得到的樹T。然后畫出刪去for之后的二叉排序樹T,若再將for 插入T中得到的二叉排序樹T是否與T相同?最后給出T的先序、中序和后序序列。答：二叉排序樹T如下圖：刪去for后的二叉排序樹如下圖：再插入結點for后的二叉排序樹T： 二叉排序樹T與T不同 T的先序序列是：do case class

6、const while protected private if for int virtual public templateT的中序序列是：case class const do for if int private protected public template virtual whileT的后序序列是：const class case for int if private template public virtual protected while do7.對給定的關鍵字集合，以不同的次序插入初始為空的樹中，是否有可能得到同一棵二叉排序樹?答： 有可能。如有兩個序列：3，1，2，

7、4 和 3，4，1，2，它們插入空樹所得的二叉排序樹是相同的。8.將二叉排序樹T的先序序列中的關鍵字依次插入一空樹中，所得和二叉排序樹T與T否相同?為什么?答： 這兩棵二叉樹完全相同。9.設二叉排序樹中關鍵字由1至1000的整數構成，現(xiàn)要查找關鍵字為363的結點，下述關鍵字序列哪一個不可能是在二叉排序樹上查找到的序列?(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, 26

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

9、支結點)等，這得根據插入結點時的次序而定。新結點總是作為葉子插入在二叉排序樹中的。11.在一棵m階的B-樹中，當將一關鍵字插入某結點而引起該結點的分裂時，此結點原有多少個關鍵字?若刪去某結點中的一個關鍵字，而導致結點合并時，該結點中原有幾個關鍵字?答：在一棵m階的B-樹中，若由于一關鍵字的插入某結點而引起該結點的分裂時，則該結點原有m-1個關鍵字。若刪去某結點中一個關鍵字而導致結點合并時，該結點中原有m/2-1個關鍵字。12.在一棵B-樹中，空指針數總是比關鍵字數多一個，此說法是否正確?請問包含8個關鍵字的3階B-樹(即2-3樹)最多有幾個結點?最少有幾個結點?畫出這兩種情況的B-樹。答：這個

10、說法是正確的。包含8個關鍵字的3階B-樹最多有7個結點，最少有4個結點。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-樹的過程。解： (1)插入z后：(2)插入v,o后 (3)插入p,w,y后 16.為什么在內存中使用的B-樹通常是3階的，而不使用更高階的B-樹?答： 因為查找等操作

11、的cpu時間在B-樹上是O(lgn(m/lgt),而m/lgt1,所以m較大時它所費時間比平衡的二叉排序樹上相應操作時間大得多，因此，僅在內存中使用的B-樹通常取最小值317.為什么二叉排序樹長高時，新結點總是一個葉子，而B-樹長高時，新結點總是根?哪一種長高能保證樹平衡?答： 因為在二叉排序樹中，關鍵字總是作為一個葉子結點插入以原來的樹中，所以當樹增高時，新結點總是一個葉子；而B-樹中關鍵字插入總是插入到葉子結點內部，在葉結點中的關鍵字數目尚未超過它能夠容納的數目之前是不會增加結點的，當關鍵字數超過結點可容納的數目時，葉結點就會發(fā)生分裂，產生一個新結點(但不一定引起樹增高)，并且將其中的中間

12、結點傳至上一層，只有當這種分裂操作傳遞至根結點并引起根結點的分裂時，才能引起樹高增加，此時產生一個新的根結點。所以說B樹長高時，新結點總是根。 顯然，后一種長高總能保證樹的平衡。19.對于一組給定的、固定不變的關鍵字序列，有可能設計出無沖突的散列函數H，此時稱H為完備的散列函數(perfect hashing function)，若H能無沖突地將關鍵字完全填滿散列表，則稱H是最小完備(minimal perfect)的散列函數。通常找完備的散列函數非常困難，找最小完備的散列函數就更困難。請問： (1)若h是已知關鍵字集合K的完備的散列函數，若要增加一個新的關鍵字到集合K，一般情況下H還是完備的

13、嗎?(2)已知關鍵字集合為(81，129，301，38，434，216，412，487，234)，散列函數為H(x)=(x+18)/63,請問H是完備的嗎?它是最小完備的嗎?(3)考慮由字符串構成的關鍵字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，試為散列表0.6設計一個完備的散列函數。(提示：考慮每個字符串的第3個字符，即s2)答：(1) 一般情況下H不是完備的，如果說插入一個新的關鍵字它還是完備的，那么再插入一個呢?它豈不是永遠是完備的散列函數了? 所以一般情況下它不能總是完備的，只有一些很少的情況下它還可能是完備的。(2)這個H是完備的，其函

14、數值依次為：1，2，5，0，7，3，6，8，4。如果散列表長m=9時，它就是最小完備的。(3) 這個函數如下：int Hash (char key) return key2%7;20.設散列函數為h(key)=key%101,解決沖突的方法為線性探查，表中用-1表示空單元。若刪去散列表HT中的304(即令HT1=-1)之后，在表HT中查找707將會發(fā)生什么?若將刪去的表項標記為-2,查找時探查到-2繼續(xù)向前搜索，探查到-1時終止搜索。請問用這種方法刪304后能否正確地查找到707?0 1 2 3 100HT202 304 507 707 答： 查找707時，首先根據散列函數計算得出該元素應在散

15、列表中的0單元，但是在0單元沒有找到，因此將向下一單元探查，結果發(fā)現(xiàn)該單元是-1(為空單元)，所以結束查找，這將導致707無法找到。 如果改用-2作為刪除標記，則可以正確找到707所在的結點。21.設散列表長度為11，散列函數h(x)=x%11,給定的關鍵字序列為：1，13，13，34，38，33，27，22.試畫出分別用拉鏈法和線性探查法解決沖突時所構造的散列表，并求出在等概率情況下，這兩種方法查找成功和失敗時的平均查找長度。請問裝填因子的值是什么?答：(1)拉鏈法如下圖： T0.10 0 33 22 1 1 12 34 2 13 3 4 5 38 27 6 7 8 9 10 (2)線性探查

16、法如下圖： 下標 0 1 2 3 4 5 6 7 8 9 10 T0.10331 131234382722 探查次數 1 1 1 3 4 1 7 8 用拉鏈法的查找成功平均查找長度為： ASLsucc=(1*4+2*3+3*1)/8=1.625 查找失敗時平均查找長度為： 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 裝填因子拉鏈=4/11=0

17、.36 線性探查=8/11=0.7322.假定有k個關鍵字互為同義詞，若用線性探查法把這些同義詞存入散列表中，至少要進行多少次探查?答： 至少要進行1+2+3.+k-1+k次探查。 也就是說，在散列表的一連串連續(xù)空間內，第一個關鍵字只需探查一次，第二個就要探查2次，如此這般，第k個關鍵字就要探查k次才能找到位置存放。所以至少要把它們全加起來才夠。23.為什么說當裝填因子非常接近1時，線性探查類似于順序查找?為什么說當裝填因子比較小(比如=0.7左右)時，散列查找的平均查找時間為O(1)?答： 當非常接近1時，整個散列表幾乎被裝滿。由于線性探查法在關鍵字同義時解決沖突的辦法是線性地向后查找，當整

18、個表幾乎裝滿時，它就很類似于順序查找了。 當比較小時，關鍵字碰撞的幾率比較小，一般情況下只要按照散列函數計算出的結果能夠1次性就找到相應結點，因此它的平均查找時間接近于1.24.設順序表中關鍵字是遞增有序的，試寫一順序查找算法，將哨兵設在表的高下標端。然后求出等概率情況下查找成功與失敗時的ASL.答: typedef structKeyType key；InfoType otherinfo； /此類型依賴于應用NodeType；typedef NodeType SeqListn+1； /n號單元用作哨兵int SeqSearch(Seqlist R，KeyType K) /在關鍵字遞增有序的順

19、序表R0.n-1中順序查找關鍵字為K的結點，/成功時返回找到的結點位置，失敗時返回-1int i；Rn.key=K； /設置哨兵for(i=0；Ri.key=K;i-)； /從表前往后找if (in&Ri.key=K) return i; /Ri是要找的結點else 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中進

20、行二分查找，成功時返回結點的位置，失敗時返回零int mid； /置當前查找區(qū)間上、下界的初值if (lowK)return BinSearch( R，K,low，mid-1)/在Rlow.mid-1中查找elsereturn BinSearch( R，K,mid+1，high)； /在Rmid+1.high中查找return 0； /當lowhigh時表示查找區(qū)間為空，查找失敗 /BinSeareh26試寫一算法判別給定的二叉樹是否為二叉排序樹，設此二叉樹以二叉鏈表為存儲結構，且樹中結點的關鍵字均不相同。解：由二叉排序樹的定義可得：二叉排序樹中左子樹的所有結點的值都小于根結點的值，所有右子樹

21、中結點的值都大于根結點的值。那么只要對待判定的二叉樹中的結點按層遍歷并判斷即可。在該算法中要用到隊列保存已遍歷的結點指針。typedef BinTNode *DataType;/循環(huán)隊列中元素為二叉樹結點指針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-datalchild-data) return -1;/不是二叉排序樹els

22、e EnQueue(&Q,p-lchild);if (p-rchild)if (p-datap-rchild-data) return -1;/不是二叉排序樹else EnQueue(&Q,p-rchild);return 1;/是二叉排序樹27.試寫一遞歸算法，從大到小輸出二叉排序樹中所有其值不小于x的關鍵字。要求算法的時間為O(lgn+m)，n為樹中結點數，m為輸出關鍵字個數(提示：先遍歷右子樹，后遍歷左子樹)。答：typedef int KeyType； /假定關鍵字類型為整數typedef struct node /結點類型KeyType key； /關鍵字項InfoType othe

23、rinfo； /其它數據域，InfoType視應用情況而定，下面不處理它struct node *lchild，*rchild； /左右孩子指針 BSTNode；typedef BSTNode *BSTree；void OUTPUTNODE(BSTree T,KeyType x)/從大到小輸出二叉排序樹中所有其值不小于x的關鍵字if (T)OUTPUTNODE( T-rchild,x);if (T-key=x) printf(%d,T-key);OUTPUTNODE( T-Lchild,x);28.寫一個遍歷B-樹的算法，使輸出的關鍵字序列遞增有序。算法中的讀盤操作可假定為DiskRead。答

24、：#define Max l000 /結點中關鍵字的最大數目：Max=m-1，m是B-樹的階#define Min 500 /非根結點中關鍵字的最小數目：Min=m/2(-1typedef int KeyType； /KeyType應由用戶定義typedef struct node /結點定義中省略了指向關鍵字代表的記錄的指針int keynum； /結點中當前擁有的關鍵字的個數，keynum=MaxKeyType keyMax+1； /關鍵字向量為key1.keynum，key0不用。struct node *parent； /指向雙親結點struct node *sonMax+1；/孩子指

25、針向量為son0.keynumBTreeNode；typedef BTreeNode *BTree；void travelBtree(BTree T)/按關鍵字遞增序輸出B-樹序列int i;if (T)for(i=0;ikeynum;i+)/T-keynum個關鍵字的結點有T-keynum+1棵子樹if (T-soni)DiskRead(T-soni);/讀入根結點的第i棵子樹travelBtree(T-soni);/遍歷第i棵子樹if (ikeynmu)/若剛遍歷的子樹不是最后一棵子樹printf(%d,T-keyi+1; 29若采用除余法作為散列函數，線性探查解決沖突，則9.4.4節(jié)中通

26、用的散列表查找算法可改寫為對線性探查專用的查找算法：int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/記錄探查次數*pos=K%m; /散列函數值作為第一個散列地址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假設散列表上的刪除操作已將結點的關鍵字標記為DELETED(例如，不妨設DELETED

27、為-2)。請修改上述散列表上的查找算法及插入算法HashInsert，使之能正確地查找和插入。解：(1)查找算法#define DELETED -2#define NIL -1 /空結點標記依賴于關鍵字類型，本節(jié)假定關鍵字均為非負整數#define M 997 /表長度依賴于應用，但一般應根據。確定m為一素數typedef struct /散列表結點類型KeyType key；InfoType otherinfo； /此類依賴于應用NodeType；typedef NodeType HashTablem； /散列表類型int HashSearch(HashTable T,KeyType K,int *pos)int i=0;/記錄探查次數*pos=K%m; /散列函數值作為第一個散列地址while(i+m) /最多探查m次if(T*pos.key=K) return 1;/查找成功返回if(T*pos.key=NIL) return 0;/查找失敗返回*pos=(*po