2021年數(shù)據(jù)結(jié)構(gòu)本形成性考核作業(yè)

數(shù)據(jù)構(gòu)造（本）課程作業(yè)作業(yè)3（本某些作業(yè)覆蓋教材第6-7章內(nèi)容）一、單項(xiàng)選取題1.假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（）。A．15B．16C2．二叉樹(shù)第k層上最多有（）個(gè)結(jié)點(diǎn)。A．2kB．2k-1C．2k-1D．2k-13．二叉樹(shù)深度為k，則二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。A．2kB．2k-1C．2k-1D．2k-14.設(shè)某一二叉樹(shù)先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹(shù)后序遍歷順序是（）。A．a(chǎn)bdecB．debacC．debcaD．a(chǎn)bedc5．將具有150個(gè)結(jié)點(diǎn)完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為69結(jié)點(diǎn)雙親結(jié)點(diǎn)編號(hào)為（）。A．33B．34C．35D．366．如果將給定一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出二叉樹(shù)帶權(quán)途徑長(zhǎng)度最小，則該樹(shù)稱(chēng)為（）。A．哈夫曼樹(shù)B．平衡二叉樹(shù)C．二叉樹(shù)D．完全二叉樹(shù)7．下列關(guān)于二叉樹(shù)說(shuō)法對(duì)的是（）。A．二叉樹(shù)中度為0結(jié)點(diǎn)個(gè)數(shù)等于度為2結(jié)點(diǎn)個(gè)數(shù)加1B．二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必不不大于0C．完全二叉樹(shù)中，任何一種結(jié)點(diǎn)度，或者為0或者為2D．二叉樹(shù)度是28．在一棵度為3樹(shù)中，度為3結(jié)點(diǎn)個(gè)數(shù)為2，度為2結(jié)點(diǎn)個(gè)數(shù)為1，則度為0結(jié)點(diǎn)個(gè)數(shù)為（）。A．4B．5C．6D．79．在一棵度具備5層滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（）。A．31B．32C．33D．1610.運(yùn)用n個(gè)值作為葉結(jié)點(diǎn)權(quán)生成哈夫曼樹(shù)中共包具有()個(gè)結(jié)點(diǎn)。A.nB.n+1C.2*nD.2*n-111.運(yùn)用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子最長(zhǎng)帶權(quán)途徑長(zhǎng)度為()。A.18B.16C.12D.312．在一棵樹(shù)中，（）沒(méi)有前驅(qū)結(jié)點(diǎn)。A．分支結(jié)點(diǎn)B．葉結(jié)點(diǎn)C．樹(shù)根結(jié)點(diǎn)D．空結(jié)點(diǎn)13．在一棵二叉樹(shù)中，若編號(hào)為i結(jié)點(diǎn)存在右孩子，則右孩子順序編號(hào)為（）。A．2iB．2i-1D．2i+114．設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（）個(gè)非葉結(jié)點(diǎn)。A．nB．n-1C15．設(shè)一棵有n個(gè)葉結(jié)點(diǎn)二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有（）個(gè)結(jié)點(diǎn)。A．2nB．2n-1C．2n+1D．2n+216．在一種圖G中，所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)之和（）倍。A．1/2B．1C．2D．417．在一種有向圖中，所有頂點(diǎn)入度之和等于所有頂點(diǎn)出度之和（）倍。A．1/2B．2C．1D．18．一種具備n個(gè)頂點(diǎn)無(wú)向完全圖包括（）條邊。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/219．一種具備n個(gè)頂點(diǎn)有向完全圖包括（）條邊。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/220．對(duì)于具備n個(gè)頂點(diǎn)圖，若采用鄰接矩陣表達(dá)，則該矩陣大小為（）。A．nB．n2C．n1D．（n1）21．對(duì)于一種具備n個(gè)頂點(diǎn)和e條邊無(wú)向圖，若采用鄰接表表達(dá)，則所有頂點(diǎn)鄰接表中結(jié)點(diǎn)總數(shù)為（）。A．nB．eC．2nD．2e22．在有向圖鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。A．入邊B．出邊C．入邊和出邊D．不是入邊也不是出邊23．鄰接表是圖一種（）。A．順序存儲(chǔ)構(gòu)造B．鏈?zhǔn)酱鎯?chǔ)構(gòu)造C．索引存儲(chǔ)構(gòu)造D．散列存儲(chǔ)構(gòu)造24．如果從無(wú)向圖任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪(fǎng)問(wèn)所有頂點(diǎn)，則該圖一定是（）。A．完全圖B．連通圖C．有回路D．一棵樹(shù)25．下列關(guān)于圖遍歷說(shuō)法不對(duì)的是（）。A．連通圖深度優(yōu)先搜索是一種遞歸過(guò)程B．圖廣度優(yōu)先搜索中鄰接點(diǎn)尋找具備“先進(jìn)先出”特性C．非連通圖不能用深度優(yōu)先搜索法D．圖遍歷規(guī)定每一頂點(diǎn)僅被訪(fǎng)問(wèn)一次26．無(wú)向圖鄰接矩陣是一種（）。 A．對(duì)稱(chēng)矩陣B．零矩陣C．上三角矩陣D．對(duì)角矩陣27．圖深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)（）遍歷。A．先序B．中序C．后序D．層次28．已知下圖所示一種圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到一種頂點(diǎn)序列為（）。A．V1V2V4V8V3V5V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V5V3V6V7D．V1V3V6V7V2V4V5V8V6V6V7V1V2V3V8V4V5二、填空題1．結(jié)點(diǎn)度是指結(jié)點(diǎn)所擁有。2．樹(shù)度是指。3．度不不大于0結(jié)點(diǎn)稱(chēng)作或。4．度等于0結(jié)點(diǎn)稱(chēng)作或。5．在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)或者說(shuō)每個(gè)結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)，簡(jiǎn)稱(chēng)為孩子。6．從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)。7．樹(shù)深度或高度是指。8．具備n個(gè)結(jié)點(diǎn)完全二叉樹(shù)深度是。9．先序遍歷二叉樹(shù)操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，訪(fǎng)問(wèn)二叉樹(shù)；先序遍歷二叉樹(shù)，先序遍歷二叉樹(shù)。10．中序遍歷二叉樹(shù)操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹(shù)；訪(fǎng)問(wèn)而叉樹(shù)，中序遍歷二叉樹(shù)。11．后序遍歷二叉樹(shù)操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，后序遍歷二叉樹(shù)；后序遍歷二叉樹(shù)，訪(fǎng)問(wèn)而叉樹(shù)。12．將樹(shù)中結(jié)點(diǎn)賦上一種有著某種意義實(shí)數(shù)，稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)。13．樹(shù)帶權(quán)途徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)。14．哈夫曼樹(shù)又稱(chēng)為，它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成所有二叉樹(shù)中帶權(quán)途徑長(zhǎng)度WPL。15．若以4，5，6，7，8作為葉子結(jié)點(diǎn)權(quán)值構(gòu)造哈夫曼樹(shù)，則其帶權(quán)途徑長(zhǎng)度是。16．具備m個(gè)葉子結(jié)點(diǎn)哈夫曼樹(shù)共有結(jié)點(diǎn)。17．在圖中，任何兩個(gè)數(shù)據(jù)元素之間都也許存在關(guān)系，因而圖數(shù)據(jù)元素之間是一種關(guān)系。18．圖遍歷是從圖某一頂點(diǎn)出發(fā)，按照一定搜索辦法對(duì)圖中各做訪(fǎng)問(wèn)過(guò)程。19．圖深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)遍歷。20．圖廣度優(yōu)先搜索類(lèi)似于樹(shù)遍歷。21．具備n個(gè)頂點(diǎn)有向圖鄰接矩陣，其元素個(gè)數(shù)為。22．圖慣用兩種存儲(chǔ)構(gòu)造是和。23．在有n個(gè)頂點(diǎn)有向圖中，每個(gè)頂點(diǎn)度最大可達(dá)。24．在一種帶權(quán)圖中，兩頂點(diǎn)之間最段途徑最多通過(guò)條邊。25．為了實(shí)現(xiàn)圖深度優(yōu)先搜索遍歷，其非遞歸算法中需要使用一種輔助數(shù)據(jù)構(gòu)造為。三、綜合題1．寫(xiě)出如下圖所示二叉樹(shù)先序、中序和后序遍歷序列。aajfghidceb2．已知某二叉樹(shù)先序遍歷成果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn)和J，它中序遍歷成果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請(qǐng)畫(huà)出這棵二叉樹(shù)，并寫(xiě)出該二叉樹(shù)后續(xù)遍歷成果。3．已知一棵完全二叉樹(shù)共有892個(gè)結(jié)點(diǎn)，求⑴樹(shù)高度⑵葉子結(jié)點(diǎn)數(shù)⑶單支結(jié)點(diǎn)數(shù)⑷最后一種非終端結(jié)點(diǎn)序號(hào)4．給出滿(mǎn)足下列條件所有二叉樹(shù)。（1）先序和中序相似（2）中序和后序相似（3）先序和后序相似5．假設(shè)通信用報(bào)文由9個(gè)字母A、B、C、D、E、F、G、H和I構(gòu)成，它們浮現(xiàn)頻率分別是：10、20、5、15、8、2、3、7和30。請(qǐng)請(qǐng)用這9個(gè)字母浮現(xiàn)頻率作為權(quán)值求：（1）設(shè)計(jì)一棵哈夫曼樹(shù)；（2）計(jì)算其帶權(quán)途徑長(zhǎng)度WPL；（3）寫(xiě)出每個(gè)字符哈夫曼編碼。6．請(qǐng)依照如下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得結(jié)點(diǎn)序列；（2）給出G一種拓?fù)湫蛄校唬?）給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8最短途徑。7．已知無(wú)向圖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）畫(huà)出G圖示；（2）然后給出G鄰接矩陣和鄰接表；（3）寫(xiě)出每個(gè)頂點(diǎn)度。四、程序填空題1.下面函數(shù)功能是返回二叉樹(shù)BT中值為X結(jié)點(diǎn)所在層號(hào)，請(qǐng)?jiān)趧澯袡M線(xiàn)地方填寫(xiě)適當(dāng)內(nèi)容。intNodeLevel(structBinTreeNode*BT，charX){if(BT==NULL)return0；/*空樹(shù)層號(hào)為0*/elseif(BT->data==X)return1；/*根結(jié)點(diǎn)層號(hào)為1*//*向子樹(shù)中查找X結(jié)點(diǎn)*/else{intc1=NodeLevel(BT->left,X);if(c1>=1)___(1)___________；intc2=______(2)__________；if___(3)__________________；//若樹(shù)中不存在X結(jié)點(diǎn)則返回0elsereturn0;}}2.下面函數(shù)功能是按照?qǐng)D深度優(yōu)先搜索遍歷辦法，輸出得到該圖生成樹(shù)中各條邊，請(qǐng)?jiān)趧澯袡M線(xiàn)地方填寫(xiě)適當(dāng)內(nèi)容。voiddfstree(adjmatrixGA，inti，intn){intj;visited[i]=1；(1)if(GA[i][j]!=0&&GA[i][j]!=MaxValue&&!visited[j]){printf("(%d,%d)%d,",i,j,GA[i][j]);