數(shù)據(jù)結(jié)構(gòu)-6-10章自測(cè)題及答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上自測(cè)題（6-10章）一、填空題1、 二叉樹(shù)第i(i>=1)層上至多有_個(gè)結(jié)點(diǎn)，深度為k(k>=1)的二叉樹(shù)至多有_個(gè)結(jié)點(diǎn)。2、 對(duì)任何二叉樹(shù)，若度為2的節(jié)點(diǎn)數(shù)為n2，則葉子數(shù)n0=_。3、 滿二叉樹(shù)上各層的節(jié)點(diǎn)數(shù)已達(dá)到了二叉樹(shù)可以容納的_，滿二叉樹(shù)也是_二叉樹(shù)，但反之不然。4、 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)。5、 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中,一共有_個(gè)指針域,其中只有_個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的_個(gè)指針域?yàn)镹ULL。6、 二叉樹(shù)有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中最常用的是_與_。7、 若二叉樹(shù)的一個(gè)葉子是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的

2、后根遍歷序列中的_個(gè)結(jié)點(diǎn)。8、 由_轉(zhuǎn)換成二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。9、 哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度_的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根_。10、 有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，其結(jié)點(diǎn)總數(shù)為_(kāi)。11、 已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)中有_個(gè)葉子結(jié)點(diǎn)。12、 具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)。13、 N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有_條邊。14、 無(wú)向圖的鄰接矩陣是一個(gè)_矩陣，有向圖的鄰接矩陣不一定是_矩陣。15、 一個(gè)具有n個(gè)頂點(diǎn)的完全無(wú)向圖的邊數(shù)為_(kāi)，一個(gè)具有n個(gè)頂點(diǎn)的完全有向圖的弧數(shù)為_(kāi)。16、 遍歷圖的基本方法有_優(yōu)先搜索和_優(yōu)先搜索兩種

3、。17、 在有向圖的鄰接矩陣上，由第i行可得到第_個(gè)結(jié)點(diǎn)的_，而由第j列可得到第_個(gè)結(jié)點(diǎn)的_。18、 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素_比較大小。19、 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是_。20、 若在線性表中采用二分查找法查找元素，該線性表應(yīng)該元素_，且采用_結(jié)構(gòu)。21、 對(duì)二叉排序樹(shù)進(jìn)行_遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的有序序列。二、單項(xiàng)選擇題1 以下說(shuō)法錯(cuò)誤的是 ( )樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼樹(shù)形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)

4、雜的數(shù)據(jù)樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)2. 深度為6的二叉樹(shù)最多有( )個(gè)結(jié)點(diǎn) 64 63 32 313. 設(shè)二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度為 ( )n-1 n floor(log2n)+1 無(wú)法確定4. 下列說(shuō)法中正確的是 ( )任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2任何一棵二叉樹(shù)中的度肯定等于2任何一棵二叉樹(shù)中的度可以小于25. 設(shè)森林T中有4棵樹(shù)，第一、二、三、四棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹(shù)后，根結(jié)點(diǎn)的右子樹(shù)上有（ ）個(gè)結(jié)點(diǎn)。n1-1 n1 n1+n2+n3 n2+n3+n4 6.

5、 森林T中有4棵樹(shù)，第一、二、三、四棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹(shù)后，根結(jié)點(diǎn)的左子樹(shù)上有（ ）個(gè)結(jié)點(diǎn)。n1-1 n1 n1+n2+n3 n2+n3+n47. 已知某二叉樹(shù)的后續(xù)遍歷序列是dabec,中序遍歷序列是deabc,它的前序遍歷序列是（ ）acbed deabc decab cedba8. 設(shè)二叉樹(shù)結(jié)點(diǎn)的先根序列、中根序列和后根序列中，所有葉子結(jié)點(diǎn)的先后順序( )都不相同 完全相同 先序和中序相同，而與后序不同 中序和后序相同，而與先序不同9. 以下說(shuō)法錯(cuò)誤的是 ( )哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。若一個(gè)二叉樹(shù)

