南郵通達(dá)數(shù)據(jù)結(jié)構(gòu)B期末試卷及答案

《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（A)第2頁(yè)共5頁(yè)《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（A)本試卷共 4 頁(yè)；考試時(shí)間 110 分鐘;自覺(jué)遵守考裝訂試線規(guī)則誠(chéng)信考試，絕不作內(nèi)不要答題自覺(jué)遵守考裝訂試線規(guī)則誠(chéng)信考試，絕不作內(nèi)不要答題弊數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)＿＿＿_(dá)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及在數(shù)據(jù)上執(zhí)行的算。設(shè)順序表長(zhǎng)度為10０,若下標(biāo)從0開始計(jì)，則刪除元素a 需要移＿個(gè)元１０素．一棵二叉樹中，若葉結(jié)點(diǎn)的個(gè)數(shù)為則度為2的結(jié)點(diǎn)個(gè)數(shù)為.有向圖進(jìn)行拓?fù)渑判驔](méi)有輸出圖中所有頂點(diǎn)，說(shuō)明圖中存_＿ 。線性表采用二分搜索必須滿足兩個(gè)條件線性表關(guān)鍵字必須＿ 存儲(chǔ)結(jié)必須采用順序存儲(chǔ)結(jié)構(gòu)。二叉搜索樹序遍歷序列是一個(gè)按關(guān)鍵字遞增排列的有序序列。7. 設(shè)有一組記錄的關(guān)鍵字為｛1９，14，1，69，２0，２7，５５,79},散函數(shù)為h(ｋey）＝散列函數(shù)值為3的_＿＿＿ 個(gè)?？焖倥判蛩惴ㄆ骄闆r下的漸近時(shí)間復(fù)雜度為O（ ＿_(dá))。采用二次探查法解決沖突可能產(chǎn)生聚集。圖常見的兩種存儲(chǔ)結(jié)構(gòu)有鄰接矩陣＿＿ .二、選擇題(20分，共1０題)一個(gè)算法必須在執(zhí)行有窮步之后結(jié).這是算法＿＿＿＿。A。有窮性?Ｂ。正確性???Ｃ。確定性?D.可行性在指針p所指示的結(jié)點(diǎn)之后插入新結(jié)點(diǎn)s的操作＿_(dá)。s—>link=ｐ；p-〉ｌink=s; ? ? B。ｓ—＞ｌink＝p—lｉｎk;p—ｋ=s；C?！祃ink=p—〉ｌink；ｐ=s;?? ? D.p-〉link＝s；s-〉liｎk=p；棧和隊(duì)列的共同點(diǎn)_＿ ＿。都是先進(jìn)后??? ??B．都是先進(jìn)先出Ｃ. 只允許在端點(diǎn)處插入和刪除元? D.沒(méi)有共同點(diǎn)4. 后綴表達(dá)式：５32＊3＋３/的值＿_(dá)＿。A.1８ ??B. 7 ?? Ｃ。9 ??Ｄ.8?5_＿_(dá)＿＿＿_(dá)個(gè)結(jié)點(diǎn)．A。5 ? B。10? ?C。D．3２采用對(duì)半查找方法查找長(zhǎng)度為n的線性表時(shí)，時(shí)間復(fù)雜度_＿ A。Ｏ(n2) ?B。Ｏ(ｎｌog2n)??C.O（n）??D。Ｏ（lｏg2n)n＿＿。A。n ?B。（n-??Ｃ．n2???Ｄ。ｎ–1一個(gè)無(wú)向連通圖的生成樹是一連通子圖。A。極?? B.極???C。有時(shí)極?D.有時(shí)候極小,排序過(guò)程中的比較次數(shù)與排序方法無(wú)關(guān)的是＿＿。A。簡(jiǎn)單選擇排序法? ?B。直接插入排序法C.快速排序法????D。冒泡排序法，散列函數(shù)為h(key）=keｙ％。采用線性探查法解決沖突，依次將關(guān)鍵字7，38,5，1616。A.5? Ｂ。6????C.7? D。8三、簡(jiǎn)答題(30分，共5題)1.圖１ 圖２2所有可能的拓?fù)渑判颍?所示，請(qǐng)給出每個(gè)頂點(diǎn)的入度。圖3空二叉搜索樹中依次插入5．設(shè)W｛，，，，，（1）畫出由權(quán)值集合Ｗ構(gòu)造的哈夫曼樹.（２）計(jì)算加權(quán)路徑長(zhǎng)度。四、判斷題(10分5題)簡(jiǎn)單選擇排序是穩(wěn)定的排序算法。,沖突概率小。1..五、程序填空題（10分,共1題)１。以下程序是對(duì)半搜索的迭代實(shí)現(xiàn)，請(qǐng)?zhí)顚懲暾?。BOＯLKeｙTypeT *x）｛intｌｏw=(1）_＿ ＿，ｈigh = ｌst．Sｉze－1；while （(2) ＿ ）｛?mid＝（ｌoｗ+high)/2;? if(ｋ<lst。Elemeｎｔｓ［ｍid］.Ｋey）higｈ＝(3） ＿ ；??ｅlsｅif（(4） ＿＿ ＿ ＿）low= ｍｉd+1;? eｌse ｛? ? ＊x=lst。Ｅｌemｅntｓ［mid]; ｒeｔｕrn TRUE；? ｝}（５) ＿ ＿}六、編程題（10分,共1題）1CoｕｎtCｏｕnt1函數(shù)。tyｐedefintK;ｔypeｄefstｒucｔbtnode｛?K Element;stｒｕｃｔbｔnoｄe＊LＣhilｄ, ＊RChｉld；｝BTNode；tｙpedefstrｕct btreｅ｛?struｃtbtnodｅ＊Ｒoot;}ＢTｒｅｅ;自覺(jué)《 數(shù)據(jù)結(jié)構(gòu)B》期末試卷(Ａ)答案 裝覺(jué)一、填空題（20分，共10題) 遵訂守考試線規(guī)則誠(chéng)信不考要試，絕答不作題弊1 ２ 3 ４ ５ ６ ７ ８ ９ 10《數(shù)據(jù)結(jié)構(gòu)B》期末試卷(Ａ)答案第3頁(yè)共5頁(yè)《B《B》期末試卷(Ａ)答案第5頁(yè)共5頁(yè)邏輯邏輯892０1０有向回路有序中2nｌ二次鄰接表二、選擇題(20分,共10題)12３４5６７8910ABＣDCDCBAD三、簡(jiǎn)答題(30分，共５題）1．前序遍歷序列（3分）中序遍歷序列：ABCDE（3分）2．每個(gè)1分，全對(duì)再加2分ＢACDE BＡCEDBCADＥ3．每個(gè)1分頂點(diǎn)入度0312２131４25１4.5．(４分)WＰL＝(5+6)＊3 + =3３+48=81(2分）12345×12345××××√五、程序填空題（１０分，每空2分）(1) 0loｗ=hｉgｈmiｄ－1k＞ｌstElemenｔs［mid］.Kｅｙreturn六、編程題（10分，共1題）１．ｉｎtuｔ(