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

1、數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)3（本部分作業(yè)覆蓋教材第6-7章的內(nèi)容）一、單項(xiàng)選擇題假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為（）。15B. 16C. 17D. 47 二叉樹(shù)第k層上最多有（）個(gè)結(jié)點(diǎn)。2kB. 2k-1C. 2k-1D. 2k-1 二叉樹(shù)的深度為k,則二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。2kB. 2k-1C. 2k-1D. 2k-1設(shè)某一二叉樹(shù)先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹(shù)后序遍歷的順序 是（ ）。abdec B.debac C.debca D.abedc 樹(shù)最適合于用來(lái)表示（）。線性結(jié)構(gòu)的數(shù)據(jù)順序結(jié)構(gòu)的數(shù)據(jù)元素之間無(wú)前驅(qū)和后繼關(guān)系的數(shù)據(jù)元

2、素之間有包含和層次關(guān)系的數(shù)據(jù)6 .設(shè)a,b為一棵二叉樹(shù)的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（）。A. a在 b 上方B. a在 b 下方C. a在b左方D. a在b右方權(quán)值為1，2, 6, 8的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是（）。A. 18B. 28C. 19D. 29將含有150個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行 編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（）。A. 33 B. 34C. 35 D. 36如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則 該樹(shù)稱為（）。A.哈夫曼樹(shù)B.平衡二叉樹(shù)C.二叉樹(shù)D.完

3、全二叉樹(shù)下列有關(guān)二叉樹(shù)的說(shuō)法正確的是（）。二叉樹(shù)中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必大于0完全二叉樹(shù)中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2二叉樹(shù)的度是2在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為 0的結(jié)點(diǎn)個(gè)數(shù)為（）。在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（）。A. 31B. 32C. 33 D. 16利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有（）個(gè)結(jié)點(diǎn)。A. nB. n+1C. 2*nD. 2*n-1利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有（）個(gè)雙支結(jié)點(diǎn)。A. nB. n-1C. n+1D. 2*n-1利用3、6、8、12這

4、四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有 葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（）。A. 18 B. 16C. 12D. 30在一棵樹(shù)中，（）沒(méi)有前驅(qū)結(jié)點(diǎn)。A.分支結(jié)點(diǎn)B.葉結(jié)點(diǎn)C.樹(shù)根結(jié)點(diǎn)D.空結(jié)點(diǎn)在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A. 2iB. 2i-1 D. 2i+1 C. 2i+2設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（）個(gè)非葉結(jié)點(diǎn)。A. nB. n-1 C. n+1D. 2n設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有（） 個(gè)結(jié)點(diǎn)。A. 2nB. 2n-1 C. 2n+1D. 2n+220 .一棵完全二叉樹(shù)共有5層，且第5層

5、上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有（）個(gè)結(jié)點(diǎn)。 TOC o 1-5 h z A. 20B. 21C. 23D. 30在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。A. 1/2B. 1C. 2D. 4在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A.鄰接矩陣表示法B.鄰接表表示法C.逆鄰接表表示法D.鄰接表和逆鄰接表在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（）。A. nB. n 1C. n 1D. n/224.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含（）條邊。A. n (n 1)B. n (n 1)C. n(n 1) /2 D. n (n 1)/225 .一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包

6、含（）條邊。A. n (n 1)B. n (n 1)C. n(n 1) /2 D. n (n 1)/2 TOC o 1-5 h z 對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A. nB.n2C.n 1 D.（n 1） 2對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為（）。A. nB. eC. 2n D. 2e對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（）。A. nB. eC. 2n D. 2e在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。C.入邊和出邊D.不是入邊也不是出邊30.在有向

7、圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。人.入邊B.出邊。.入邊和出邊D.不是入邊也不是出邊31.鄰接表是圖的一種（）。入.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是（）。A.完全圖B.連通圖 C.有回路 D. 一棵樹(shù) 下列有關(guān)圖遍歷的說(shuō)法不正確的是（）。連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征非連通圖不能用深度優(yōu)先搜索法圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次 無(wú)向圖的鄰接矩陣是一個(gè)（）。A.對(duì)稱矩陣B.零矩陣 C.上三角矩陣D.對(duì)角矩陣圖的深

8、度優(yōu)先遍歷算法類似于二叉樹(shù)的（）遍歷。A.先序B.中序 。.后序D.層次若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可已知下圖所示的一個(gè)圖， 能得到的一種頂點(diǎn)序列為（）。A. VVVVVVVV 1 2 4 8 3 5 6 7V V V V V V V V1 2 4 5 8 3 6 7D.V V V V V V V V24853671 3 6 7 2 4 5 8V V V V V V V V二、填空題結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的樹(shù)的度是指。度大于0的結(jié)點(diǎn)稱作 或。.度等于0的結(jié)點(diǎn)稱作 或。 在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的 或者說(shuō)每個(gè)結(jié)點(diǎn)的 稱為該結(jié)點(diǎn)的，簡(jiǎn)稱為孩子。 一個(gè)結(jié)點(diǎn)稱為其后繼結(jié)點(diǎn)的。 具有 的結(jié)

