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

...wd......wd......wd...數(shù)據(jù)構(gòu)造C語言版復(fù)習(xí)資料2一、選擇題1.以下數(shù)據(jù)構(gòu)造中哪一個(gè)是非線性構(gòu)造(B)A.隊(duì)列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，4B.3，2，5，6，4，1 D.1，5，4，6，2，33.設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則以下等式成立的是(C)。 A.N0=N1+1 B.N0=Nl+N2 C.N0=N2+1 D.N0=2N1+l4.設(shè)某棵二叉樹中有1000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為(B)。A．9B.10 C.11 D.125、在一棵具有4層的滿二叉樹中結(jié)點(diǎn)總數(shù)為〔A〕。A.15 B.16 C.17 D.326、設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為〔D〕。A.adbce B.decab C.debac D.abcde7.設(shè)有8個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(C)條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.88.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為(C)。A.n，eB.2n，eC.n，2eD.e，n 9.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)b出發(fā)進(jìn)展深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為(A)。 A.bacfde B.becfad C.bacedfD.beafdc填空題數(shù)據(jù)元素之間的邏輯構(gòu)造有四種基本類型，分別是集合、線性、樹形構(gòu)造和網(wǎng)狀構(gòu)造。數(shù)據(jù)元素之間的存儲(chǔ)構(gòu)造有兩種基本類型，分別是順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。3.設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是n-i+1。4.設(shè)入棧序列為7、3、4、8，則通過棧的作用后可以得到的出棧序列為8、4、3、7。5.深度為k的二叉樹中最少有k個(gè)結(jié)點(diǎn)，最多有2k-1個(gè)結(jié)點(diǎn)。6.二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)。7.樹中的一個(gè)節(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個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開場(chǎng)順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為i/2，左孩子結(jié)點(diǎn)的編號(hào)為2i。9、哈夫曼樹是其樹的帶權(quán)路徑長(zhǎng)度最短的二叉樹。10、樹內(nèi)各結(jié)點(diǎn)度的度的最大值稱為樹的度。11.一有向圖的鄰接表存儲(chǔ)構(gòu)造如下：從頂點(diǎn)2出發(fā)，DFS(深度優(yōu)先)遍歷的輸出序列是21345，BFS(廣度優(yōu)先)遍歷的輸出序列是21345。22341512.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為e和n，所有頂點(diǎn)的度數(shù)之和為b，則n=b/2。三、綜合題1.以以下列圖所示的樹：(1)求樹的先根序列和后根序列；(2)將此樹換為相應(yīng)的二叉樹；AABCDEFIHGJAABCDEFGHIJ解：(1)樹的先根序列為：ABEJFCGDHI樹的后根序列為：JEFBGCHIDA(3)將此樹轉(zhuǎn)換為相應(yīng)的二叉樹如以以下列圖所示：ABDCEFGHABDCEFGHIJ解：〔1〕這棵二叉樹如以以下列圖所示：(2)這棵樹后序遍歷序列為：CBEHJIGFDA2951140608020435161922101215863295114060802043516192210121586解：〔1〕構(gòu)造的Huffman樹如以以下列圖所示：(2)帶權(quán)外部路徑為：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434.請(qǐng)畫出以以下列圖的鄰接矩陣和鄰接表。解：(1)鄰接矩陣如下：0110110011100110110111110(2)鄰接表如以以下列圖所示：011212412030342303034341212445321032105.一個(gè)圖的頂點(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)造最小生成樹的過程如下所示：949416372163721163(3)(1)(2)(3)(1)(2)2072071254694163721254694163724469416372(6)(5)(4)(6)(5)(4)依次得到的各條邊為：(1,3)6,(2,3)7,(1,4)9,(4,6)4,(2,5)12,(4,7)20〔2〕用克魯斯卡爾算法構(gòu)造最小生成樹的過程如下所示：754754642136754642136775