6、的樹(shù)葉是某子樹(shù)的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)。已知二叉樹(shù)的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹(shù)，因?yàn)椴恢罉?shù)的根結(jié)點(diǎn)是哪一個(gè)。在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)的之后。10. 任何一個(gè)帶權(quán)的無(wú)向連通圖的最小生成樹(shù)（ ）只有一棵 有一棵或多棵 一定有多棵 可能不存在11. 在無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的（ ）倍。0.5 1 2 412. 在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的（ ）倍。 0.5 1 2 4 13. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（ ）條邊能確保是一個(gè)連通圖。 5 6 7

7、 814. 以下說(shuō)法正確的是 （ ）連通圖的生成樹(shù)，是該連通圖的一個(gè)極大連通子圖。無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。任何一個(gè)有向圖，其全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄小Ｓ谢芈返膱D不能進(jìn)行拓?fù)渑判颉?5. 利用逐點(diǎn)插入法建立序列(51，71，43，81，74，20，34，45，64，30)對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素34要進(jìn)行( )次元素間的比較。 3 4 5 616. 哈希表的平均查找長(zhǎng)度是( )的函數(shù)。哈希表的長(zhǎng)度 表中元素的多少 哈希函數(shù) 裝填因子三、簡(jiǎn)答及應(yīng)用題1、已知一棵二叉樹(shù)的中根序列和后根序列分別為BDCEAFHG和EDCBHGEA，試畫出這棵二叉樹(shù)。2、分別

8、給出簡(jiǎn)答題11.1圖中樹(shù)的先根、后根和層次遍歷的結(jié)點(diǎn)訪問(wèn)序列。3、設(shè)某密碼電文由8個(gè)字母組成，每個(gè)字母在電文中的出現(xiàn)頻率分別是7，19，2，6，32，3，21，10，試為這8個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼編碼。4、分別給出圖簡(jiǎn)答題3中從v5出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點(diǎn)序列。5、圖簡(jiǎn)答題17-1所示為一無(wú)向連通圖，構(gòu)造出它的最小生成樹(shù)。6、若一棵排序二叉樹(shù)的關(guān)鍵字輸入序列為7，8，25，80，10，100，6， 90，請(qǐng)畫出該二叉樹(shù)。7、已知一組關(guān)鍵字為1,14,27,29,55,68,10,11,23，則按哈希函數(shù)H(key)=key MOD 11和鏈地址法處理沖突來(lái)構(gòu)造哈希表。

9、（1）畫出所構(gòu)造的哈希表。（2）在記錄的查找概率相等的前提下，計(jì)算該表查找成功時(shí)的平均查找長(zhǎng)度。8、對(duì)于關(guān)鍵字序列65，97，76，49，38，13，回答下述問(wèn)題：（1）寫出一趟冒泡排序的結(jié)果；（2）寫出一趟快速排序的結(jié)果。一、填空題1、 2i-1，2k-12、 n2+13、 最大值、完全4、 floor(log2n)+15、 2n、n-1、n+16、 二叉鏈表、三叉鏈表7、 第一個(gè)8、 樹(shù)9、 最短、較近10、 2m-111、 1212、 4513、 N-114、 對(duì)稱、 對(duì)稱15、 n(n-1)/2、n(n-1)16、 深度、廣度17、 i、出度、j、入度18、 28，6，12，2019、 散列查找 20、 按值有序、順序存儲(chǔ)21、 中序二、單項(xiàng)選擇題1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 11、 12、 13、 14、 15、 16、三、簡(jiǎn)答及應(yīng)用題1、略2、先根序列：A B E F K L C G D H I J；后根序列：E K L F B G C H I J D A；層次序列：A B C D E F G H I J K L。3、第一步，先以給定的權(quán)值構(gòu)造出哈夫曼樹(shù)，如圖簡(jiǎn)答題18所示。第二步，假?zèng)]規(guī)