數(shù)據(jù)結(jié)構(gòu)第二單元測(cè)驗(yàn)答案

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

2、為K的完全二叉樹(shù)至少有()個(gè)結(jié)點(diǎn)A.2k–1B.2k1–1C.2k1D.2k6.深度為6的二叉樹(shù)最多有()個(gè)結(jié)點(diǎn)A64B.63C.32D.317.設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為()A.5B.6C.7D.88.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是()A.9B.11C.15D.不確定9.一棵完全二叉樹(shù)上有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)的二叉樹(shù)其高度為()A.nlog2nB.log2nC.?log2n?|1D.不確定11.將含有83個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始編號(hào)，根為1號(hào)，按從上到下.從左到右順序結(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙親結(jié)點(diǎn)編號(hào)為（）A.42B.40C.21D.2012.一個(gè)二叉樹(shù)按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹(shù)

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

5、索二叉樹(shù)中求中序前驅(qū)D.后序線索二叉樹(shù)中求后續(xù)后繼第3頁(yè)共5頁(yè)?log2k?1____。7.對(duì)一棵完全二叉樹(shù)，設(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)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)，共有_N1_____個(gè)空鏈域。9.在二叉樹(shù)中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_plchild==NULL&&prchlid==NULL_____。10.若一個(gè)二

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

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

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

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