2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩12頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、1第六章第六章樹及二叉樹樹及二叉樹一、下面是有關(guān)二叉樹的敘述,請判斷正誤一、下面是有關(guān)二叉樹的敘述,請判斷正誤(√)1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu),則在n個結(jié)點(diǎn)的二叉樹鏈表中只有n—1個非空指針域。()2.二叉樹中每個結(jié)點(diǎn)的兩棵子樹的高度差等于1。(√)3.二叉樹中每個結(jié)點(diǎn)的兩棵子樹是有序的。()4.二叉樹中每個結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。()5.二叉樹中每個結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值,且小于

2、其右非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點(diǎn))()6.二叉樹中所有結(jié)點(diǎn)個數(shù)是2k11,其中k是樹的深度。(應(yīng)2i1)()7.二叉樹中所有結(jié)點(diǎn),如果不存在非空左子樹,則不存在非空右子樹。()8.對于一棵非空二叉樹,它的根結(jié)點(diǎn)作為第一層,則它的第i層上最多能有2i—1個結(jié)點(diǎn)。(應(yīng)2i1)(√)9.用二叉鏈表法(linkrlink)存儲包含n個結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的2n個指針區(qū)域中有n1個為空指針。(正確。用二叉鏈表存

3、儲包含n個結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)共有2n個鏈域。由于二叉樹中,除根結(jié)點(diǎn)外,每一個結(jié)點(diǎn)有且僅有一個雙親,所以只有n1個結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針,還有n1個空指針。)即有后繼鏈接的指針僅n1個。(√)10.具有12個結(jié)點(diǎn)的完全二叉樹有5個度為2的結(jié)點(diǎn)。最快方法:用葉子數(shù)=[n2]=6,再求n2=n01=5(?)11、哈夫曼樹中沒有度為1的結(jié)點(diǎn),所以必為滿二叉樹。(?)12、在哈夫曼樹中,權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。(?)13、線索二

4、叉樹是一種邏輯結(jié)構(gòu)。(√)14、深度為K的完全二叉樹至少有2K1個結(jié)點(diǎn)。(√)15、具有n個結(jié)點(diǎn)的滿二叉樹,其葉結(jié)點(diǎn)的個數(shù)為(n1)2。(√)16、前序和中序遍歷用線索樹方式存儲的二叉樹,不必使用棧。(╳)17、哈夫曼樹是帶權(quán)路徑長度最短的樹,路徑上權(quán)值較大的點(diǎn)離根較遠(yuǎn)。二、填空二、填空1由3個結(jié)點(diǎn)所構(gòu)成的二叉樹有5種形態(tài)。2.一棵深度為6的滿二叉樹有n1n2=0n2=n01=31個分支結(jié)點(diǎn)和261=32個葉子。注:滿二叉樹沒有度為1的

5、結(jié)點(diǎn),所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3一棵具有257個結(jié)點(diǎn)的完全二叉樹,它的深度為9。(注:用?log2(n)?1=?8.xx?1=94.設(shè)一棵完全二叉樹有700個結(jié)點(diǎn),則共有350個葉子結(jié)點(diǎn)。答:最快方法:用葉子數(shù)=[n2]=3503三、單項選擇題三、單項選擇題(C)1不含任何結(jié)點(diǎn)的空樹。(A)是一棵樹(B)是一棵二叉樹(C)是一棵樹也是一棵二叉樹(D)既不是樹也不是二叉樹答:以前的標(biāo)答是B,因為那時樹的定義是n≥1(C)2二叉樹是非

6、線性數(shù)據(jù)結(jié)構(gòu),所以。A、它不能用順序存儲結(jié)構(gòu)存儲B、它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲C、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲D、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用(C)3.具有n(n0)個結(jié)點(diǎn)的完全二叉樹的深度為。(A)?log2(n)?(B)?log2(n)?(C)?log2(n)?1(D)?log2(n)1?注1:?x?表示不小于x的最小整數(shù);?x?表示不大于x的最大整數(shù),它們與[]含義不同!注2:選(A)是錯誤的。例如當(dāng)n為2的整數(shù)冪時就

7、會少算一層。似乎?log2(n)1?是對的?(A)4把一棵樹轉(zhuǎn)換為二叉樹后,這棵二叉樹的形態(tài)是。(A)唯一的(B)有多種(C)有多種,但根結(jié)點(diǎn)都沒有左孩子(D)有多種,但根結(jié)點(diǎn)都沒有右孩子5.從供選擇的答案中,選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。樹是結(jié)點(diǎn)的有限集合,它A根結(jié)點(diǎn),記為T。其余的結(jié)點(diǎn)分成為m(m≥0)個B的集合T1,T2,…,Tm,每個集合又都是樹,此時結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn),Ti稱為T的子結(jié)

8、點(diǎn)(1≤i≤m)。一個結(jié)點(diǎn)的子結(jié)點(diǎn)個數(shù)為該結(jié)點(diǎn)的C。供選擇的答案A:①有0個或1個②有0個或多個③有且只有1個④有1個或1個以上B:①互不相交②允許相交③允許葉結(jié)點(diǎn)相交④允許樹枝結(jié)點(diǎn)相交C:①權(quán)②維數(shù)③次數(shù)(或度)④序答案:ABC=1,1,36.從供選擇的答案中,選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。二叉樹A。在完全的二叉樹中,若一個結(jié)點(diǎn)沒有B,則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹

溫馨提示

  • 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論