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

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

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

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

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

5、上有六個結(jié)點，該樹共有（）個結(jié)點。 TOC o 1-5 h z A. 20B. 21C. 23D. 30在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。A. 1/2B. 1C. 2D. 4在一個有像圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A.鄰接矩陣表示法B.鄰接表表示法C.逆鄰接表表示法D.鄰接表和逆鄰接表在圖的存儲結(jié)構(gòu)表示中，表示形式唯一的是（）。A. nB. n 1C. n 1D. n/224.一個具有n個頂點的無向完全圖包含（）條邊。A. n (n 1)B. n (n 1)C. n(n 1) /2 D. n (n 1)/225 .一個具有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 對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A. nB.n2C.n 1 D.（n 1） 2對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（）。A. nB. eC. 2n D. 2e對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（）。A. nB. eC. 2n D. 2e在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。C.入邊和出邊D.不是入邊也不是出邊30.在有向

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

8、度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。A.先序B.中序 。.后序D.層次若從頂點V1出發(fā)，按深度優(yōu)先搜索法進(jì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é)點的度是指結(jié)點所擁有的樹的度是指。度大于0的結(jié)點稱作 或。.度等于0的結(jié)點稱作 或。 在一棵樹中，每個結(jié)點的 或者說每個結(jié)點的 稱為該結(jié)點的，簡稱為孩子。 一個結(jié)點稱為其后繼結(jié)點的。 具有 的結(jié)

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

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

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

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

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

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

15、return 1; /*根結(jié)點的層號為 1*/*向子樹中查找X結(jié)點*/else int c1=NodeLevel(BT-left,X);if(c1=1)(1);int c2=(2);if(3);/若樹中不存在X結(jié)點則返回0 else return 0;下面函數(shù)的功能是按照圖的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的 各條邊，請在劃有橫線的地方填寫合適內(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è)計