版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第15頁華東理工大學(xué)網(wǎng)絡(luò)學(xué)院華東理工大學(xué)網(wǎng)絡(luò)學(xué)院《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》ch6樹和二叉樹、樹和二叉樹、ch8查找查找班級班級學(xué)號學(xué)號姓名姓名成績成績一、名詞解釋(每個一、名詞解釋(每個2分,共分,共10分)分)1.結(jié)點的度2.哈夫曼樹3.線索化4.二叉樹5.沖突答:1結(jié)點的度:結(jié)點的子樹的個數(shù)。2哈夫曼樹:帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹或者最優(yōu)二叉樹。3線索化:對二叉樹以某種次序進(jìn)行遍歷并且加以線索的過程。4二叉樹:滿足條件(1
2、)每個結(jié)點的度都不大于2;(2)每個結(jié)點的孩子結(jié)點次序不能任意顛倒;這樣的樹形結(jié)構(gòu)稱為二叉樹。5沖突:不同的關(guān)鍵字可能得到同一個哈希地址,這種現(xiàn)象稱為沖突。二、填空題(每空二、填空題(每空1分,共分,共20分)分)1.由樹轉(zhuǎn)換為二叉樹,其根節(jié)點的右子樹總是為空。2.深度為6(根層次為1)的二叉樹至多有26–1個結(jié)點。3.含17個結(jié)點的二叉樹的深度是5(設(shè)根結(jié)點的深度為1)。4.一棵高度為h的滿二叉樹共有2h1個終端結(jié)點。5.已知一棵完全
3、二叉樹的第5層有3個結(jié)點,其葉子結(jié)點數(shù)是9。6.對線性表進(jìn)行二分查找時,要求線性表必須以.順序方式存儲,且結(jié)點按關(guān)鍵字有序排列。7.哈希表的查找效率主要取決于哈希表造表時選取的哈希函數(shù)和處理沖突的方法8.在各種查找方法中,平均查找長度與結(jié)點個數(shù)無關(guān)的是哈希查找法。9.在分塊查找方法中,首先查找索引(表),然后再查找相應(yīng)的塊。10.由樹轉(zhuǎn)換成的二叉樹里,一個結(jié)點N的左孩子是N在原樹里對應(yīng)結(jié)點的最左子結(jié)點,而N的右孩子是它在原樹里對應(yīng)結(jié)點的
4、最鄰近的右兄弟。11.在哈希存儲中,裝填因子α的值越大,則發(fā)生沖突的可能性就越大;α的值越小,則發(fā)生沖突的可能性就越小。12.N個結(jié)點的二叉樹采用二叉鏈表存放,共有空鏈域個數(shù)為n1。13.樹是結(jié)點的有限集合,它有0個或1個根結(jié)點,記為T。其余的結(jié)點分成為m(m≥0)個互不相交的集合T1,T2,…,Tm,每個集合又都是樹,此時結(jié)點T稱為Ti的父結(jié)點,Ti稱為T的子結(jié)點(1≤i≤m)。一個結(jié)點的子樹個數(shù)為該結(jié)點的度。三、判斷正誤(對的用三、
5、判斷正誤(對的用”T”表示,錯誤的用表示,錯誤的用”F”表示。每小題表示。每小題1分,共分,共10分)分)1.(T)具有n個結(jié)點的滿二叉樹,其葉結(jié)點的個數(shù)為(n1)2。2.(F)用一維數(shù)組存儲二叉樹時,總是以前序遍歷存儲節(jié)點。第35頁10.設(shè)有100個元素,用折半查找法進(jìn)行查找時,最大比較次數(shù)為C次。A5B6C7D8五、簡答題(每小題五、簡答題(每小題5分,共分,共10分)分)1.在哈希表中,發(fā)生沖突的可能性與哪些因素有關(guān)?為什么?答:
6、主要與哈希函數(shù)、裝填因子α有關(guān)。如果用哈希函數(shù)計算的地址分布均勻,則沖突的可能性較小,如果裝填因子α較小,則哈希表較稀疏,發(fā)生沖突的可能性較小。2.試分別找出滿足以下條件的所有二叉樹:(1)二叉樹的前序序列與中序序列相同;(2)二叉樹的中序序列與后序序列相同;(3)二叉樹的前序序列與后序序列相同。答:(1)二叉樹的前序序列與中序序列相同:空樹或缺左子樹的單支樹;(2)二叉樹的中序序列與后序序列相同:空樹或缺右子樹的單支樹;(3)二叉樹的
7、前序序列與后序序列相同:空樹或只有根結(jié)點的二叉樹。六、綜合題(每小題六、綜合題(每小題5分,共分,共20分。分。)1已知一棵二叉樹的中序、后序序列分別如下:中序:DCEFBHGAKJLIM后序:DFECHGBKLJMIA要求:⑴畫出該二叉樹;⑵寫出該二叉樹的先序序列。答:先序:ABCDEFGHIJKLM2有關(guān)鍵字集合:53、17、19、61、98、75、79、63、46、49,哈希函數(shù):H(key)=keymod13,采用開放定址法中的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)4
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)
- 數(shù)據(jù)結(jié)構(gòu)單元練習(xí)10
- 數(shù)據(jù)結(jié)構(gòu)(專)階段練習(xí)4
- 數(shù)據(jù)結(jié)構(gòu)應(yīng)用題練習(xí)
- 數(shù)據(jù)結(jié)構(gòu)與算法3
- 第3章_數(shù)據(jù)結(jié)構(gòu)
- 數(shù)據(jù)結(jié)構(gòu) 第3章 棧和隊列練習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)1-09答案
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題含答案
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 (3)
- 數(shù)據(jù)結(jié)構(gòu)
- 數(shù)據(jù)結(jié)構(gòu)練習(xí)題2及答案
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 (3)
- 數(shù)據(jù)結(jié)構(gòu)第3版習(xí)題答案
評論
0/150
提交評論