數(shù)據(jù)結構第二單元測驗答案

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

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

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

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

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

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

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

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

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