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

1、據(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.隊(duì)列B.二叉樹C.棧D.線性表2 .設(shè)輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為（B）。A. 5,6,3,4,1,2C.3,1,2,6,5,4B. 3,2,5,6,4,1D.1,5,4,6,2,33 .設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為NO,度數(shù)為1的結(jié)點(diǎn)數(shù)為N1,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,則下列等式成立的是（C）oA.NO=Nl+1B.NO=N1+N2C.NO=N2+1D.NO=2N1+14 .設(shè)某棵二叉樹中有1000個結(jié)點(diǎn)，則該二叉樹的最小高度為（B）。A.9B

2、.10C.11D.125、在一棵具有4層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（AA.15B.16C.17D.326、設(shè)一棵二叉樹的中序遍歷序列：badce,后序遍歷序列：bdeca,則二叉樹先序遍歷序列為（D）。A.adbceB.decabC.debacD.abcde7 .設(shè)有8個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（C）條邊才能確保是一個連通圖。A.5B.6C.7D.88 .設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（C）。A.n,eB2n,eC.n,2eD.e,n9 .設(shè)無向圖G中的邊的集合E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),

3、則從頂點(diǎn)b出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為(A)。A.bacfdeB.beefadC.bacedfD.beafde二、填空題1 .數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，分別是集合、線性、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)O2 .數(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-1+l34 .設(shè)入棧序列為7、3、4、8,則通過棧的作用后可以得到的出棧序列為上4、3、7o5 .深度為k的二叉樹中最少有k個結(jié)點(diǎn),最多有2匚1個結(jié)點(diǎn)。6 .二叉樹的第i層最多有2個結(jié)點(diǎn)。7 .樹中

4、的一個節(jié)點(diǎn)擁有的子樹數(shù)稱為該節(jié)點(diǎn)的度。一棵樹的度是指該樹中節(jié)點(diǎn)的度的最大值，度為零的節(jié)點(diǎn)稱為葉結(jié)點(diǎn)，度不為零的節(jié)點(diǎn)稱為分支結(jié)點(diǎn)。8 .設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始L順序編號，則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為i/2,左孩子結(jié)點(diǎn)的編號為2io9、哈夫曼樹是其樹的帶權(quán)路徑長度最短的二叉樹。10、樹內(nèi)各結(jié)點(diǎn)度的度的最大值稱為樹的度。11 .已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點(diǎn)2出發(fā)，DFS(深度優(yōu)先)遍歷的輸出序列是21345，BFS(廣度優(yōu)先)遍歷的輸出序列是21345圖的鄰接表存楮結(jié)構(gòu)12 .設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為e和n,所有頂點(diǎn)的度數(shù)之和為b,則n=b/

5、2三、綜合題1 .下圖所示的樹：(1)求樹的先根序列和后根序列;(2)將此樹換為相應(yīng)的二叉樹；解：(1)樹的先根序列為：ABEJFCGDHI樹的后根序列為：JEFBGCHIDA(3)將此樹轉(zhuǎn)換為相應(yīng)的二義樹如下圖所示:2 .已知二叉樹的前序遍歷序列是ABCDEFGHIJ,中序遍歷序列是BCAEDFHGIJ,試畫這棵二叉樹，并給出這棵樹后十二的結(jié)果。解：(1)這棵二叉樹如下圖所示：(2)這棵樹后序遍歷序列為：CBEHJIGFDA3 .給定權(quán)值集合12,04,15,02,08,10,16,19,構(gòu)造相應(yīng)的Huffman樹,并計(jì)算它的帶權(quán)外部路徑長度。(7解：(1)構(gòu)造的Huffman樹如下圖所示：

6、/一(2)帶權(quán)外部路徑為：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434 .請畫出下圖的鄰接矩陣和鄰接表。解：(1)鄰接矩陣如下：飛1101一10011100110110111110鄰接表如下圖所示:5 .已知一個圖的頂點(diǎn)集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)算法(從頂點(diǎn)1出發(fā)）和克魯斯卡爾（Kruskal）算法得到最小生成樹，寫出在最小生成樹中依次得到的各條邊。解：（1）用普里姆算法構(gòu)造最小生成樹的過程如下所示:依次得到的各條邊為：(1,3