數(shù)據(jù)結(jié)構(gòu)(專)階段練習(xí)3

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

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

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

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

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

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

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

8、與后序序列相同。答：(1)二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹;(2)二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3)二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。2 .在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？答：主要與哈希函數(shù)、裝填因子“有關(guān)。如果用哈希函數(shù)計(jì)算的地址分布均勻，則沖突的可能性較小，如果裝填因子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個(gè)常用漢字及出現(xiàn)頻度如下：的 地 于 個(gè) 和 是 有;2019181715101要求：畫出對(duì)應(yīng)的Huffman樹；求出每個(gè)漢字的 Huffman編碼。 01 的00 地111 于110 個(gè)101 和001 是1000 有3.請(qǐng)畫出右圖所示的樹所對(duì)應(yīng)的二叉樹。七、算法設(shè)計(jì)題(15分)若用二叉鏈表作為二叉樹的存儲(chǔ)表示，試針對(duì)以下問題編寫遞歸算法：(1)統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。(2)以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左孩子和右孩子。(1)統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)個(gè)數(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