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

2、C. 哈夫曼樹D. 完全二叉樹題目5在一棵度具有5層的滿二叉樹中結點總數為（ ）。A. 32B. 16C. 31D. 33題目6一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（ ）個結點。A. 72B. 38C. 37D. 31題目7利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為（ ）。A. 30B. 12C. 18D. 16題目8在一棵樹中，（ ）沒有前驅結點。A. 樹根結點B. 分支結點C. 空結點D. 葉結點題目9設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數都為2，該樹結點中共有20個指針域為空,則該樹有（ ）個葉結

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

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

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

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

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

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

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