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

一、單項(xiàng)選擇題（每小題2分，共32分）題目1假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為（）。選擇一項(xiàng)：17161547題目2二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：2k2k-12k-12k-1題目3設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（）。選擇一項(xiàng)：debacabdecabedcdebca題目4將含有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（）。選擇一項(xiàng)：36353334題目5如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（）。選擇一項(xiàng)：A.平衡二叉樹B.完全二叉樹C.哈夫曼樹D.二叉樹題目6在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（）。選擇一項(xiàng)：7654題目7在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）。選擇一項(xiàng)：31321633題目8利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：2*nn2*n-1n+1題目9利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長帶權(quán)路徑長度為（）。選擇一項(xiàng)：16181230題目10在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。選擇一項(xiàng)：A.樹根結(jié)點(diǎn)B.分支結(jié)點(diǎn)C.空結(jié)點(diǎn)D.葉結(jié)點(diǎn)題目11設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,則該樹共有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：2n-12n+12nD.2n+2題目12在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。選擇一項(xiàng)：421/21題目13鄰接表是圖的一種（）。選擇一項(xiàng)：A.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.散列存儲(chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)題目14如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（）。選擇一項(xiàng)：A.有回路B.一棵樹C.完全圖D.連通圖題目15圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。選擇一項(xiàng)：A.先序B.層次C.后序D.中序題目16已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。選擇一項(xiàng)：V1V2V4V5V8V3V6V7V1V2V4V8V3V5V6V7V1V2V4V8V5V3V6V7V1V3V6V7V2V4V5V8二、1填空題,（每小題1分，共20分）題目17結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的子樹樹木或后繼結(jié)點(diǎn)數(shù)題目18樹的度是指樹中所有結(jié)點(diǎn)的度的最大值題目19度大于0的結(jié)點(diǎn)稱作或。分支結(jié)點(diǎn)、非終端結(jié)點(diǎn)題目20滿分1.00度等于0的結(jié)點(diǎn)稱作或。葉子結(jié)點(diǎn)、非終端結(jié)點(diǎn)題目21在一棵樹中，每個(gè)結(jié)點(diǎn)的或者說每個(gè)結(jié)點(diǎn)的稱為該結(jié)點(diǎn)的 ，簡稱為孩子。子樹的根、后繼結(jié)點(diǎn)、孩子結(jié)點(diǎn)題目22從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先題目23樹的深度或高度是指樹中結(jié)點(diǎn)的最大層數(shù)題目24具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是。[log2ri]+1題目25先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，訪問二叉樹的根結(jié)點(diǎn)；先序遍歷二叉樹的左子樹，先序遍歷二叉樹的右子樹題目26中序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹的左子樹；訪問而叉樹的根結(jié)點(diǎn)，中序遍歷二叉樹的右子樹題目27后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，后序遍歷二叉樹的左子樹；后序遍歷二叉樹的右子樹，訪問而叉樹的根結(jié)點(diǎn)題目28將樹中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)題目29樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和題目30哈夫曼樹又稱為最優(yōu)二叉樹，它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最小的二叉樹題目31若以4,5,6,7,8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是69題目32具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2m-1結(jié)點(diǎn)。題目33圖的遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法對圖中所有頂點(diǎn)各做一次訪問的過程。題目34圖的深度優(yōu)先搜索遍歷類似于樹的先序遍歷。題目35圖的廣度優(yōu)先搜索類似于樹的按層次遍歷。題目36圖常用的兩種存儲(chǔ)結(jié)構(gòu)是和鄰接矩陣、鄰接表三、綜合題（每小題8分，共40分）題目37寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答:二叉樹的定義是遞歸的，所以，一顆二叉樹可看做由根結(jié)點(diǎn)，左子樹和右子樹這三個(gè)基本部分組成，即依次遍歷整個(gè)二叉樹，右子樹或者左子樹又可看做一顆二叉樹并繼續(xù)分為根結(jié)點(diǎn)、左子樹和右子樹三部分……，這樣劃分一直進(jìn)行到樹葉結(jié)點(diǎn)。（1）先序?yàn)椤案笥?，先序序列為：fdbacegihl（2）先序?yàn)椤白蟾摇保刃蛐蛄袨椋篴bcdefghij（3）先序?yàn)椤白笥腋?，先序序列為：acbedhjigf題目38已知某二叉樹的先序遍歷結(jié)果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn)和J，它的中序遍歷結(jié)果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請畫出這棵二叉樹，并寫出該二叉樹后續(xù)遍歷的結(jié)果。該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K、M、I、E、J、F、C、A題目39假設(shè)通信用的報(bào)文由9個(gè)字母A、B、C、D、E、F、G、H和I組成，它們出現(xiàn)的頻率分別是:10、20、5、15、8、2、3、7和30。請請用這9個(gè)字母出現(xiàn)的頻率作為權(quán)值求：（1）設(shè)計(jì)一棵哈夫曼樹；（2）計(jì)算其帶權(quán)路徑長度WPL；（3）寫出每個(gè)字符的哈夫曼編碼。（2）帶權(quán)路徑長度WPL值為270（3）每個(gè)字符的哈夫曼編碼為:A：100,B：11,C：1010,D：000,E：0010,F：10110,G：10111,H：0011,I：01題目40請根據(jù)以下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列；（2）給出G的一個(gè)拓?fù)湫蛄校唬?）給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最短路徑。（1）深度優(yōu)先遍歷:v1,v2,v3,v8,v5,v7,v4,v6廣度優(yōu)先遍歷：v1,v2,v4,v6,v3,v5V7,v8（2）G的拓?fù)湫蛄衛(wèi)j為：V1,V2,V4,V6,V5,B5,V3,V5,V7,V8（3）其最短路徑為：V1,V2,V5,V7,V8題目41已知無向圖G描述如下：G=（V,E）V={V1,V2,V3,V4,V5}E={（V1,V2）,（V1,V4）,（V2,V4）,（V3,V4）,（V2,V5）,（V3,V4）,（V3,V5）}（1）畫出G的圖示；（2）然后給出G的鄰接矩陣和鄰接表；（3）寫出每個(gè)頂點(diǎn)的度。GG的鄰接矩陣G的鄰接表(3)VI、V2、V3、V4、V5的度分別為：2、3、2、3、2四、程序填空題(每空2分，共8分)題目42滿分4.00以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidInorder(structBTreeNode*BT)(if(BT!=NULL){Inorder(BT->left);printf("%c",BT->data);Inorder(BT->right);}題目43滿分4.00以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序