【正文】 叉樹(shù)中，沒(méi)有右孩子的結(jié)點(diǎn)一定是葉結(jié)點(diǎn)。 ( )(8)在結(jié)點(diǎn)數(shù)目一定的前提下，各種形態(tài)的二叉樹(shù)中，完全二叉樹(shù)具有最小深度。 (9)滿二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的度不是0就是2。 ( )(10)在所有深度相同的二叉樹(shù)中，滿二叉樹(shù)具有最大結(jié)點(diǎn)數(shù)目。 ( )(11)由二叉樹(shù)的前序序列和中序序列可以唯一地確定一棵二叉樹(shù)。 ( )(12)由二叉樹(shù)的中序序列和后序序列可以唯一地確定一棵二叉樹(shù)。 ( )(13)由二叉樹(shù)的前序序列和后序序列可以唯一地確定一棵二叉樹(shù)。 ( ) (14)哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。 ( )(15)滿二叉樹(shù)一定是完全二叉樹(shù)。 ( )二、單項(xiàng)選擇題。 (1)樹(shù)型結(jié)構(gòu)最適合用來(lái)描述( )。 A．有序的數(shù)據(jù)元素 B．無(wú)序的數(shù)據(jù)元素 C．?dāng)?shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù) D．?dāng)?shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù) (2)按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有( )種形態(tài)(不考慮數(shù)據(jù)信息的組合情況)。 A．2 B．3 C．4 D．5 (3)若一棵二叉樹(shù)有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的葉結(jié)點(diǎn)的個(gè)數(shù)是( )。 A．9 B．11 C．12 D．不確定 (4)若一棵滿二叉樹(shù)有2047個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)為( )。 A．512 B．1024 C．2048 D．4096 (5)深度為h的滿二叉樹(shù)的第i層有( )個(gè)結(jié)點(diǎn)。(i≤h) ( ) A．2i—1 B．2i1 C．2h—1 D．2h1 (6)深度為h的滿二叉樹(shù)共有( )個(gè)結(jié)點(diǎn)。(ih) A．22h1 B．22h1 C．2h1 D．2h1 (7)若某完全二叉樹(shù)的深度為h，則該完全二叉樹(shù)中至少有( )個(gè)結(jié)點(diǎn)。 A．2h B．2h1 c．2h+1 D．2h—1三、填空題。 (1)任何非空樹(shù)中有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，該結(jié)點(diǎn)就是樹(shù)的______ ______。 (2)樹(shù)的層次定義為_(kāi)___________________。 (3)度為k的樹(shù)中第i層最多有______________個(gè)結(jié)點(diǎn)(i≥1)。 (4)深度為h的k叉樹(shù)最多有_______ _____________個(gè)結(jié)點(diǎn)。 (5)非空二叉樹(shù)一共有_______________種基本形態(tài)。 (6)非空二叉樹(shù)中第i層最多有______________個(gè)結(jié)點(diǎn)。 (7)深度為h的二叉樹(shù)最多有_____________________________個(gè)結(jié)點(diǎn)。 (8)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度h=____________________。 (9)若二叉樹(shù)有N0個(gè)葉結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則N0與n2的關(guān)系是________ ______。 (10)若具有n個(gè)結(jié)點(diǎn)的非空二叉樹(shù)．樹(shù)有N0個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)有_______ _____個(gè)度為2的結(jié)點(diǎn)，___________個(gè)度為1的結(jié)點(diǎn)。 (11)對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按照層次從上到下，每一層從左到右的次序?qū)λ薪Y(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為_(kāi)_____________，左孩子的編號(hào)為_(kāi)______________，右孩子的編號(hào)為_(kāi)_____________。 (12)若具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，則該鏈表中有_____________個(gè)指針域，其中有________________個(gè)指針域用于鏈接孩子結(jié)點(diǎn)，______________個(gè)指針域空閑存放著NULL。 (13)已知二叉樹(shù)的前序遍歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，其后序遍歷序列為_(kāi)_________。 (14)已知某完全二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的存放次序?yàn)锳，B，C，D，E，F(xiàn)，G，H，I，J，該完全二叉樹(shù)的后序序列為_(kāi)____ _______。(15)具有N0個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)共有__________個(gè)結(jié)點(diǎn)。 第七章 圖習(xí) 題 一、 判斷題(在你認(rèn)為正確的題后的括號(hào)中打√，否則打X)。 (1)n個(gè)頂點(diǎn)的無(wú)向圖最多有n(n1)條邊。 ( ) (2)在有向圖中，所有頂點(diǎn)的人度之和等于所有頂點(diǎn)的出度之和。 ( ) (3)在無(wú)向圖中，若頂點(diǎn)i到頂點(diǎn)j有路徑，則這兩個(gè)頂點(diǎn)之間是連通的。 ( ) (4)在有向圖中，若頂點(diǎn)i到頂點(diǎn)j有路徑，則這兩個(gè)頂點(diǎn)之間是連通的。 ( ) (5)連通圖的最小生成樹(shù)是唯一的。 ( ) (6若表示某圖的鄰接矩陣不是對(duì)稱(chēng)矩陣，則該圖一定是有向圖。 ( ) (7)對(duì)于同一個(gè)有向圖，鄰接表中的邊結(jié)點(diǎn)數(shù)目與逆鄰接表中邊結(jié)點(diǎn)數(shù)目相等。 ( ) (8)無(wú)向圖的鄰接表中邊結(jié)點(diǎn)數(shù)目一定為偶數(shù)。 ( )(9) 設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為e=d。 ( ) 二、單項(xiàng)選擇題。 (1)在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的( )倍。 A．1／2 B．1 C．2 D．4 (2)一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有( )條邊。 A．n(n1)／2 B．n(n1) C．n(n+1)/2 D．n(2) (3)一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有( )條邊。 A．n(n1)/2 B．n(n1) C．n(n+1)/2 D．n(2) (4)在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要( )條邊。 A．n B．n+1 C．n1 D．2n (5)具有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)一定有( )條邊。 A．n B．n+1 C．n1 D．2n (6)在帶權(quán)圖中，兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度是( )。 A．路徑上的頂點(diǎn)數(shù)目 B．路徑上的邊的數(shù)目 C．路徑上頂點(diǎn)和邊的數(shù)目 D．路徑上所有邊上的權(quán)值之和 (7)若具有n個(gè)頂點(diǎn)的無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，該鄰接矩陣一定為一個(gè)( )。 A．一般矩陣 B．對(duì)稱(chēng)矩陣 C．對(duì)角矩陣 D．稀疏矩陣 (8)若圖的鄰接矩陣中主對(duì)角線上的元素均為0，其余元素全為1，則可以斷定該圖一定 ( ). A．是無(wú)向圖 B．是有向圖 C．是完全圖 D．不是帶權(quán)圖 (9)有向圖的鄰接表的第i個(gè)鏈表中的邊結(jié)點(diǎn)數(shù)目是第i個(gè)頂點(diǎn)的( )。 A．度數(shù) B．出度 C．人數(shù) D．邊數(shù) (10)若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為奇數(shù)，則該圖( )。 A．一定有奇數(shù)個(gè)頂點(diǎn) B．一定有偶數(shù)個(gè)頂點(diǎn) C．一定是有向圖 D?？赡苁菬o(wú)向圖 (11)若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為偶數(shù)，則該圖( )。 A．一定是無(wú)向圖 B。可能是有向圖 C．可能是無(wú)向圖，也可能是有向圖 D．一定有偶數(shù)個(gè)頂點(diǎn) (12)若無(wú)向圖有k條邊，則相應(yīng)的鄰接表中就有( )個(gè)邊結(jié)點(diǎn)。 A．k1 B．k C．2k D．K2 (13)若有向圖有k條邊，則相應(yīng)的鄰接表中就有( )個(gè)邊結(jié)點(diǎn)。 A．k1 B．k C．2k D．K2 (14)對(duì)于一個(gè)不帶權(quán)的無(wú)向圖的鄰接矩陣而言，( )。 A．矩陣中非零元素的數(shù)目等于圖中邊的數(shù)目 B．矩陣中非全零的