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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)（本）形考作業(yè)3一、單項選擇題（每小題2分，共38分）題目1假定一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（ ）。A. 47B. 15C. 16D. 17題目2二叉樹第k層上最多有（ ）個結(jié)點。A. B. 2kC. D. 2k-1題目3將含有150個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為69的結(jié)點的雙親結(jié)點的編號為（ ）。A. 35B. 33C. 36D. 34題目4如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（ ）。A. 平衡二叉樹B. 二叉樹

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

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

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

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

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

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

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

9、的帶權(quán)路徑長度為（ ）A,66B.80C.62D.87（2）權(quán)重值為4的葉結(jié)點的哈夫曼編碼為（ ）。A.0001B.1110C.001D.110題目34（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結(jié)點是（ ）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）已知某二叉樹的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹的根結(jié)點是（ ）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é)點，建立一棵哈夫曼樹,該樹的中序遍歷序列為（ ）A. 5，11，28，6，17，58，30，101，18，43，25B. 5，