數(shù)據(jù)結構(專)階段練習3

1、華東理工大學網絡學院（?？疲?shù)據(jù)結構ch6樹和二叉樹、ch8查找班級 學號 姓名 成績一、名詞解釋（每個2分，共10分）1 .結點的度：結點的子樹的個數(shù)。2 .二叉樹：滿足條件（1）每個結點的度都不大于 2; （2）每個結點的孩子結點次序 不能任意顛倒；這樣的樹形結構稱為二叉樹。3 .線索化：對二叉樹以某種次序進行遍歷并且加以線索的過程。4 .哈夫曼樹：帶權路徑長度 WPL最小的二叉樹稱為哈夫曼樹或者最優(yōu)二叉樹。5 .沖突：不同的關鍵字可能得到同一個哈希地址，這種現(xiàn)象稱為沖突。二、填空題（每空1分，共20分）1 .由樹轉換為二叉樹，其根節(jié)點的右子樹總是為空 。2 .在分塊查找方法中，首先查找索

2、引（表），然后再查找相應的塊。3 .含17個結點的二叉樹的深度是5（設根結點的深度為 1）。4 .一棵高度為h的滿二叉樹共有2h-1個終端結點。5 .已知一棵完全二叉樹的第 5層有3個結點，其葉子結點數(shù)是9。6 .對線性表進行二分查找時，要求線性表必須以.順序方式存儲,且結點按關鍵字有序 排歹” O7 . N個結點的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為n+1。8 .在各種查找方法中，平均查找長度與結點個數(shù)無關的是哈希杳找法。9 .深度為6 （根層次為1）的二叉樹至多有26 -1個結點。10 .由樹轉換成的二叉樹里，一個結點N的左孩子是 N在原樹里對應結點的最左子結點_,而N的右孩子是它在原

3、樹里對應結點的最鄰近的右兄弟。11 .在哈希存儲中，裝填因子”的值越大，則發(fā)牛沖突的可能性就越大；a的值越小，則 發(fā)生沖突的可能性就越小。12 .哈希表的查找效率主要取決于哈希表造表時選取的哈希函數(shù)和 處理沖突的方法 。13 .樹是結點的有限集合，它有 0個或1個 根結點，記為 To其余的結點分成為 m （m >0）個 互不相交 的集合T1, T2,，Tm,每個集合又都是樹，此時結點 T稱為Ti 的 父結點 ，Ti稱為T的子結點（1wiwm）。一個結點的子樹個數(shù)為該 結點的度 。三、判斷正誤（對的用”'表示，錯誤的用“F”表示。每小題1分，共10分）1 .（ T ）具有n個結點的

4、滿二叉樹，其葉結點的個數(shù)為（n+1） /2。2 .（ F ）用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲節(jié)點。3 .( T )判斷線索二叉樹中某結點 p有左孩子的條件是 p->ltag=0。4 .( F )哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的點離根較遠。5 .( F )折半查找適用于有序表，包括有序的順序表和有序的鏈表。6 . ( F )哈夫曼樹中沒有度為 1的結點，所以必為滿二叉樹。7 . ( T )深度為K的完全二叉樹至少有 2K-1個結點。8 . ( T )若查找表的長度為 n,則順序查找法的平均查找長度為(n+1) /2。9 . ( F )二叉排序樹或是一棵空樹，或是具

5、有下列性質的二叉樹：若它的左子樹非空， 則根結點的值大于其左孩子的值；若它的右子樹非空，則根結點的值大于其右孩子的值。10 .( F )分塊查找法中的索引順序表的特點是塊間可無序，但塊內一定要有序。四、單項選擇題(每小題2分，共20分)1 .對包含n個元素的哈希表進行查找，平均查找長度為：DA O(log2n) B O(n) C O(nlog2n) D 不直接依賴于 n2 .將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1,則編號最大的非葉結點的編號為：CA 48 B 49 C 50 D 513 .某二叉樹結點的中序序列為A、B、C、D、E、F、

6、G,后序序列為 B、D、C、A、F、G、巳則其左子樹中結點數(shù)目為：CA 3 B 2 C 4 D54 .設一哈希表表長 M為100 ,用除留余數(shù)法構造哈希函數(shù)，即H (K) =K MOD P ( P<=M ),為使函數(shù)具有較好性能，P應選 CA 100 B 99 C 97D895 .在順序表(3, 6, 8,10,12,15,16,18, 21,25, 30 )中，用折半法查找關鍵碼值11,所需的關鍵碼比較次數(shù)為：CA 2B 3C 4D 56 .將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1,則編號為49的結點的左孩子的編號為：AA 98B

7、 99C 50D 487 .平衡二叉排序樹具有的特點是左子樹與右子樹的高度差的絕對值不超過_D。A 1 B 1C 0 D 18 .由3個結點所構成的樹有B一種形態(tài)。A 1B 2 C 3D 49 .二叉樹是非線性數(shù)據(jù)結構，所以C。A它不能用順序存儲結構存儲B它不能用鏈式存儲結構存儲C順序存儲結構和鏈式存儲結構都能存儲D順序存儲結構和鏈式存儲結構都不能使用10 .設有100個元素，用折半查找法進行查找時，最少比較次數(shù)為C 次。五、簡答題(每小題5分，共10分)1 .試分別找出滿足以下條件的所有二叉樹：(1)二叉樹的前序序列與中序序列相同；(2)二叉樹的中序序列與后序序列相同；(3)二叉樹的前序序列

8、與后序序列相同。答：(1)二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹;(2)二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3)二叉樹的前序序列與后序序列相同：空樹或只有根結點的二叉樹。2 .在哈希表中，發(fā)生沖突的可能性與哪些因素有關？為什么？答：主要與哈希函數(shù)、裝填因子“有關。如果用哈希函數(shù)計算的地址分布均勻，則沖突的可能性較小，如果裝填因子a較小，則哈希表較稀疏，發(fā)生沖突的可能性較小。六、綜合題(每小題5分，共15分)1 .已知一棵二叉樹的中序、后序序列分別如下:中序：D C E F B H G A K J LI M后序：D F E C H G B K L J M I

9、 A要求：畫出該二叉樹； 寫出該二叉樹的先序序列。先序：A B C D E F G H I J K L M2.在一段文字中，7個常用漢字及出現(xiàn)頻度如下：的 地 于 個 和 是 有;2019181715101要求：畫出對應的Huffman樹；求出每個漢字的 Huffman編碼。 01 的00 地111 于110 個101 和001 是1000 有3.請畫出右圖所示的樹所對應的二叉樹。七、算法設計題(15分)若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法：(1)統(tǒng)計二叉樹中葉結點的個數(shù)。(2)以二叉樹為參數(shù)，交換每個結點的左孩子和右孩子。(1)統(tǒng)計二叉樹中葉結點個數(shù)int leaf ( BinTreeNode * ptr ) if ( ptr = NULL ) return 0;else if ( ptr-> leftChild = NULL && ptr -> rightChild = NULL ) return 1;else return leaf ( ptr->leftChild ) + leaf ( ptr -> rightChild void exchange ( BinTreeNode * ptr )BinTre