數(shù)據(jù)結(jié)構(gòu)（本）形考作業(yè)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)（本）形考作業(yè)3一、單項(xiàng)選擇題（每小題2分，共38分）題目1假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。A. 47B. 15C. 16D. 17題目2二叉樹(shù)第k層上最多有（ ）個(gè)結(jié)點(diǎn)。A. B. 2kC. D. 2k-1題目3將含有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. 35B. 33C. 36D. 34題目4如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則該樹(shù)稱為（ ）。A. 平衡二叉樹(shù)B. 二叉樹(shù)

2、C. 哈夫曼樹(shù)D. 完全二叉樹(shù)題目5在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（ ）。A. 32B. 16C. 31D. 33題目6一棵完全二叉樹(shù)共有6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。A. 72B. 38C. 37D. 31題目7利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子結(jié)點(diǎn)中的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（ ）。A. 30B. 12C. 18D. 16題目8在一棵樹(shù)中，（ ）沒(méi)有前驅(qū)結(jié)點(diǎn)。A. 樹(shù)根結(jié)點(diǎn)B. 分支結(jié)點(diǎn)C. 空結(jié)點(diǎn)D. 葉結(jié)點(diǎn)題目9設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，該樹(shù)結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?則該樹(shù)有（ ）個(gè)葉結(jié)

3、點(diǎn)。A. 21B. 10C. 9D. 22題目10在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。A. 2B. 1C. 1/2D. 4題目11鄰接表是圖的一種（ ）。A. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B. 順序存儲(chǔ)結(jié)構(gòu)C. 索引存儲(chǔ)結(jié)構(gòu)D. 散列存儲(chǔ)結(jié)構(gòu)題目12圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的（ ）遍歷。A. 后序B. 中序C. 先序D. 層次題目13已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. V1V2V4V8V3V5V6V7B. V1V3V6V7V2V4V5V8C. V1V2V4V5V8V3V6V7D. V1V2V4V8V5V3V6

4、V7題目14已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. abecdfB. aedfcbC. aecbdfD. aebcfd題目15圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。A. 一對(duì)多B. 一對(duì)一C. 每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼D. 多對(duì)多題目16在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。A. 2i-1B. 2i+1C. 2i+2D. 2i題目17一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，共有（ ）層。(設(shè)根結(jié)點(diǎn)在第一層)A. 6B. 7C. 4D. 5題目18對(duì)二叉排序樹(shù)進(jìn)行（ ）遍

5、歷，可以使遍歷所得到的序列是有序序列。A. 前序B. 按層次C. 后序D. 中序題目19已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ ）。A. 2m+1B. m/2C. 2mD. m二、判斷題（每小題1分，共10分）題目20一棵二叉樹(shù)的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹(shù)共有11個(gè)結(jié)點(diǎn)。對(duì)題目21一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則它的最高層上有7個(gè)結(jié)點(diǎn)。對(duì)題目22一棵二叉樹(shù)有6個(gè)葉結(jié)點(diǎn)，則該樹(shù)總共有11個(gè)結(jié)點(diǎn)。錯(cuò)題目23根據(jù)搜索方法的不同，圖的遍歷有先序；中序；后序三種方法。錯(cuò)題目24對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n-1個(gè)指針域空。錯(cuò)題目25設(shè)一棵完

6、全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹(shù)一共有21個(gè)結(jié)點(diǎn)。對(duì)題目26設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9，該完全二叉樹(shù)一共有19個(gè)結(jié)點(diǎn)。錯(cuò)題目27按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。錯(cuò)題目28一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。錯(cuò)題目29一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2，則該樹(shù)共有15個(gè)結(jié)點(diǎn)。對(duì)三、程序填空題（每空6分，共12分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）題目30以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程

7、序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。Void Inorder (struct BTreeNode *BT)if(BT!=NULL)Inorder(BT->left);Inorder(BT->right)printf(“%c”,BT->data)利用上述程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是d,e,b,f,c,a;題目31以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void Inorder (

8、struct BTreeNode *BT)if(BT!=NULL)Inorder(BT->left);printf(“%c”,BT->data);Inorder(BT->right);利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是d,b,e,a,f,c;四、綜合應(yīng)用題（每小題8分，5題，共40分）題目32（1）以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)。該樹(shù)的帶權(quán)路徑長(zhǎng)度為（ ）A,64B.65C.62D.66（2）權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼編碼為（ ）。A.010B.0101C.000D.0111題目33（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)

9、的帶權(quán)路徑長(zhǎng)度為（ ）A,66B.80C.62D.87（2）權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為（ ）。A.0001B.1110C.001D.110題目34（1）已知某二叉樹(shù)的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹(shù)的根結(jié)點(diǎn)是（ ）A. eB. cC. bD. a（2）先序遍歷序列是（ ）。A. e,b,c,d,aB. c,a,b,d,eC. a,b,d,e,cD. a.c,b,d,e,題目35 （1）已知某二叉樹(shù)的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹(shù)的根結(jié)點(diǎn)是（ ）A. eB. cC. bD. a（2）后序遍歷序列為（ ）。A. e,d,b,c,aB. c,a,b,d,eC. a,b,d,e,cD. a.c,b,d,e,題目36（1）以給定權(quán)重值5，6，17，18，25，30，為葉結(jié)點(diǎn)，建立一棵哈夫曼樹(shù),該樹(shù)的中序遍歷序列為（ ）A. 5，11，28，6，17，58，30，101，18，43，25B. 5，