1數(shù)據結構復習題及答案

中南大學現(xiàn)代遠程教育課程測試（專科）復習題及參考答案

數(shù)據結構、判斷題：．數(shù)組是一種復雜的數(shù)據結構，數(shù)組元素之間的關系既不是線性的也不是樹形的。（）．鏈式存儲在插人和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據元素之間的邏輯順序。（）.在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有nk個，則有n0=nk+1。（）.折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（）.如果兩個串含有相同的字符，則這兩個串相等。（）.數(shù)組可以看成線性結構的一種推廣，因此可以對它進行插入、刪除等運算。（）.在用循環(huán)單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。（）TOC\o"1-5"\h\z.通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。 （）.一個廣義表的表尾總是一個廣義表。 （）.當從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調整，直到調整到合適位置為止。 （）.對于一棵具有n個結點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O（h）。 （）.存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關，而且與圖的邊數(shù)也有關。 （）.直接選擇排序是一種穩(wěn)定的排序方法。 （）.閉散列法通常比開散列法時間效率更高。 （）.有n個結點的不同的二叉樹有n!棵。（）.直接選擇排序是一種不穩(wěn)定的排序方法。（）.在2048個互不相同的關鍵碼中選擇最小的5個關鍵碼，用堆排序比用錦標賽排序更快。（）.當3階B_樹中有255個關鍵碼時，其最大高度（包括失敗結點層）不超過8。（）.一棵3階B_樹是平衡的3路搜索樹，反之，一棵平衡的3路搜索樹是3階非B_樹。（）.在用散列表存儲關鍵碼集合時，可以用雙散列法尋找下一個空桶。在設計再散列函數(shù)時，要求計算出的值與表的大小m互質。（）.在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每一塊中元素個數(shù)有關。（）TOC\o"1-5"\h\z.在順序表中取出第i個元素所花費的時間與i成正比。 （）.在棧滿情況下不能作進棧運算，否則產生“上溢”。 （）.二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。 （）.對任意一個圖，從它的某個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.（）.二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值;若它的右子樹非空，則根結點的值小于其右孩子的值。（）.在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（）.一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定相等。 （）、選擇題：.在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（）。A.O（n） B.O（n／2）C.O（1） D.O（n2）.帶頭結點的單鏈表first為空的判定條件是：（）first==NULLfirst一>1ink==NULLfirst一>link==firstfirst!=NUlL.當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）。A.n-2B.n-lC.nD.n+1

