第6章樹和二叉樹一、下面是有關(guān)二叉樹的敘述，請判斷正誤（每小題1分，共10分）（）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)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（）6.二叉樹中所有結(jié)點(diǎn)個數(shù)是2"-1，其中k是樹的深度。（）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（）8?對于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2—1個結(jié)點(diǎn)。（）9.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個指針區(qū)域中有n+1個為空指針。（）10.具有12個結(jié)點(diǎn)的完全二叉樹有5個度為2的結(jié)點(diǎn)。二、填空由3個結(jié)點(diǎn)所構(gòu)成的二叉樹有 種形態(tài)。一棵深度為6的滿二叉樹有 個分支結(jié)點(diǎn)和 個葉子。一棵具有257個結(jié)點(diǎn)的完全二叉樹，它的深度為設(shè)一棵完全二叉樹有700個結(jié)點(diǎn)，則共有 個葉子結(jié)點(diǎn)。設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，則此完全二叉樹有—個葉子結(jié)點(diǎn)，有 個度為2的結(jié)點(diǎn)，有個結(jié)點(diǎn)只有非空左子樹，有 個結(jié)點(diǎn)只有非空右子樹。一棵含有n個結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為 .，最小深度為—_。二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按 次序）和中序法（也稱對稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是FEBGCHD，則它的后序序列必是 。&中序遍歷的遞歸算法平均空間復(fù)雜度為 。9?用5個權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度—三、單項選擇題((((）1.不含任何結(jié)點(diǎn)的空樹 （A((((）1.不含任何結(jié)點(diǎn)的空樹 （A）是一棵樹； （B）是一棵二叉樹；（C）是一棵樹也是一棵二叉樹； （D）既不是樹也不是二叉樹）2.二叉樹是非線性數(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)都不能使用）3?具有n（n>0）個結(jié)點(diǎn)的完全二叉樹的深度為 (A)「log2(n)] (B)Llog2(n)」(C)Llog2(n)」+14.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是(D)「log2(n)+1]。A唯一的BA唯一的C有多種，但根結(jié)點(diǎn)都沒有左孩子（D有多種，但根結(jié)點(diǎn)都沒有右孩子從供選擇的答案中，選出應(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é)點(diǎn)（1WiWm）。一個結(jié)點(diǎn)的子結(jié)點(diǎn)個數(shù)為該結(jié)點(diǎn)的_C 。

供選擇的答案A：①有供選擇的答案A：①有0個或1個B:①互不相交C：①權(quán)②有0個或多個②允許相交②維數(shù)有且只有1個③允許葉結(jié)點(diǎn)相交③次數(shù)(或度)有1個或1個以上④允許樹枝結(jié)點(diǎn)相交④序6?從供選擇的答案中，選出應(yīng)填入下面敘也內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。二叉樹丄。在完全的二叉樹中，若一個結(jié)點(diǎn)沒有B，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點(diǎn)N的左子女是N在原樹里對應(yīng)結(jié)點(diǎn)的—，而N的右子女是它在原樹里對應(yīng)結(jié)點(diǎn)的—供選擇的答案A：①是特殊的樹 ②不是樹的特殊形式③是兩棵樹的總稱④有是只有二個根結(jié)點(diǎn)的樹形結(jié)構(gòu)B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn)④兄弟C?D：①最左子結(jié)點(diǎn) ②最右子結(jié)點(diǎn)③最鄰近的右兄弟 ④最鄰近的左兄弟最左的兄弟⑥最右的兄弟第7章圖一、單選題(每題1分，共16分)TOC\o"1-5"\h\z( )1.在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。A.12 B.1 C.2 D.4( )2.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。A.1/2 B.1 C?2 D.4( )3.有8個結(jié)點(diǎn)的無向圖最多有 條邊。A.14 B.28 C.56 D.112( )4.有8個結(jié)點(diǎn)的無向連通圖最少有 條邊。A.5 B?6 C.7 D.8( )5.有8個結(jié)點(diǎn)的有向完全圖有 條邊。A.14 B.28 C.56 D.112( )6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用 來實(shí)現(xiàn)算法的。A.棧 B.隊列 C.樹 D.圖( )7.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用 來實(shí)現(xiàn)算法的。A.棧 B.隊列 C?樹 D.圖)8.已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是024315601365420243156013654204231650361542100100110001001100110101101000011011100010)9.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0243156B.0135642 C.0423165D.0134256

)10.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243651 B.0136425 C.0423156D.0134256)11.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243165 B.0135642 C.0123465D.0123456)12.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A.0132A.0132C?0321B?0231D?0123則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是)13?已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是)13?已知圖的鄰接表如下所示，根據(jù)算法，A.0321B.0123C.0132D.0312)14?深度優(yōu)先遍歷類似于二叉樹的A.先序遍歷 B.中序遍歷C?后序遍歷D?層次遍歷)15?廣度優(yōu)先遍歷類似于二叉樹的A.先序遍歷 A.先序遍歷 B.中序遍歷C?后序遍歷D?層次遍歷)16?任何一個無向連通圖的最小生成樹A.只有一棵 A.只有一棵 B.一棵或多棵C?一定有多棵D?可能不存在注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一)二、填空題(每空1分，共20分)圖有 、 等存儲結(jié)構(gòu)，遍歷圖有 、 等方法。有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點(diǎn)i的 如果n個頂點(diǎn)的圖是一個環(huán)，則它有——棵生成樹。 (以任意一頂點(diǎn)為起點(diǎn)，得到n-1條邊)TOC\o"1-5"\h\zn個頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲，則空間復(fù)雜度為_ _n個頂點(diǎn)e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為_ —設(shè)有一稀疏圖G,則G采用一_存儲較省空間。設(shè)有一稠密圖G,則G采用 存儲較省空間。圖的逆鄰接表存儲結(jié)構(gòu)只適用于 圖。已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點(diǎn)出發(fā)的方法是 。圖的深度優(yōu)先遍歷序列——惟一的。11?n個頂點(diǎn)e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復(fù)雜度為— ；若采用鄰接表存儲時，該算法的時間復(fù)雜度為 。n個頂點(diǎn)e條邊的圖釆用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復(fù)雜度為— _；若采用鄰接表存儲，該算法的時間復(fù)雜度為 。圖的BFS生成樹的