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

C習(xí)資料2wword下載即可編輯??！PAGE2PAGE2做一 、選擇題

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

B DC E FGPAGE5PAGE5做8853221111110000(2)這棵樹(shù)后序遍歷序列為：CBEHJIGFDA3給定權(quán)值集合12,04,15,02,08,10,16,19，構(gòu)造相應(yīng)的 n樹(shù)，并計(jì)算它的帶權(quán)外部路徑長(zhǎng)度。解：（1）構(gòu)造的 Huffman樹(shù)如下圖所示：(2)帶權(quán)外部路徑為：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=243請(qǐng)畫(huà)出下圖的鄰接矩陣和鄰接表。解：(1)鄰接矩陣如下：011011011001110011011011 1 1 1 0(2)鄰接表如下圖所示：1231234512403403412401231234已知一個(gè)圖的頂點(diǎn)集 V和邊集 E分別為：(6,7)26};分別畫(huà)出用普里姆(Prim)算法(從頂點(diǎn) 1出發(fā))和克魯斯卡爾(Kruskal)算法得到最小生成樹(shù)，寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。解：（1）用普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程如下所示：6613613761372(2)6193742(3)619374420721265619619374426619374421265(4)

(5)

(6)依次得到的各條邊為： 136,237,149,464,2512,47201（2）用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程如：1