4．在系統(tǒng)實現(xiàn)遞歸調用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的( )，在被調用程序中可直接操縱實際參數(shù)。A.空間B.副本C.返回地址C.返回地址5．在一棵樹中，(A.分支結點C.樹根結點D.地址)沒有前驅結點D.葉結點D.空結點在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加( )。A.2B.1C.0D.-1對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為( )的值除以9。A.20B.18C.25D.22在有向圖中每個頂點的度等于該頂點的( )。A.入度B.出度C.入度與出度之和D.入度與出度之差在基于排序碼比較的排序算法中，()算法的最壞情況下的時間復雜度不高于O(n10g2n)。A.起泡排序 B.希爾排序C.歸并排序 D.快速排序當a的值較小時，散列存儲通常比其他存儲方式具有()的查找速度。A.較慢B.較快C.相同D.不清楚設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5，則散列表項應能夠至少容納( )個表項。(設搜索成功的平均搜索長度為Snl={1+l/(1一a)}/2,其中a為裝填因子)A.400B.526C.624D.676堆是一個鍵值序列{匕,匕,…..kn},對1=1,2,….|_n/2_|,滿足( )AkZk產 0W且www或wwi2ii2i+1 i2ii2i+1若將數(shù)據結構形式定義為二元組(K,R),其中K是數(shù)據元素的有限集合，則R是K上()A.操作的有限集合B.映象的有限集合C.類型的有限集合 D.關系的有限集合在長度為n的順序表中刪除第i個元素(YiWn)時，元素移動的次數(shù)為()A.n-i+1 B.iC.i+1 D.n-i若不帶頭結點的單鏈表的頭指針為head,則該鏈表為空的判定條件是()A.head==NULL B.head->next==NULLC.head!=NULL D.head->next==head引起循環(huán)隊列隊頭位置發(fā)生變化的操作是()A.出隊 B.入隊C.取隊頭元素 D.取隊尾元素若進棧序列為1,2,3,4,5,6,且進棧和出?？梢源┎暹M行,則不可能出現(xiàn)的出棧序列是()A.2,4,3,1,5,6B.3,2,4,1,6,5 C.4,3,2,1,5,6 D.2,3,5,1,6,4字符串通常采用的兩種存儲方式是()A.散列存儲和索引存儲 B.索引存儲和鏈式存儲 C.順序存儲和鏈式存儲 D.散列存儲和順序存儲設主串長為n,模式串長為m(m<n),則在匹配失敗情況下，樸素匹配算法進行的無效位移次數(shù)為()A.m B.n-mC.n-m+1 D.n二維數(shù)組A[12][18]采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150,則元素A[9][7]的地址為()A.429 B.432C.435 D.438對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結果是()A.(e,f) B.((e,f))C.(f) D.()下列圖示的順序存儲結構表示的二叉樹是()n個頂點的強連通圖中至少含有()A.n-1條有向邊 B.n條有向邊C.n(n-1)/2條有向邊D.n(n-1)條有向邊對關鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結果為(A.(19，23，56，34，78，67，88，92)B.23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D.(19，23，67，56，34，78，92，88)若在9階B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數(shù)為()A.4 B.5C.8 D.9由同一關鍵字集合構造的各棵二叉排序樹()其形態(tài)不一定相同，但平均查找長度相同其形態(tài)不一定相同，平均查找長度也不一定相同其形態(tài)均相同，但平均查找長度不一定相同其形態(tài)均相同，平均查找長度也都相同ISAM文件和VSAM文件的區(qū)別之一是()前者是索引順序文件，后者是索引非順序文件前者只能進行順序存取，后者只能進行隨機存取前者建立靜態(tài)索引結構，后者建立動態(tài)索引結構前者的存儲介質是磁盤，后者的存儲介質不是磁盤下列描述中正確的是()線性表的邏輯順序與存儲順序總是一致的每種數(shù)據結構都具備三個基本運算：插入、刪除和查找數(shù)據結構實質上包括邏輯結構和存儲結構兩方面的內容選擇合適的數(shù)據結構是解決應用問題的關鍵步驟下面程序段的時間復雜度是()i=s=0while(s<n){i++;s+=i;}A.O(1)B.O(n)C.O(log2n)D.O(n2)對于順序表來說，訪問任一節(jié)點的時間復雜度是()A.O(1)B.O(n)C.O(log2n)D.O(n2)在具有n個節(jié)點的雙鏈表中做插入、刪除運算，平均時間復雜度為()A.O(1)B.O(n)C.O(log2n)D.O(n2)經過下列運算后，QueueFront(Q)的值是()InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x);A.aB.bC.1 D.2一個棧的入棧序列是a,b,c,則棧的不可能輸出序列是()

