數(shù)據(jù)結(jié)構(gòu)本形成性考核作業(yè)及講評(píng)-參考素材累積資料

1、數(shù)據(jù)結(jié)構(gòu)本形成性考核作業(yè)及講評(píng)（本局部作業(yè)覆蓋教材第6-7章的內(nèi)容）一、單項(xiàng)選擇題L假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為 30,那么葉子結(jié)點(diǎn)數(shù)為（）。A. 15 B. 16 C. 17 D. 47 2.二叉樹(shù)第k層上最多有（） 個(gè)結(jié)點(diǎn)。2k（k-l）2k-l2-12k.二叉樹(shù)的深度為k,那么二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。2k2k-l2k-lk2-1.設(shè)某一二叉樹(shù)先序遍歷為abdec,中序遍歷為dbeac,那么 該二叉樹(shù)后序遍歷的順序是（）。A. abdec B. debac C. debca D. abedc.樹(shù)最適合于用來(lái)表示（）。A.線性結(jié)構(gòu)的數(shù)據(jù)B.順序結(jié)構(gòu)的數(shù)據(jù)C.元素之間無(wú)

2、前驅(qū)和后繼關(guān)系的數(shù)據(jù)D.元素之間有包含和層次關(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右方7.權(quán)值為1, 2, 6, 8的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路 徑長(zhǎng)度是（）。A. 18 B. 28 C. 19 D. 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. 34 C. 35 D. 36.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù) 的帶權(quán)路徑長(zhǎng)度最小，那么該樹(shù)稱為（

3、）。A.哈夫曼樹(shù)B.平衡二叉樹(shù)C.二叉樹(shù)D.完全二叉樹(shù).以下有關(guān)二叉樹(shù)的說(shuō)法正確的選項(xiàng)是（）。A.二叉樹(shù)中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1B.二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必大于0C.完全二叉樹(shù)中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2D.二叉樹(shù)的度是211.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,那么度為0的結(jié)點(diǎn)個(gè)數(shù)為（）。A. 4 B. 5 C. 6 D. 7.在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（）。A. 31 B. 32 C. 33 D. 16.利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有 （）個(gè)結(jié)點(diǎn)。A. n B. n+1 C. 2*n D. 2*nT.利用

4、n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有 （）個(gè)雙支結(jié)點(diǎn)。A. n B. n-1 C. n+1 D. 2*n-1 15.利用 3、 6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該 樹(shù)中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（）。A. 18 B. 16 C. 12 D. 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ù)中，假設(shè)編號(hào)為i的結(jié)點(diǎn)存在右孩子，那么右 孩子的順序編號(hào)為（）。A. 2i B. 2i-l D. 2i+l C. 2i+2 18.設(shè) 一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，那么該樹(shù)有（）個(gè)非葉結(jié)點(diǎn)。A. n B. n-1 C. n+1 D.

5、 2n 19.設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉 結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,那么該樹(shù)共有（）個(gè)結(jié)點(diǎn)。A. 2n B. 2n-l C. 2n+l D. 2n+2 20. 一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有()個(gè)結(jié)點(diǎn)。A. 20 B. 21C. 23 D. 30.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和 的()倍。A. 1/2 B. 1 C. 2 D. 4.在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的 出度之和的()倍。A.鄰接矩陣表示法B.鄰接表表示法C.逆 鄰接表表示法D.鄰接表和逆鄰接表.在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是()。A. n B. nl C. n

6、l D. n/2 24. 一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完 全圖包含()條邊。A. n (nl) B. n (nl) C. n (nl) /2 D. n (nl) /2一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含()條邊。A. n (nl) B. n (nl) C. n (nl) /2 D. n (nl) /226.對(duì)于具有n個(gè)頂點(diǎn)的圖，假設(shè)采用鄰接矩陣表示，那么該矩 陣的大小為()。22A. n B. n C. nl D. (nl)27.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，假設(shè)采用鄰接 表表示，那么表頭向量的大小為()。A. n B. e C. 2n D. 2e28.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，假設(shè)

