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

《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（A)第2頁共5頁《數(shù)據(jù)結(jié)構(gòu)Ｂ》期末試卷（A)本試卷共 4 頁；考試時間 110 分鐘;自覺遵守考裝訂試線規(guī)則誠信考試，絕不作內(nèi)不要答題自覺遵守考裝訂試線規(guī)則誠信考試，絕不作內(nèi)不要答題弊數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)＿＿＿_結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)以及在數(shù)據(jù)上執(zhí)行的算。設順序表長度為10０,若下標從0開始計，則刪除元素a 需要移＿個元１０素．一棵二叉樹中，若葉結(jié)點的個數(shù)為則度為2的結(jié)點個數(shù)為.有向圖進行拓撲排序沒有輸出圖中所有頂點，說明圖中存_＿ 。線性表采用二分搜索必須滿足兩個條件線性表關鍵字必須＿ 存儲結(jié)必須采用順序存儲結(jié)構(gòu)。二叉搜索樹序遍歷序列是一個按關鍵字遞增排列的有序序列。7. 設有一組記錄的關鍵字為｛1９，14，1，69，２0，２7，５５,79},散函數(shù)為h(ｋey）＝散列函數(shù)值為3的_＿＿＿ 個?？焖倥判蛩惴ㄆ骄闆r下的漸近時間復雜度為O（ ＿_)。采用二次探查法解決沖突可能產(chǎn)生聚集。圖常見的兩種存儲結(jié)構(gòu)有鄰接矩陣＿＿ .二、選擇題(20分，共1０題)一個算法必須在執(zhí)行有窮步之后結(jié).這是算法＿＿＿＿。A。有窮性?Ｂ。正確性???Ｃ。確定性?D.可行性在指針p所指示的結(jié)點之后插入新結(jié)點s的操作＿_。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；棧和隊列的共同點_＿ ＿。都是先進后??? ??B．都是先進先出Ｃ. 只允許在端點處插入和刪除元? D.沒有共同點4. 后綴表達式：５32＊3＋３/的值＿_＿。A.1８ ??B. 7 ?? Ｃ。9 ??Ｄ.8?5_＿_＿＿＿_個結(jié)點．A。5 ? B。10? ?C。D．3２采用對半查找方法查找長度為n的線性表時，時間復雜度_＿ A。Ｏ(n2) ?B。Ｏ(ｎｌog2n)??C.O（n）??D。Ｏ（lｏg2n)n＿＿。A。n ?B。（n-??Ｃ．n2???Ｄ。ｎ–1一個無向連通圖的生成樹是一連通子圖。A。極?? B.極???C。有時極?D.有時候極小,排序過程中的比較次數(shù)與排序方法無關的是＿＿。A。簡單選擇排序法? ?B。直接插入排序法C.快速排序法????D。冒泡排序法，散列函數(shù)為h(key）=keｙ％。采用線性探查法解決沖突，依次將關鍵字7，38,5，1616。A.5? Ｂ。6????C.7? D。8三、簡答題(30分，共5題)1.圖１ 圖２2所有可能的拓撲排序．3所示，請給出每個頂點的入度。圖3空二叉搜索樹中依次插入5．設W｛，，，，，（1）畫出由權(quán)值集合Ｗ構(gòu)造的哈夫曼樹.（２）計算加權(quán)路徑長度。四、判斷題(10分5題)簡單選擇排序是穩(wěn)定的排序算法。,沖突概率小。1..五、程序填空題（10分,共1題)１。以下程序是對半搜索的迭代實現(xiàn)，請?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ｒｅｅ;自覺《 數(shù)據(jù)結(jié)構(gòu)B》期末試卷(Ａ)答案 裝覺一、填空題（20分，共10題) 遵訂守考試線規(guī)則誠信不考要試，絕答不作題弊1 ２ 3 ４ ５ ６ ７ ８ ９ 10《數(shù)據(jù)結(jié)構(gòu)B》期末試卷(Ａ)答案第3頁共5頁《B《B》期末試卷(Ａ)答案第5頁共5頁邏輯邏輯892０1０有向回路有序中2nｌ二次鄰接表二、選擇題(20分,共10題)12３４5６７8910ABＣDCDCBAD三、簡答題(30分，共５題）1．前序遍歷序列（3分）中序遍歷序列：ABCDE（3分）2．每個1分，全對再加2分ＢACDE BＡCEDBCADＥ3．每個1分頂點入度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ｔ(