A.acbB.abcC.bcaD.cab循環(huán)隊列是空隊列的條件是（）A．Q->rear==Q->frontB.（Q->rear+1）%maxsize==Q->frontC.Q->rear==0 D.Q->front==0設s3="IAM",s4="ATERCHER".貝Ustrcmp（s3,s4）=（）A.0B.小于0C.大于0D.不確定一維數(shù)組的元素起始地址loc[6]=1000,元素長度為4,則loc[8]為（）A.1000B.1004C.1008D.8廣義表（（a,b）,c,d）的表尾是（）A.aB.bC.（a,b）D.（c,d）對于二叉樹來說，第I層上至多有一個節(jié)點（）A.2iB.2i-1C.2i-1D.2i-1-1某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF,則后序遍歷序列為（）A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCAM叉樹中，度為0的節(jié)點數(shù)稱為（）A.根B.葉C.祖先D.子孫已知一個圖如下所示，若從頂點a出發(fā)按寬度搜索法進行遍歷，則可能得到的一種頂點序列為（）A.4工1了,4，B,D,a,ctfj,e,b堆的形狀是一棵（）A.二叉排序樹B.滿二叉樹C.完全二義樹D.平衡二叉樹排序方法中,從未排序序列中挑選元素,并將其依次放入已排序序列（初始時為空）的一端的方法,稱為（）A.希爾排序B.歸并排序C插入排序D.選擇排序采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）A.nB.n/2C.（n+1）/2D.（n-1）/2散列查找是由鍵值 確定散列表中的位置,進行存儲或查找（）A.散列函數(shù)值B.本身C.平方D.相反數(shù)順序文件的缺點是（）A.不利于修改B.讀取速度慢C.只能寫不能讀D.寫文件慢索引文件的檢索方式是直接存取或按 存?。ǎ〢.隨機存取B.關鍵字C.間接D.散列堆是一個鍵值序列{k1,k2,.....kn},對i=1,2,….|_n/2_|,滿足（ ）A.…石k#.上―W且www或wwi2ii2i+1 i2ii2i+1計算與算法應用題（本大題每小題9分）.給定表（119,14,22,1,66,21,83,27,56,13,10）請按表中元素的順序構造一棵平衡二叉樹,并求其在等概率情況下查找成功的平均長度。（9分）.已知一個有向圖的頂點集和邊集分別為：假定該圖采用鄰接矩陣表示,則分別寫出從頂點（9假定該圖采用鄰接矩陣表示,則分別寫出從頂點（9分）3.設散列表的長度為，散列函數(shù)為（）,%給1定3的關鍵碼序列為1,914,23,0,168,20,84,27。試畫出用線性探查法解決沖突時所構成的散列表。（8分）個關鍵字進行快速排序，在最好的情況下僅需進行,3,4，,試5個關鍵字進行快速排序，在最好的情況下僅需進行,3,4，,試5舉,出6能,達7到｝上述結果的初始關鍵字序列；次關鍵字的比較。假）設關鍵字集合為對所舉序列進行快速排序，寫出排序過程。（9分）（1）式中序遍的序列R?前序遍出.序列1,4,6,時9每,一8插,入1,4,6,時9每,一8插,入5后,樹中刪去根結點后的結果。樹的形態(tài)。若做了某種旋轉，說明旋.畫出在一個初始為空的樹中依次插入轉的類型。然后，給出在這棵插入后得到的.已知一組記錄的排序碼為（46，7，956，38，4，080,9，52）4，寫出對其進行快速排序的每一次劃分結果。.一個線性表為B（=1，223，4，557，20，03，7，831，15，3）6，設散列表為HT[0.，散列函數(shù)為 （ ） 并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。已知一棵二叉樹的前序遍歷的結果序列是 ，中序遍歷的結果是 ，試寫出這棵二叉樹的后序遍歷結果。假定對線性表，，，，，，進行散列存儲，采用 ％作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應的平均查找長度分別為和。1．假定一組記錄的排序碼為（4，679，56，38，4，08，025，34，57，21，）則對其進行快速排序的第一次劃分后又對左、右兩個子區(qū)間分別進行一次劃分，得到的結果為：。下圖是帶權的有向圖的鄰接表表示法。從結點出發(fā)，深度遍歷圖所得結點序列為（），廣度遍歷圖所得結點序列為（）；的一個拓撲序列是（）；從結點到結點的最短路徑為（）；從結點到結點的關鍵路徑為（）。其中、、的選擇有：D的選擇有:TOC\o"1-5"\h\z① VV1V1V1

.畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。.已知如圖所示的有向網，試利用

Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。15.假定用于通信的電文由8個字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試為這8個字母設計不等長Huffman編碼，并給出該電文的總碼數(shù)。已知一棵二叉樹的中序和前序序列如下,試畫出該二叉樹并求該二叉樹的后序序列。(9分)中序序列：，，，，a,,,,,前序序列：a,bcdefghi假設用于通信的電文僅由8個字母組成,字母在電文中出現(xiàn)的頻率分別為0.,007.1,90.0,02.0,06.,302.0,21 1試為這個字母設計哈夫曼編碼。使用?的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。四、算法設計題1已知深度為的二叉樹以一維數(shù)組 11作為其存儲結構。請寫一算法，求該二叉樹中葉結點的個數(shù)。2.編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找item帶回整個結點的值并返回ture,否則返回false。bool(FBitndree編寫算法，將一個結點類型為n 的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1,……an1,an,則逆序鏈接后變?yōu)?an,an-1,……a1。根據下面函數(shù)原型，編寫一個遞歸算法，統(tǒng)計并返回以 為樹根指針的二叉樹中所有葉子結點的個數(shù)。intCount(BTre；eNode*BT).設A=(a1,...,am)和B=(b1,...,bn)均為順序表，4和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B'W空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個比較A,B大小的算法。.已知單鏈表a和b的元素按值遞增有序排列，編寫算法歸并a和b得到新的單鏈表c,c的元素按值遞減有序。