7、采用鄰接表表示，那么所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（）。A. n B. e C. 2n D. 2e.在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所 有（）鄰接點(diǎn)。A.入邊B.出邊C.入邊和出邊D.不是入邊也不是出邊.在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn) 所有（）鄰接點(diǎn)。A.入邊B.出邊C.入邊和出邊D.不是 入邊也不是出邊31.鄰接表是圖的一種（）。A.順序存儲(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ù)33.以下有關(guān) 圖遍歷的說(shuō)法不正確的選項(xiàng)

8、是（）。A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特 征C.非連通圖不能用深度優(yōu)先搜索法D.圖的遍歷要求每一頂 點(diǎn)僅被訪問(wèn)一次34.無(wú)向圖的鄰接矩陣是一個(gè)（）。A.對(duì)稱矩陣B.零矩陣C.上三角矩陣D.對(duì)角矩陣35.圖 的深度優(yōu)先遍歷算法類似于二叉樹(shù)的（）遍歷。A.先序B.中 序C.后序D.層次36.以下圖所示的一個(gè)圖，假設(shè)從頂點(diǎn)VI出發(fā)，按深度優(yōu)先 搜索法進(jìn)行遍歷，那么可能得到的一種頂點(diǎn)序列為（）。A. V1V2V4V8V3V5V6V7 B. V1V2V4V5V8V3V6V7C. V1V2V4V8V5V3V6V7 D. V1V3V6V7V2V4V

9、5V8I2 V3二、填空題4 V5 V6 V7 V8 1.結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的。2.樹(shù)的度是指。3.度大于0的結(jié)點(diǎn)稱作或。4.度等 于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é)點(diǎn)互稱為兄弟結(jié)點(diǎn)，簡(jiǎn)稱為兄弟。8.每個(gè)結(jié) 點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的。9.從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的。 10.樹(shù)的深度或高度是指。11. m（niO）棵互不相交的樹(shù)的集合稱為。12.度為k的樹(shù)中 的第i層上最多有 結(jié)點(diǎn)。13.深度為k的二叉樹(shù)最多有 結(jié)點(diǎn)。.在一棵二叉樹(shù)中，如果樹(shù)中的每一層都是滿的，那么稱此

10、 樹(shù)為；但如果出最后一層外，其余層都是滿的，并且最后一層 是滿的，或者是在缺少假設(shè)干連續(xù)個(gè)結(jié)點(diǎn)，那么稱此二叉樹(shù)為。.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是。16.先序遍歷 二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空，那么為空操作，否那么進(jìn)行 如下操作，訪問(wèn)二叉樹(shù)的；先序遍歷二叉樹(shù)的，先序遍歷二叉 樹(shù)的。.中序遍歷二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空，那么為 空操作，否那么進(jìn)行如下操作，中序遍歷二叉樹(shù)的；訪問(wèn)而叉樹(shù)的，中序遍歷二叉樹(shù) 的。.后序遍歷二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空，那么為 空操作，否那么進(jìn)行如下操作，后序遍歷二叉樹(shù)的；后序遍歷二 叉樹(shù)的，訪問(wèn)而叉樹(shù)的。.將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)

11、數(shù)，稱此實(shí)數(shù)為 該結(jié)點(diǎn)的。20.樹(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。.假設(shè)以4, 5, 6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù), 那么其帶權(quán)路徑長(zhǎng)度是。.具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有 結(jié)點(diǎn)。.在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是一種 的關(guān)系。.圖的鄰接矩陣表示法是用一個(gè) 來(lái)表示圖中頂點(diǎn)之間的相 鄰關(guān)系。26.鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的。.圖的遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法 對(duì)圖中各做訪問(wèn)的過(guò)程。.圖的深度優(yōu)先搜索遍歷類似于樹(shù)的 遍歷。29.圖的廣 度優(yōu)先搜索類似于樹(shù)的遍歷。.具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為。30.具有n個(gè)頂點(diǎn)的無(wú)向圖至少有 條邊，才能確保其為一個(gè) 連通圖。31.圖常用的兩種存儲(chǔ)結(jié)構(gòu)