9、點(diǎn)互稱為兄弟結(jié)點(diǎn)，簡(jiǎn)稱為兄弟。 每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的。 從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的。樹(shù)的深度或高度是指。m(m 0)棵互不相交的樹(shù)的集合稱為。度為k的樹(shù)中的第i層上最多有 結(jié)點(diǎn)。深度為k的二叉樹(shù)最多有 結(jié)點(diǎn)。 在一棵二叉樹(shù)中，如果樹(shù)中的每一層都是滿的，則稱此樹(shù)為; 但如果出最后一層外，其余層都是滿的，并且最后一層是滿的，或者是在缺少若干連續(xù)個(gè)結(jié) 點(diǎn)，則稱此二叉樹(shù)為。15 .具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是。先序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操 作，訪問(wèn)二叉樹(shù)的；先序遍歷二叉樹(shù)的，先序遍歷二叉樹(shù)的_中序遍歷二叉樹(shù)的的操作

10、定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操 作，中序遍歷二叉樹(shù)的；訪問(wèn)而叉樹(shù)的，中序遍歷二叉樹(shù)的_后序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操 作，后序遍歷二叉樹(shù)的；后序遍歷二叉樹(shù)的，訪問(wèn)而叉樹(shù)的_將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn)的。樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的。哈夫曼樹(shù)又稱為，它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶 權(quán)路徑長(zhǎng)度WPL。若以4, 5, 6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度 是。23 .具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有 結(jié)點(diǎn)。在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是一

11、種 的關(guān)系。一的鄰接矩陣表示法是用一個(gè) 來(lái)表示圖中頂點(diǎn)之間的相鄰關(guān)系。鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的。 圖的遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中各做 訪問(wèn)的過(guò)程。 圖的深度優(yōu)先搜索遍歷類似于樹(shù)的 遍歷。圖的廣度優(yōu)先搜索類似于樹(shù)的 遍歷。具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為。具有n個(gè)頂點(diǎn)的無(wú)向圖至少有 條邊，才能確保其為一個(gè)連通圖。圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 和。 一個(gè)AOV網(wǎng)（頂點(diǎn)活動(dòng)圖）應(yīng)該是一 。即不應(yīng)該帶有回路，否則 回路上的所有活動(dòng)都。用鄰接矩陣存儲(chǔ)有向圖G,其第i行的所有元素之和等于頂點(diǎn)i的。在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)。在一個(gè)帶權(quán)圖中，兩

12、頂點(diǎn)之間的最段路徑最多經(jīng)過(guò) 條邊。為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié) 構(gòu)為。三、綜合題1.寫(xiě)出如下圖所示的二叉樹(shù)的先序、中序和后序遍歷序列。已知某二叉樹(shù)的先序遍歷結(jié)果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn) 和J，它的中序遍歷結(jié)果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請(qǐng)畫(huà)出這棵二叉樹(shù)，并寫(xiě)出該二叉樹(shù)后續(xù)遍歷的結(jié)果。3 .已知一棵完全二叉樹(shù)共有892個(gè)結(jié)點(diǎn)，求樹(shù)的高度葉子結(jié)點(diǎn)數(shù)單支結(jié)點(diǎn)數(shù)最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)給出滿足下列條件的所有二叉樹(shù)。先序和中序相同中序和后序相同先序和后序相同假設(shè)通信用的報(bào)文由9個(gè)字母A、B、C、D、E、F、G

13、、H和I組成，它們出現(xiàn)的 頻率分別是：10、20、5、15、8、2、3、7和30。請(qǐng)請(qǐng)用這9個(gè)字母出現(xiàn)的頻率作為權(quán) 值求：設(shè)計(jì)一棵哈夫曼樹(shù)；計(jì)算其帶權(quán)路徑長(zhǎng)度WPL;寫(xiě)出每個(gè)字符的哈夫曼編碼。請(qǐng)根據(jù)以下帶權(quán)有向圖G給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié) 點(diǎn)序列；給出G的一個(gè)拓?fù)湫蛄?；給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最短路徑。已知無(wú)向圖G描述如下：G= (V, E)V=V1, V2, V3, V4, V5E= (V1, V2), (V1, V4), (V2, V4), (V3, V4), (V2, V5), (V3, V4), (V3, V5)畫(huà)出G的圖示；然后給出G的

14、鄰接矩陣和鄰接表；寫(xiě)出每個(gè)頂點(diǎn)的度?；卮鹣铝袉?wèn)題：對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣的無(wú)向圖，如何判斷下列有關(guān)問(wèn)題?圖中有多少條邊？任意兩頂點(diǎn)間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接表的有向圖，如何判斷下列有關(guān)問(wèn)題？圖中有多少條邊？圖中是否存在從V.到V,的邊？如何求頂點(diǎn)V的入度和出度？.四、程序填空題下面函數(shù)的功能是返回二叉樹(shù)BT中值為X的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地 方填寫(xiě)合適內(nèi)容。int NodeLevel(struct BinTreeNode* BT, char X) if(BT=NULL) return 0;/*空樹(shù)的層號(hào)為 0*/else if(BT-data=X)

15、return 1; /*根結(jié)點(diǎn)的層號(hào)為 1*/*向子樹(shù)中查找X結(jié)點(diǎn)*/else int c1=NodeLevel(BT-left,X);if(c1=1)(1);int c2=(2);if(3);/若樹(shù)中不存在X結(jié)點(diǎn)則返回0 else return 0;下面函數(shù)的功能是按照?qǐng)D的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹(shù)中的 各條邊，請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適內(nèi)容。void dfstree(adjmatrix GA, int i, int n)int j;visited i=1;(1)if(GAij!=0 & GAij!=MaxValue & !visitedj)printf(%d,%d)%d,”,i,j,GAij);(2)五、算法設(shè)計(jì)