.編寫遞歸算法，對于二叉樹中每一個元素值為的結點，刪去以它為根的子樹，并釋放相應的空間。編寫算法判別是否為二叉排序樹算法中涉及試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點V.的路徑（i<>j）。注意:的圖的基本操作必須在存儲結構上實現(xiàn)。算法中涉及參考答案一、判斷題V .XXV 3V19.X 20.X27X. 2V8二、單項選擇題V .XXV 3V19.X 20.X27X. 2V8二、單項選擇題.A2.B3.B4..13.B14.D15.5.C26.B27C28.D29.B30.A31.AC三計算與算法應用題.［解答］V3.X4 .V56.V15X16V 17X18X1V.22X. 2V3.D5.C6.A7.C8.AA16.A17.D18.32.B33.D34.A35.C36.C37.D.7X.X8V4.25X.C9.C 10.BC19.C20.A38.C39.D40.A.X91.0X6X.12B22.A23.B43.D44.C45.A21.41.B42.CC24.D246.A47.B平均長度為4.2、解：畫圖（略）深度優(yōu)先搜索序列：a，廣度優(yōu)先搜索序列：a，3、解：計算機關鍵碼得到的散列地址關鍵碼1914230168208427散列地址611013761在散列表中散列結果0 1 2 3 4 5 6 7 8 9 10 11 121401682719208423對n個關鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關鍵字比較。這里要求10次，

而7-1+2*（3-1）=10,這就要求2趟快速排序后，算法結束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分（1）4132657或4137652或4537612或4135627 按（自2己）序列完成搜（索2成）功的平均搜索長度為l／12*（1+2+l+l+l+：l3+／l21+5.答案：（l）djbaechif（2）abdjcefhi（3）jdbeihfca6.在這個 樹中刪除根結點時有兩種方案【方案1】在根的左子樹中沿右鏈走到底,用5遞補根結點中原來的6,再刪除5所在的結點【方案2】在根的右子樹中沿左鏈走到底,用7遞補根結點中原來的6,再刪除7所在的結點劃分次序劃分結果第一次第二次第三次第四次第五次第六次查找成功的平均查找長度：AS9、此二叉樹的后序遍歷結果是：10.1／371／l712.（A）深度遍歷：1,2,廣度遍歷：12.（A）深度遍歷：1,2,廣度遍歷：拓撲序列：最短路徑：關鍵路徑：3,8,4,5,7,6或1,2,1,2,4,6,3,5,7,81,2,4,6,5,3,7,81,2,5,7,81,6,5,3,83,8,5,7,4,13.ASLsucc=(1+2X2+3X4+4X3)/10=2.9源點終點最短路徑路徑長度121,3,21931,31541,3,2,421,3,21931,31541,3,2,42951,3,52961,3,2,4,644則ab電文總碼數(shù)4*5+2*2*6+3*10*36+4*4=次數(shù){5,25,編碼為(5分)01001000000101001011110001為(2分)5+4*3+4+3*11+2圖(2分)樹(略)后序序列：方案1;哈夫曼編碼100c,e,d,°b,i,j,，h，g,39,1f,a(5+4分)、61先將概率放大100倍，以0先將概率放大100倍，以廬便構造1夫曼樹。0/w={7,19,2,6,32,3,21,10},按哈夫曼規(guī)則：[[(2,3),6],(7,119,21,321"(10017(「22 25方案比較3方案1的WPL106'入、0，\123=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.|02+0.03)=1.44+0.92+0.25=2.61方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結論：哈夫曼編碼優(yōu)于等長二進制編碼四、算法設計題：二叉樹采取順序結構存儲,是按完全二叉樹格式存儲的。對非完全二叉樹要補上“虛結點”。因為不是完全二叉樹,在順序結構存儲中對葉子結點的判定是根據其左右子女為0。葉子和雙親結點下標間的關系滿足完全二叉樹的性質。求深度為以順序結構存儲的二叉樹的葉子結點數(shù)是二