國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案

國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案形考任務3一、單項選擇題（每小題2分，共38分）題目1假定一棵二叉樹中，雙分支結點數(shù)為15，單分支結點數(shù)為30，則葉子結點數(shù)為（）。選擇一項：B.16題目2二叉樹第k層上最多有（）個結點。選擇一項：A.2k-1題目3將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1，則編號為69的結點的雙親結點的編號為（）。選擇一項：C.34題目4如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（）。選擇一項：B.哈夫曼樹題目5在一棵度具有5層的滿二叉樹中結點總數(shù)為（）。選擇一項：C.31題目6一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（）個結點。選擇一項：B.37題目7利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為（）。選擇一項：A.18題目8在一棵樹中，（）沒有前驅(qū)結點。選擇一項：A.樹根結點題目9設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2，該樹結點中共有20個指針域為空,則該樹有（）個葉結點。選擇一項：B.10題目10在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。選擇一項：A.2題目11鄰接表是圖的一種（）。選擇一項：A.鏈式存儲結構題目12圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。選擇一項：A.先序題目13已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（）。選擇一項：D.V1V2V4V8V5V3V6V7題目14已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（）。選擇一項：D.aecbdf題目15圖狀結構中數(shù)據(jù)元素的位置之間存在（）的關系。選擇一項：B.多對多題目16在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（）。選擇一項：A.2i+1題目17一棵具有16個結點的完全二叉樹，共有（）層。(設根結點在第一層)選擇一項：B.5題目18對二叉排序樹進行（）遍歷，可以使遍歷所得到的序列是有序序列。選擇一項：B.中序題目19已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（）。選擇一項：C.2m二、判斷題（每小題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個結點。選擇一項：對三、程序填空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應的方框上）題目30以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結點）。完成程序中空格部分。題目31以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格