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

數(shù)據(jù)結(jié)構(gòu)C語言版復(fù)習(xí)資料2一、選擇題1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( B ) A. 隊列 B. 二叉樹 C. 棧 D. 線性表2.設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為( B )。 A. 5，6，3，4，1，2 C. 3，1，2，6，5，4 B. 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 )。 A9 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. 88.設(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. beafdc2、 填空題1. 數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，分別是集合、線性、 樹形結(jié)構(gòu) 和 網(wǎng)狀結(jié)構(gòu) 。2. 數(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é)點，最多有 2k-1 個結(jié)點。6.二叉樹的第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 。 23415 12.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為e和n，所有頂點的度數(shù)之和為b，則n= b/2 。三、綜合題1.下圖所示的樹： (1) 求樹的先根序列和后根序列； (2) 將此樹換為相應(yīng)的二叉樹；ABCDEFIHGJABCDEFGHIJ解：(1) 樹的先根序列為：ABEJFCGDHI樹的后根序列為：JEFBGCHIDA(3) 將此樹轉(zhuǎn)換為相應(yīng)的二叉樹如下圖所示：ABDCEFGHIJ2.已知二叉樹的前序遍歷序列是ABCDEFGHIJ，中序遍歷序列是BCAEDFHGIJ，試畫這棵二叉樹，并給出這棵樹后序遍歷的結(jié)果。解：（1）這棵二叉樹如下圖所示：(2) 這棵樹后序遍歷序列為：CBEHJIGFDA2951140608020435161922101215863.給定權(quán)值集合12,04,15,02,08,10,16,19，構(gòu)造相應(yīng)的Huffman樹，并計算它的帶權(quán)外部路徑長度。解：（1）構(gòu)造的Huffman樹如下圖所示：(2)帶權(quán)外部路徑為：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434.請畫出下圖的鄰接矩陣和鄰接表。解：(1)鄰接矩陣如下：0110110011100110110111110(2)鄰接表如下圖所示：011241203423034341244532105.已知一個圖的頂點集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)造最小生成樹的過程如下所示：941637216372163(3)(1)(2)207125469416372125469416372469416372(6)(5)(4)依次得到的各條邊為：(1,3)6, (2,3)7, (1,4)9, (4,6)4, (2,5)12, (4,7)20（2）用克魯斯卡爾算法構(gòu)造最小生成樹的過程如下所示：754642136754642136775464213