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

1、第15頁華東理工大學(xué)網(wǎng)絡(luò)學(xué)院華東理工大學(xué)網(wǎng)絡(luò)學(xué)院《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》ch6樹和二叉樹、樹和二叉樹、ch8查找查找班級(jí)班級(jí)學(xué)號(hào)學(xué)號(hào)姓名姓名成績(jī)成績(jī)一、名詞解釋（每個(gè)一、名詞解釋（每個(gè)2分，共分，共10分）分）1.結(jié)點(diǎn)的度2.哈夫曼樹3.線索化4.二叉樹5.沖突答：1結(jié)點(diǎn)的度：結(jié)點(diǎn)的子樹的個(gè)數(shù)。2哈夫曼樹：帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為哈夫曼樹或者最優(yōu)二叉樹。3線索化：對(duì)二叉樹以某種次序進(jìn)行遍歷并且加以線索的過程。4二叉樹：滿足條件（1

2、）每個(gè)結(jié)點(diǎn)的度都不大于2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒；這樣的樹形結(jié)構(gòu)稱為二叉樹。5沖突：不同的關(guān)鍵字可能得到同一個(gè)哈希地址，這種現(xiàn)象稱為沖突。二、填空題（每空二、填空題（每空1分，共分，共20分）分）1.由樹轉(zhuǎn)換為二叉樹，其根節(jié)點(diǎn)的右子樹總是為空。2.深度為6（根層次為1）的二叉樹至多有26–1個(gè)結(jié)點(diǎn)。3.含17個(gè)結(jié)點(diǎn)的二叉樹的深度是5（設(shè)根結(jié)點(diǎn)的深度為1）。4.一棵高度為h的滿二叉樹共有2h1個(gè)終端結(jié)點(diǎn)。5.已知一棵完全

3、二叉樹的第5層有3個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是9。6.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須以.順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列。7.哈希表的查找效率主要取決于哈希表造表時(shí)選取的哈希函數(shù)和處理沖突的方法8.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的是哈希查找法。9.在分塊查找方法中，首先查找索引（表），然后再查找相應(yīng)的塊。10.由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左孩子是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的最左子結(jié)點(diǎn)，而N的右孩子是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的

4、最鄰近的右兄弟。11.在哈希存儲(chǔ)中，裝填因子α的值越大，則發(fā)生沖突的可能性就越大；α的值越小，則發(fā)生沖突的可能性就越小。12.N個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為n1。13.樹是結(jié)點(diǎn)的有限集合，它有0個(gè)或1個(gè)根結(jié)點(diǎn)，記為T。其余的結(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)（1≤i≤m）。一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)為該結(jié)點(diǎn)的度。三、判斷正誤（對(duì)的用三、

5、判斷正誤（對(duì)的用”T”表示，錯(cuò)誤的用表示，錯(cuò)誤的用”F”表示。每小題表示。每小題1分，共分，共10分）分）1.(T)具有n個(gè)結(jié)點(diǎn)的滿二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)為（n1）2。2.(F)用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)節(jié)點(diǎn)。第35頁10.設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大比較次數(shù)為C次。A5B6C7D8五、簡(jiǎn)答題（每小題五、簡(jiǎn)答題（每小題5分，共分，共10分）分）1.在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？答：

6、主要與哈希函數(shù)、裝填因子α有關(guān)。如果用哈希函數(shù)計(jì)算的地址分布均勻，則沖突的可能性較小，如果裝填因子α較小，則哈希表較稀疏，發(fā)生沖突的可能性較小。2.試分別找出滿足以下條件的所有二叉樹：(1)二叉樹的前序序列與中序序列相同；(2)二叉樹的中序序列與后序序列相同；(3)二叉樹的前序序列與后序序列相同。答：(1)二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹；(2)二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3)二叉樹的

7、前序序列與后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。六、綜合題（每小題六、綜合題（每小題5分，共分，共20分。分。）1已知一棵二叉樹的中序、后序序列分別如下：中序：DCEFBHGAKJLIM后序：DFECHGBKLJMIA要求：⑴畫出該二叉樹；⑵寫出該二叉樹的先序序列。答：先序：ABCDEFGHIJKLM2有關(guān)鍵字集合：53、17、19、61、98、75、79、63、46、49，哈希函數(shù)：H（key）=keymod13，采用開放定址法中的