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

下載本文檔

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

文檔簡(jiǎn)介

1、第1頁共5頁數(shù)據(jù)結(jié)構(gòu)第二單元測(cè)驗(yàn)答案數(shù)據(jù)結(jié)構(gòu)第二單元測(cè)驗(yàn)答案一、選擇題1.由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹()A.2B.3C.4D.52.由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹()A.2B.3C.4D.53.二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為()A.2IB.2I11C.2I1D.2I14.一棵二叉樹高度為h所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹最少有()結(jié)點(diǎn)A.2hB.2h1C.2h1D.h1除第一層外每層最少2個(gè)結(jié)點(diǎn)5.一棵樹高

2、為K的完全二叉樹至少有()個(gè)結(jié)點(diǎn)A.2k–1B.2k1–1C.2k1D.2k6.深度為6的二叉樹最多有()個(gè)結(jié)點(diǎn)A64B.63C.32D.317.設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中的葉子數(shù)為()A.5B.6C.7D.88.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)個(gè)數(shù)是()A.9B.11C.15D.不確定9.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是()A.2

3、50B.500C.254D.505E以上答案都不對(duì)10.對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹其高度為()A.nlog2nB.log2nC.?log2n?|1D.不確定11.將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào),根為1號(hào),按從上到下.從左到右順序結(jié)點(diǎn)編號(hào),那么編號(hào)為41的雙親結(jié)點(diǎn)編號(hào)為()A.42B.40C.21D.2012.一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中,如圖01234567891011121314ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹

4、的第()層。A.1B.2C.3D.413.某二叉樹的先序序列和后序序列正好相反,則該二叉樹一定是()的二叉樹A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子D.任一結(jié)點(diǎn)無右孩子14.任何一棵二叉樹的葉結(jié)點(diǎn)在其先根.中根.后根遍歷序列中的相對(duì)位置()A.肯定發(fā)生變化B.有時(shí)發(fā)生變化C.肯定不發(fā)生變化D.無法確定15.二叉樹線索化后,仍不能有效求解的問題是()A.先序線索二叉樹中求先序后繼B.中序線索二叉樹中求中序后繼C.中序線

5、索二叉樹中求中序前驅(qū)D.后序線索二叉樹中求后續(xù)后繼第3頁共5頁?log2k?1____。7.對(duì)一棵完全二叉樹,設(shè)一個(gè)結(jié)點(diǎn)的編號(hào)為i,若它的左孩子結(jié)點(diǎn)存在,則其編號(hào)為2i;若右孩子結(jié)點(diǎn)存在,則其編號(hào)為2i1;而雙親結(jié)點(diǎn)的編號(hào)為?i2?。8.具有N個(gè)結(jié)點(diǎn)的二叉樹,采用二叉鏈表存儲(chǔ),共有_N1_____個(gè)空鏈域。9.在二叉樹中,指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_plchild==NULL&&prchlid==NULL_____。10.若一個(gè)二

6、叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn),則它必是該子樹的__前序____序列中的最后一個(gè)結(jié)點(diǎn)。11.在有n個(gè)頂點(diǎn)的有向圖中,若要使任意兩點(diǎn)間可以互相到達(dá),則至少需要_n___條弧。12.如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán),則它有___n____棵生成樹。13.為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索,除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外,還需__隊(duì)列__存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。14.求圖的最小生成樹有兩種算法,__克魯斯卡爾____算法

7、適合于求稀疏圖的最小生成樹。三、判斷題1.樹與二叉樹是兩種不同的樹型結(jié)構(gòu)?!?.度為二的樹就是二叉樹。3.在二叉樹的第i層上至少有2i1個(gè)結(jié)點(diǎn)(i=1)。4.完全二叉樹一定存在度為1的結(jié)點(diǎn)。5.若一棵二叉樹的任一非葉子結(jié)點(diǎn)的度為2,則該二叉樹為滿二叉樹(X)6.一個(gè)樹的葉結(jié)點(diǎn),在前序遍歷和后序遍歷下,皆以相同的相對(duì)位置出現(xiàn)。√7.若某二叉樹的葉子結(jié)點(diǎn)數(shù)為1,則其先序序列和后序序列一定相反(√)8.二叉樹的前序遍歷并不能唯一確定這棵樹,但

8、是如果我們還知道該樹的根結(jié)點(diǎn)是那一個(gè),則可以確定這棵二叉樹。9.已知一棵樹的先序序列和后序序列,一定能構(gòu)造出該樹(√)10.哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹,路徑上權(quán)值較大的結(jié)點(diǎn)離根較近?!?1.有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。12.一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)可能不等。13.在無向圖的深度優(yōu)先遍歷算法中,DFS(從某個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖的算法)被調(diào)用了幾次就說明該圖有幾個(gè)聯(lián)通分量。(√)14.需要借

9、助于一個(gè)隊(duì)列來實(shí)現(xiàn)DFS算法(深度優(yōu)先遍歷)。15.廣度遍歷生成樹描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。16.既使有向無環(huán)圖的拓?fù)湫蛄形ㄒ?,也不能唯一確定該圖。17.在AOE圖中,關(guān)鍵路徑上某個(gè)活動(dòng)的時(shí)間縮短,整個(gè)工程的時(shí)間也就必定縮短。四、解答題1.已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ中序遍歷的結(jié)果是KBCDAFHIGJ試畫出這棵二叉樹。當(dāng)前序序列為ABKCDFGHIJ,中序序列為KBCDAFHIGJ時(shí),逐步形成二叉樹的過程

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論