數(shù)據結構習題-供參考

1、樹和二叉樹習題（39）1請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設二叉樹用 llink-rlink 法存儲。 2 假設 K1，Kn 是 n 個關鍵詞，試解答： (1) 試用二叉查找樹的插入算法建立一棵二叉查找樹，即當關鍵詞的插入次序為 K1，K2，Kn 時，用算法建立一棵以LLINK / RLINK 鏈接表示的二叉查找樹。 (2) 設計一個算法，打印出該二叉查找樹的嵌套括號表示結構。例如，K1=B，K2=A，K3=D，K4=C，K5=E，則用二叉查找樹的插入算法建立的二叉查找樹為：該二叉查找樹的嵌套括號表示結構為：B（A，D（C，E） ） 3 寫出在二叉排序樹中刪除一個結點的算法，使刪

2、除后仍為二叉排序樹。設刪除結點由指針 p 所指，其雙親結點由指針 f 所指，并假設被刪除結點是其雙親結點的右孩子。用類 PASCAL（或 C）語言將上述算法寫為過程形式。 4. 已知二叉樹排序樹中某結點指針 p,其雙親結點指針為 fp,p 為 fp 的左孩子，試編寫算法，刪除 p 所指結點。 5二叉排序樹采用二叉鏈表存儲。寫一個算法，刪除結點值是 X 的結點。要求刪除該結點后,此樹仍然是一棵二叉排序樹，并且高度沒有增長（注：可不考慮被刪除的結點是根的情況） 。 6. 設記錄 R1,R2,Rn 按關鍵字值從小到大順序存儲在數(shù)組 r1.n中,在rn+1處設立一個監(jiān)督哨,其關鍵字值為+; 試寫一查找

3、給定關鍵字 k 的算法;并畫出此查找過程的判定樹,求出在等概率情況下查找成功時的平均查找長度。 7設計算法以求解編號為i和j的兩個結點的最近的公共祖先結點的編號。 8元素集合已存入整型數(shù)組 A1.n中， 試寫出依次取 A 中各值 Ai(1=i=2 的樹，樹中的每個結點中不是包含一個或幾個關鍵字，而是只含有組成關鍵字的符號。編寫一個在鍵（TIRE）樹 T 上查找關鍵字等于給定值 KEY 的記錄的算法。若查找成功，返回指向該記錄的指針；否則返回空指針。 11寫出從哈希表中刪除關鍵字為 K 的一個記錄的算法，設哈希函數(shù)為 H，解決沖突的方法為鏈地址法。12編寫一用鏈接表（LINKED LIST）解決

4、沖突的哈希表插入函數(shù)。 13在用除余法作為散列函數(shù)、線性探測解決沖突的散列表中，寫一刪除關鍵字的算法，要求將所有可以前移的元素前移去填充被刪除的空位，以保證探測序列不致于斷裂。 14設排序二叉樹中結點的結構為下述三個域構成: data: 給出結點數(shù)據的值；left: 給出本結點的左兒子結點的地址；right: 給出本結點的右兒子結點的地址 設 data 域為正整數(shù)，該二叉樹樹根結點地址為 T。 現(xiàn)給出一個正整數(shù) x。請編寫非遞歸程序，實現(xiàn)將 data 域的值小于等于 x 的結點全部刪除掉。 15已知二叉樹 T 的結點形式為(llink, data,count,rlink,),在樹中查找值為 X

5、 的結點，若找到，則記數(shù)（count）加 1；否則，作為一個新結點插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。 16假設一棵平衡二叉樹的每個結點都標明了平衡因子 b,試設計一個算法，求平衡二叉樹的高度。 17設從鍵盤輸入一個整數(shù)的序列：n,a1,a2，an,其中 n 表示連續(xù)輸入整數(shù)的個數(shù)。（1）試編寫一程序按整數(shù)值建立一個二叉排序樹 18.設二叉排序樹的各元素值均不相同，采用二叉鏈表作為存儲結構，試分別設計遞歸和非遞歸算法按遞減序打印所有左子樹為空，右子樹非空的結點的數(shù)據域的值。 19 在單鏈表中， 每個結點含有 5 個正整型的數(shù)據元素若 （最后一個結點的數(shù)據元素不滿 5 個， 以值

6、0 充） ，試編寫一算法查找值為 n（n0）的數(shù)據元素所在的結點指針以及在該結點中的序號，若鏈表中不存在該數(shù)據元素則返回空指針。 20編寫對有序表進行順序查找的算法，并畫出對有序表進行順序查找的判定樹。假設每次查找時的給定值為隨機值，又查找成功和不成功的概率也相等，試求進行每一次查找時和給定值進行比較的關鍵字個數(shù)的期望值。 21. 在二叉排序樹的結構中，有些數(shù)據元素值可能是相同的 ，設計一個算法實現(xiàn)按遞增有序打印結點的數(shù)據域，要求相同的數(shù)據元素僅輸出一個，算法還應能報出最后被濾掉，而未輸出的數(shù)據元素個數(shù)，對如圖所示的二叉排序樹，輸出為：10，12，13，15，18，21，27，35，42濾掉

7、3 個元素。22已知二叉排序樹采用二叉鏈表存儲結構，根結點的指針為 T，鏈結點的結構為（lchild,data,rchild） ，其中l(wèi)child、 rchild 分別指向該結點左、 右孩子的指針 （當孩子結點不存在時， 相應指針域為 null） ,data域存放結點的數(shù)據信息。請寫出遞歸算法，從小到大輸出二叉排序樹中所有數(shù)據值=x 的結點的數(shù)據。要求先找到第一個滿足條件的結點后再依次輸出其他滿足條件的結點。 23. 已知某哈希表 HT 的裝填因子小于 1，哈希函數(shù) H(key)為關鍵字的第一個字母在字母表中的序號。 （1） 處理沖突的方法為線性探測開放地址法。編寫一個按第一個字母的順序輸出哈

8、希表中所有關鍵字的程序。 （2）處理沖突的方法為鏈地址法。編寫一個計算在等概率情況下查找不成功的平均查找長度的算法。注意，此算法中規(guī)定不能用公式直接求解計算。 24有一個 100*100 的稀疏矩陣，其中 1%的元素為非零元素，現(xiàn)要求用哈希表作存儲結構。 （1）請你設計一個哈希表 （2）請寫一個對你所設計的哈希表中給定行值和列值存取矩陣元素的算法；并對你的算法所需時間和用一維數(shù)組（每個分量存放一個非零元素的行值，列值，和元素值）作存儲結構時存取元素的算法（注：此算法不需要寫出，僅需說明存取的方法和所用時間）進行比較。 25將一組數(shù)據元素按哈希函數(shù) H（key）散列到哈希表 HT（0:m）中，用

9、線性探測法處理沖突（H（key）+1、H（key）+2、H（key）-1） ，假設空單元用 EMPTY 表示，刪除操作是將哈希表中結點標志位從 INUSE標記為 DELETED，試寫出該散列表的查找、插入和刪除三個基本操作算法。 26. 設給定關鍵字輸入序列為（100，90，120，60，78，35，42，31，15）用散列法散列 0-10 的地址區(qū)間。要求設計一合理的散列函數(shù)；沖突時用鏈表法解決，寫出散列算法，并構造出散列表，在等概率查找情況下查找成功的平均查找長度是多少？ 類似本題的另外敘述有： (1) 已知輸入關鍵字序列為（100,90,120,60,78,35,42,31,15）地址區(qū)

10、間為。設計一個哈希表函數(shù)把上述關鍵字散到中，畫出散列表（沖突用線性探測法） ；寫出查找算法，計算在等概率情況下查找成功的平均查找長度。 27. 已知順序表中有 m個記錄，表中記錄不依關鍵字有序排列，編寫算法為該順序表建立一個有序的索引表，索引表中的每一項含記錄的關鍵字和該記錄在順序表中的序號，要求算法的時間復雜度在最好的情況下能達到O(m).28設計算法以輸出二叉樹中先序序列的前k（k0）個結點的值。29設計算法按中序次序依次輸出各結點的值及其對應的序號。例如，下圖中的二叉樹的輸出結果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9)

