數(shù)據(jù)結(jié)構(gòu)C語言版復(fù)習(xí)資料2

數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2一、選擇題1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？ ( B )A.隊列 B.二叉樹 C.棧 D.線性表設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為( B )。A.5，6，3，4，1，2 C.3，1，2，6，5，4B.3，2，5，6，4，1 D.1，5，4，6，2，33.設(shè)某二叉樹中度數(shù)為 0的結(jié)點數(shù)為 N0，度數(shù)為 1的結(jié)點數(shù)為 Nl，度數(shù)為2的結(jié)點數(shù)為 N2，則下列等式成立的是 ( C )。A.N0=N1+1 B.N0=Nl+N2 C.N0=N2+1 D.N0=2N1+l4.設(shè)某棵二叉樹中有 1000個結(jié)點，則該二叉樹的最小高度為 ( B )。A．9 B.10 C.11 D.125、在一棵具有 4層的滿二叉樹中結(jié)點總數(shù)為（ A ）。A.15 B.16 C. 17 D.326、設(shè)一棵二叉樹的中序遍歷序列： badce，后序遍歷序列： bdeca，則二叉樹先序遍歷序列為（ D ）。A.adbce B.decab C.debac D.abcde7.設(shè)有8個結(jié)點的無向圖，該圖至少應(yīng)有 ( C )條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為(C)。A.n，e B.2n，e C.n，2e D.e，n9.設(shè)無向圖 G中的邊的集合 E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點 b出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點序列為 ( A )。A.bacfde B.becfad C.bacedf D.beafdc二、填空題1.數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，分別是集合、線性、 樹形結(jié)構(gòu)和 網(wǎng)狀結(jié)構(gòu) 。1/6數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 22.數(shù)據(jù)元素之間的存儲結(jié)構(gòu)有兩種基本類型，分別是 順序存儲結(jié)構(gòu)和 鏈?zhǔn)酱鎯Y(jié)構(gòu) 。3.設(shè)輸入序列是1、2、3、??、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是n-i+1。4.設(shè)入棧序列為7、3、4、8，則通過棧的作用后可以得到的出棧序列為8、4、3、7。5.深度為k的二叉樹中最少有k個結(jié)點，最多有k個結(jié)點。2-16.二叉樹的第i層最多有2i-1個結(jié)點。7.樹中的一個節(jié)點擁有的子樹數(shù)稱為該節(jié)點的度。一棵樹的度是指該樹中節(jié)點的度的最大值，度為零的節(jié)點稱為葉結(jié)點，度不為零的節(jié)點稱為 分支結(jié)點 。8.設(shè)有n個結(jié)點的完全二叉樹， 如果按照從自上到下、 從左到右從 1開始順序編號，則第 i 個結(jié)點的雙親結(jié)點編號為 i/2 ，左孩子結(jié)點的編號為2i 。9、哈夫曼樹是其樹的帶權(quán)路徑長度 最短 的二叉樹。10、樹內(nèi)各結(jié)點度的 度的最大值 稱為樹的度。11.已知一有向圖的鄰接表存儲結(jié)構(gòu)如下： 從頂點 2出發(fā)，DFS(深度優(yōu)先)遍歷的輸出序列是 21345 ，BFS(廣度優(yōu)先 )遍歷的輸出序列是21345 。1234512.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為 e和n，所有頂點的度數(shù)之和為 b，則n=b/2 。三、綜合題2/6數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2下圖所示的樹：求樹的先根序列和后根序列；將此樹換為相應(yīng)的二叉樹；AB CE F GJ解：(1)樹的先根序列為： ABEJFCGDHI樹的后根序列為： JEFBGCHIDA將此樹轉(zhuǎn)換為相應(yīng)的二叉樹如下圖所示：2.已知二叉樹的前序遍歷序列是 ABCDEFGHIJ

DH IABE CDJ F GHI，中序遍歷序列是 BCAEDFHGIJ，試畫這棵二叉樹，并給出這棵樹后序遍歷的結(jié)果。A解：（1）這棵二叉樹如下圖所示：B DC E FGH I3/6J數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2(2)這棵樹后序遍歷序列為： CBEHJIGFDA3.給定權(quán)值集合 {12,04,15,02,08,10,16,19}，構(gòu)造相應(yīng)的 Huffman樹，并計算它的帶權(quán)外部路徑長度。86解：（1）構(gòu)造的 Huffman樹如下圖所示：513516 1929 2215 14 10 1206 0802 04(2)帶權(quán)外部路徑為： (16+19)*2+(15+10+12)*3+8*4+(4+2)*5=243請畫出下圖的鄰接矩陣和鄰接表。解：(1)鄰接矩陣如下：0 1 1 0 11 0 0 1 11 0 0 1 10 1 1 0 11 1 1 1 04/6數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2鄰接表如下圖所示：12345

1 2 40 3 40 3 41 2 40 1 2 35.已知一個圖的頂點集 V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)13,(1,3)6,(1,4)9,(2,5)12,(2,3)7,(3,4)15,(3,5)14,(3,6)10, (4,6)4,(4,7)20,(5,6)18,(6,7)26};分別畫出用普里姆(Prim)算法(從頂點1出發(fā))和克魯斯卡爾(Kruskal)算法得到最小生成樹，寫出在最小生成樹中依次得到的各條邊。解：（1）用普里姆算法構(gòu)造最小生成樹的過程如下所示：116661933374722(1)(2)(3)111666999333747420744447262126212655(4)(5)(6)依次得到的各條邊為：(1,3)6,(2,3)7,(1,4)9,(4,6)4,(2,5)12,(4,7)205/6數(shù)據(jù)結(jié)構(gòu) C語言版復(fù)習(xí)資料 2（2）用克魯斯卡爾算法構(gòu)造最小生成樹的過程如下所示：16161333444