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

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