11、(G,10)。 eq oac(,A) eq oac(,B) eq oac(,G) eq oac(,C) eq oac(,D) eq oac(,H) eq oac(,E) eq oac(,F) eq oac(,I) eq oac(,J)30設計算法以輸出每個結點到根結點之間的路徑上的所有結點的值。31設計算法將一棵以二叉鏈表形式存儲的二叉樹轉換為順序存儲形式存儲到數(shù)組An中，并將其中沒有存放結點值的數(shù)組元素設置為NULL。32設計算法將一棵以順序存儲方式存儲在數(shù)組A中的二叉樹轉換為二叉鏈表形式。33分別設計出先序、中序和后序遍歷二叉樹的非遞歸算法。34分別討論先序、中序和后序線索化二叉樹中前驅和

12、后繼的求解。35設計一個遍歷先序線索二叉樹的非遞歸算法，要求不許用棧。36設計算法將值為x的結點作為右子樹的（后序序列的）第一個結點的左孩子插入到后序線索二叉樹中。37分別設計出先序、中序和后序線索化算法。27設計算法以實現(xiàn)將以二叉鏈表形式存儲的樹（森林）轉換為對應的雙親表示形式。28已知樹（森林）的高度為4，所對應的二叉樹的先序序列為ABCDE，請構造出所有滿足這一條件的樹或森林。 29設計算法將一個以孩子鏈表形式表示的森林轉換為二叉鏈表形式。30設計算法按先序次序輸出森林中每個結點的值及其對應的層次數(shù)。31設計算法以求解森林的高度。32設計算法以輸出森林中的所有葉子結點的值。33設計算法逐層輸出森林中的所有結點的值。 34設計算法將森林中的結點以廣義表的形式輸出。例如，下圖中的森林的輸出結果為： (A,(B,(E,(K),F,G),(C,(H,I),(D,(J) , (L,(M,N), (O,(P) eq oac(,A) eq oac(,L) eq oac(,O) eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,M) eq oac(,N) eq oac(,P) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) eq oac(,I) eq oac(,J) eq oac(,K) 35設計