國家開放大學電大數(shù)據(jù)結構網(wǎng)絡課形考任務3作業(yè)及答案檔任務3一、單項選擇題（每小題2分，共38分）題目1假定一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30,則葉子結點數(shù)為（）。選擇一項：A. 47B. 16C. 17D. 15題目2二叉樹第k層上最多有（）個結點。選擇一項：A. 2k-lB. 2k-lC. 2k-lD. 2k題目3將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1,則編號 為69的結點的雙親結點的編號為（）。選擇一項：A. 36B. 35C. 34D. 33題目4如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（）。選擇一項：A. 二叉樹B. 哈夫曼樹C. 完全二叉樹D. 平衡二叉樹在一棵度具有5層的滿二又樹中結點總數(shù)為（)o選擇一項:A.16B.3231D.33題目6 一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（）個結點。選擇一項:A.31B.37C.38D.72題目7利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為（在一棵樹中，（）沒有前驅(qū)結點。).選擇一項:A.18B.16C.30D.12題目8選擇一項:A.樹根結點B.葉結點C.空結點D.分支結點題目9 設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2,該樹結點中共有20個指針域為空，則該樹有（ ）個葉結點。選擇一項:B. 10C. 21D. 22題目10在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。選擇一項：A. 2B. 1C. 4D. 1/2題目11鄰接表是圖的一種（）.選擇一項：A. 鏈式存儲結構B. 順序存儲結構C. 散列存儲結構D. 索引存儲結構題目12圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。選擇一項：A. 先序B. 后序C. 層次D. 中序題目13已知下圖所示的一個圖，若從頂點VI出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（選擇一項：A. V1V2V4V5V8V3V6V7B. V1V3V6V7V2V4V5V8C. V1V2V4V8V3V5V6V7D. V1V2V4V8V5V3V6V7題目14已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（選擇一項：A. aedfcbB. abecdfC. aebcfdD. aecbdf題目15圖狀結構中數(shù)據(jù)元素的位置之間存在（）的關系。選擇一項：A. 一對多B. 多對多C. 每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼D. 一對一題目16在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（選擇一項：A. 21+1B. 2i-lC. 2iD. 2i+2題目17一棵具有16個結點的完全二叉樹.共有（）層。（設根結點在第一層）選擇一項：A. 7B. 5C. 6D. 4題目18對二叉排序樹進行（）遍歷，可以使遍歷所得到的序列是有序序列。選擇一項：A. 按層次B. 申序C. 前序D. 后序題目19已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為（）選擇一項：A. m/2B. mC. 2siD. 2m+1二、判斷題（每小題1分，共10分）題目20一棵二叉樹的葉結點（終端結點）數(shù)為5,單分支結點數(shù)為2,該樹共有11個結點。選擇一項：對錯題目21一棵有14個結點的完全二叉樹，則它的最高層上有7個結點。選擇一項：對錯題目22一棵二叉樹有6個葉結點，則該樹總共有11個結點。選擇一項：對錯題目23根據(jù)搜索方法的不同，圖的遍歷有.先序：中序：后序三種方法。選擇一項：對錯題目24對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有n-1個指針域空。選擇一項：對題目25設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù)，該葉結點的雙親結點的編號為10,該完全二叉樹 一共有21個結點。選擇一項：對錯題目26設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數(shù)，該葉結點的雙親結點的編號為9,該完全二叉樹一共有19個結點。選擇一項：對錯題目27按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。選擇一項：對錯題目28一棵有8個權重值構造的哈夫曼數(shù)，共有17個結點。選擇一項：對錯題目29一棵有7個葉結點的二叉樹，其1度結點數(shù)的個數(shù)為2,則該樹共有15個結點。選擇一項：對錯三、程序4空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應的方框上）題目30以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結點）。完成程序中空格部分。voidInorder (struct BTreeNode *BT) if( BT!=NULL)lnorder(BT->left);lnorder(BT-> right) vprintf(”c“,BT->data)利用上述程序?qū)ψ髨D進行后序遍歷,結果是 d.e.b.f.c.a題目31以下程序是中序遍歷二義樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和 right,數(shù)據(jù)域data為字符型，BT指向根結點）。void Inorder (struct BTreeNode *BT)(if(BT!=NULL)(lnorder(BT->left);printf(”c”BT>data) v ;lnorder(BT->right) :利用上述程序?qū)τ覉D進行中序遍歷，結果是 d.b.e.a.f.G四、綜合應用題（每小題8分，5題，共40分）題目32（1 ）以3,4,5 , 8 , 9 ,作為口偷點的權,構造一棵哈夫曼樹.該樹的帶權路徑長度為B 寸A.64B.65C.62 D. 66（2）權重為3的葉結點的哈夫曼編碼為C U V .A.010B.0101C.000D.0111題目33(1 )以2,3,4.7 , 8 ,鋼乍為0偷點的權,構造一棵咕夫曼樹，岫的帝權路徑長度為B = 力A.66B.80 C. 62 D. 87(2)權重值為4的葉結點的哈夫曼編碼為C = /A.0001 B 1110 C.001 D. 110題目34(1) 已知某二叉樹的后序遍歷序列是debca,中序遍歷物是dbeac,該二叉樹的根結點是DU yA. e B. c C. b D. a(2) 先序遍歷序列是C y.A. e.b.c.d.a B. c.a(bMd.e C. a.b.d.e.c D. a.c.b.d.e,題目35(1)已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是eadcb,該二叉樹的根結點是D =A. eB. c C.b D. a(2 )后序遍歷序列為A V .A. e.d.b.c.a B. c.a.b.d.e C. a.b.d.e.c D. a.c.b.d.e.題目36(l)以給定權重值5, 6, 17, 18, 25, 30,為葉結點，建立一棵哈夫曼樹，該樹的中序遍歷序列為B #A. 5,11,28,6,17,58,30,101,18,43,25B.5,11,6,28,17,58,30,101,18,43,25C.5,11,6,28,101,58,30,17,18,43,25D.5,11,6,28,17,58,30,101,18,25,43(2)權重值為6的葉結點的哈夫曼為D = y .A. 1001B.011C.001D.0001