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

數(shù)據(jù)結構復習題及答案數(shù)據(jù)結構復習題及答案數(shù)據(jù)結構復習題及答案數(shù)據(jù)結構復習題及答案編制僅供參考審核批準生效日期地址：電話：傳真:郵編:中南大學現(xiàn)代遠程教育課程考試（考試）復習題及參考答案數(shù)據(jù)結構(使用教材：余臘生編著，人民郵電出版社出版，《數(shù)據(jù)結構—基于C++模板類的實現(xiàn)》一、判斷題數(shù)組是一種復雜的數(shù)據(jù)結構，數(shù)組元素之間的關系既不是線性的也不是樹形的。[]鏈式存儲在插人和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序。[]在用循環(huán)單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。[]通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。[]一個廣義表的表尾總是一個廣義表。[]當從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。[]對于一棵具有n個結點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O（h）。[]存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關，而且與圖的邊數(shù)也有關。[]直接選擇排序是一種穩(wěn)定的排序方法。[]30、閉散列法通常比開散列法時間效率更高。[]有n個結點的不同的二叉樹有n!棵。[]直接選擇排序是一種不穩(wěn)定的排序方法。[]在2048個互不相同的關鍵碼中選擇最小的5個關鍵碼，用堆排序比用錦標賽排序更快。[]當3階B_樹中有255個關鍵碼時,其最大高度(包括失敗結點層)不超過8。[]一棵3階B_樹是平衡的3路搜索樹,反之,一棵平衡的3路搜索樹是3階非B_樹。[]在用散列表存儲關鍵碼集合時，可以用雙散列法尋找下一個空桶。在設計再散列函數(shù)時，要求計算出的值與表的大小m互質(zhì)。[]在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有nk個，則有n0=nk+1。[]折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。[]如果兩個串含有相同的字符，則這兩個串相等。[]數(shù)組可以看成線性結構的一種推廣，因此可以對它進行插入、刪除等運算。[]在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每一塊中元素個數(shù)有關。[]在順序表中取出第i個元素所花費的時間與i成正比。[]在棧滿情況下不能作進棧運算，否則產(chǎn)生“上溢”。[]二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。[]對任意一個圖，從它的某個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.[]二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值;若它的右子樹非空，則根結點的值小于其右孩子的值。[]在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。[]一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定相等。[]二、選擇題在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為[]A.O(n)B.O(n／2)C.O(1)D.O(n2)帶頭結點的單鏈表first為空的判定條件是：[]A.first==NULLB.first一>1ink＝＝NULLC.first一>link==firstD.first!＝NUlL當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為[]A.n-2B.n-lC.nD.n+1在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的（），在被調(diào)用程序中可直接操縱實際參數(shù)。[]A.空間B.副本C.返回地址D.地址在一棵樹中，[]沒有前驅(qū)結點。A.分支結點D.葉結點C.樹根結點D.空結點在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加[]。A.2B.1C.0D.-1對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為[]的值除以9。A.20B.18C.25D.22在有向圖中每個頂點的度等于該頂點的[]。A.入度B.出度C.入度與出度之和D.入度與出度之差在基于排序碼比較的排序算法中，[]算法的最壞情況下的時間復雜度不高于O(n1og2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序當α的值較小時，散列存儲通常比其他存儲方式具有[]的查找速度。A.較慢B.較快C.相同D.不清楚設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(shù)不超過，則散列表項應能夠至少容納[]個表項。(設搜索成功的平均搜索長度為ASL＝{1+l／(1一α)}／2，其中α為裝填因子)A.400B.526C.624D.676堆是一個鍵值序列{k1,k2,…..kn},對I=1,2,….|_n/2_|,滿足[]A.ki≤k2i≤k2i+1B.ki<k2i+1<k2iC.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i或ki≤k2i+1(2i+1≤n)若將數(shù)據(jù)結構形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上[]A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關系的有限集合在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為[]

A.n-i+1B.i

C.i+1D.n-i

15.若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是[]

A.head==NULLB.head->next==NULL

C.head!=NULLD.head->next==head

16.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是[]

A.出隊B.入隊

C.取隊頭元素D.取隊尾元素

17.若進棧序列為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，6D.2，3，5，1，6，4

18.字符串通常采用的兩種存儲方式是[]A.散列存儲和索引存儲B.索引存儲和鏈式存儲C.順序存儲和鏈式存儲D.散列存儲和順序存儲19.設主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進行的無效位移次數(shù)為[]

A.mB.n-m

C.n-m+1D.n20.二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為[]

A.429B.432

C.435D.43821.對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結果是[]

A.(e,f)B.((e,f))

C.(f)D.()22.下列圖示的順序存儲結構表示的二叉樹是[]個頂點的強連通圖中至少含有[]

A.n-1條有向邊B.n條有向邊

C.n(n-1)/2條有向邊D.n(n-1)條有向邊

24.對關鍵字序列(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)

25.若在9階B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數(shù)為[]

A.4B.5

C.8D.9

26.由同一關鍵字集合構造的各棵二叉排序樹[]

A.其形態(tài)不一定相同，但平均查找長度相同

B.其形態(tài)不一定相同，平均查找長度也不一定相同

C.其形態(tài)均相同，但平均查找長度不一定相同

D.其形態(tài)均相同，平均查找長度也都相同

27.ISAM文件和VSAM文件的區(qū)別之一是[]

A.前者是索引順序文件，后者是索引非順序文件

B.前者只能進行順序存取，后者只能進行隨機存取

C.前者建立靜態(tài)索引結構，后者建立動態(tài)索引結構

D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤

28.下列描述中正確的是[]

A．線性表的邏輯順序與存儲順序總是一致的

B．每種數(shù)據(jù)結構都具備三個基本運算：插入、刪除和查找

C．數(shù)據(jù)結構實質(zhì)上包括邏輯結構和存儲結構兩方面的內(nèi)容

D．選擇合適的數(shù)據(jù)結構是解決應用問題的關鍵步驟

29.下面程序段的時間復雜度是[]

I=s=0

While(s<n)

{I++;

s+=I;

}

A．O(1)(n)(log2n)(n^2)

30.對于順序表來說，訪問任一節(jié)點的時間復雜度是[]

A．O(1)(n)(log2n)(n^2)

31.在具有n個節(jié)點的雙鏈表中做插入、刪除運算，平均時間復雜度為[]

A．O(1)(n)(log2n)(n^2)

32.經(jīng)過下列運算后，QueueFront(Q)的值是[]

InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x);

33.一個棧的入棧序列是a,b,c，則棧的不可能輸出序列是[]

A.acb

34.循環(huán)隊列是空隊列的條件是[]

A．Q->rear==Q->frontB.(Q->rear+1)%maxsize==Q->front

>rear==0>front==0

35.設s3="IAM",s4="ATERCHER".則strcmp(s3,s4)=[]

B.小于0C.大于0D.不確定

36.一維數(shù)組的元素起始地址loc[6]=1000，元素長度為4，則loc[8]為[]

A．1000.1004C

37.廣義表（（a,b）,c,d）的表尾是[]

A．a(chǎn)C.(a,b)D.(c,d)

38．對于二叉樹來說，第I層上至多有____個節(jié)點[]

A．2iB.2i-1

39.某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為[]

A．BDGCEFHA

叉樹中，度為0的節(jié)點數(shù)稱為[]

A．根B.葉C.祖先D.子孫

41.已知一個圖如下所示，若從頂點a出發(fā)按寬度搜索法進行遍歷，則可能得到的一種頂點序列為[]42.堆的形狀是一棵[]

A．二叉排序樹B.滿二叉樹C.完全二義樹D.平衡二叉樹

43.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為[]

A．希爾排序B.歸并排序C.插入排序D.選擇排序

44采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為[]

A．n2C.(n+1)/2D.(n-1)/2

45.散列查找是由鍵值______確定散列表中的位置，進行存儲或查找[]

A．散列函數(shù)值B.本身C.平方D.相反數(shù)

46.順序文件的缺點是[]

A．不利于修改B.讀取速度慢C.只能寫不能讀D.寫文件慢

47.索引文件的檢索方式是直接存取或按_____存取[]A．隨機存取B.關鍵字C.間接D.散列填空題若頻繁地對線性表進行插入與刪除操作，該線性表應采用______________存儲結構。在雙鏈表中，每個結點有兩個指針域，一個指向______，另一個指向_____?？崭翊莀___，其長度等于____。一個圖的表示法是唯一的，而表示法是不唯一的。對于長度為n的關鍵字有序的線性表，若進行順序查找，則時間復雜度為____；若采用二分法查找，則時間復雜度為____；設線性表中元素的類型是實型，其首地址為1024，則線性表中第6個元素的存儲位置是。對于順序存儲的棧，因為棧的空間是有限的，在進行運算時，可能發(fā)生棧的上溢，在進行運算時，可能發(fā)生棧的下溢。在雙向鏈表中，每個結點有兩個指針域，一個指向______，另一個指向_____。由一棵二叉樹的前序序列和可唯一確定這棵二叉樹。折半查找的存儲結構僅限于____，且是____。對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為和。分析下面算法（程序段），給出最大語句頻度，該算法的時間復雜度是____。{for(i=1;i<=n;i++)for(j=1;j<=i;j++)cout<<i+j;}稀疏矩陣的壓縮存儲結構，一種是表示法，而另一種是表示法。數(shù)據(jù)邏輯結構包括、和三種類型，樹形結構和圖形結構合稱為。在線性結構中，第一個結點前驅(qū)結點，其余每個結點有且只有個前驅(qū)結點；最后一個結點后續(xù)結點，其余每個結點有且只有個后續(xù)結點。在樹形結構中，樹根結點沒有結點，其余每個結點有且只有個直接前驅(qū)結點，葉子結點沒有結點，其余每個結點的直接后續(xù)結點可以。在圖形結構中，每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以。線性結構中元素之間存在關系，樹形結構中元素之間存在關系，圖形結構中元素之間存在關系。算法的五個重要特性是____,____,____,____,____。在一個單鏈表中p所指結點之前插入一個s(值為e)所指結點時，可執(zhí)行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=;20][5..10]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，則A[18][9]的地址是____。求下列廣義表操作的結果：(1)GetTail[GetHead[((a,b),(c,d))]];(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]n個頂點的連通圖至少____條邊。在無權圖G的鄰接矩陣A中，若(vi,vj)或＜vi,vj＞屬于圖G的邊集合，則對應元素A[i][j]等于____，否則等于____。已知一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是____。已知一個圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的邊的方法是____。如果含n個頂點的圖形成一個環(huán)，則它有棵生成樹。一個非連通無向圖，共有28條邊，則該圖至少有個頂點。遍歷圖的過程實質(zhì)上是。BFS遍歷圖的時間復雜度為，DFS遍歷圖的時間復雜度為，兩者不同之處在于，反映在數(shù)據(jù)結構上的差別是。順序查找法的平均查找長度為____；折半查找法的平均查找長度為____；哈希表查找法采用鏈接法處理沖突時的平均查找長度為____。在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是____。折半查找的存儲結構僅限于____，且是____。假設在有序線性表A[1..20]上進行折半查找，則比較一次查找成功的結點數(shù)為____，則比較二次查找成功的結點數(shù)為____，則比較三次查找成功的結點數(shù)為____，則比較四次查找成功的結點數(shù)為____，則比較五次查找成功的結點數(shù)為____，平均查找長度為____。對于長度為n的線性表，若進行順序查找，則時間復雜度為____；若采用折半法查找，則時間復雜度為____；已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當用折半查找90時，需進行次查找可確定成功；查找47時，需進行次查找成功；查找100時，需進行次查找才能確定不成功。二叉排序樹的查找長度不僅與有關，也與二叉排序樹的有關。一個無序序列可以通過構造一棵樹而變成一個有序樹，構造樹的過程即為對無序序列進行排序的過程。在利用快速排序方法對一組記錄（54，38，96，23，15，72，60，45，83）進行快速排序時，遞歸調(diào)用而使用的棧所能達到的最大深度為____，共需遞歸調(diào)用的次數(shù)為____，其中第二次遞歸調(diào)用是對____一組記錄進行快速排序。在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取____方法，其次選取____方法，最后選取____方法；若只從排序結果的穩(wěn)定性考慮，則應選取____方法；若只從平均情況下排序最快考慮，則應選取____方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應選取____方法。計算與算法應用題1.給定表（119，14，22，1，66，21，83，27，56，13，10）

請按表中元素的順序構造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長度。（9分）2.已知一個有向圖的頂點集V和邊集G分別為： V={a,b,c,d,e,f,g,h} E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>};假定該圖采用鄰接矩陣表示，則分別寫出從頂點a出發(fā)進行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點序列。（9分）3.設散列表的長度為13，散列函數(shù)為H（h）=k%13，給定的關鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構成的散列表。（8分）01234567891011124.對7個關鍵字進行快速排序，在最好的情況下僅需進行10次關鍵字的比較。

(1)假設關鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結果的初始關鍵字序列；

(2)對所舉序列進行快速排序，寫出排序過程。（９分）5.如圖所示二叉樹，回答下列問題。（9分）

6.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結點后的結果。7.已知一組記錄的排序碼為（46，79，56，38，40，80,

95，24），寫出對其進行快速排序的每一次劃分結果。8.

一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數(shù)為H（key）=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。9.

已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。10.假定對線性表(38，25，74，52，48，65，36)進行散列存儲，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應的平均查找長度分別為和。11．假定一組記錄的排序碼為(46，79，56，38，40，80，25，34，57，21)，則對其進行快速排序的第一次劃分后又對左、右兩個子區(qū)間分別進行一次劃分，得到的結果為：。12.下圖是帶權的有向圖G的鄰接表表示法。從結點V1出發(fā)，深度遍歷圖G所得結點序列為（A），廣度遍歷圖G所得結點序列為（B）；G的一個拓撲序列是（C）；從結點V1到結點V8的最短路徑為（D）；從結點V1到結點V8的關鍵路徑為（E）。其中A、B、C的選擇有：V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6V1,V2,V3,V8,V5,V7,V4,V6D、E的選擇有：①

V1,V2,V4,V5,V3,V8②

V1,V6,V5,V3,V8③

V1,V6,V7,V8④

V1,V2,V5,V7,V8

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

另外，還要求大家熟練掌握Huffman樹的構建方法，樹與二叉樹之間的轉(zhuǎn)換，以及各種排序方法的排序過程。五、閱讀下列算法，分析它的作用};};intLinkList::sum(){intx;NodeType*p;p=Head->next;while(p!=NULL){x++;p=p->next;}returnx;}裝訂線裝訂線VoidBstree::Search(KeyTypeK){intflag=0;BstNode*q=root,*p=NULL;while((q!=NULL)&&(flag==0)){if(q->key==K)flag=1;elseif(K<q->key){p=q;q=q->lch;}else{p=q;q=q->rch;}}if(flag==0)cout<<"\n查找失敗，無此結點！\n";elsecout<<"\n查找成功，找到："<<q->key<<endl;78785249294.假定從鍵盤上輸入一批整數(shù)，依次為：786345309134–1，請寫出輸出結果。#include<>#include<>consstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“”Voidmain(){stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))cout<<pop(a)<<””;cout<<end1;}該算法的輸出結果為：__________________________________________________________.5.閱讀以下二叉樹操作算法，指出該算法的功能。Template<calsstype>voidBinTree<Type>：：unknown(BinTreeNode<Type>*t){BinTreeNode<Type>*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}該算法的功能是：________________________________6.voidAA(LNode*HL,constElemType&item){LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while(p->next!=HL)p=p->next;newptr->next=HL;p->next=newptr;}對于結點類型為LNode的單鏈表，以上算法的功能為：7.voidBB(List&L){inti=0;while(i<{intj=i+1;while(j<{if[j]=={for(intk=j+1;k<;k++)[k-1]=[k];;}elsej++;}i++;}}以上算法的功能為：9.voidCC(BTreeNode*&BST){ElemTypea[6]={45，23，78，35，77，25}；BST=NULL；for(inti=0,i<6;i++)Insert(BST,a[i]);}調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：9.voidDD(){ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge(A,B,0,4,9);for(inti=0;i<10;i++)cout<<B[i]<<”“;cout<<endl;}調(diào)用該算法后，輸出結果為：};};ElemTtypeSqstack::pop(){ElemTypex;if(top==0)x=-999;else{x=elem[top];top--;}returnx;}};};voidSqstack::push(ElemTypex){if(top==MAX-1)cout<<”\n滿！”；else{top++;elem[top]=x;}}編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找item帶回整個結點的值并返回true，否則返回false。boolFind（BtreeNode*BST，ElemType&item）3.編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an-1，an，則逆序鏈接后變?yōu)?an，an-1，……a1。4.根據(jù)下面函數(shù)原型，編寫一個遞歸算法，統(tǒng)計并返回以BT為樹根指針的二叉樹中所有葉子結點的個數(shù)。intCount(BTreeNode*BT)；5.設A=(a1,...,am)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個比較A，B大小的算法。6.已知單鏈表a和b的元素按值遞增有序排列,編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。7.編寫遞歸算法，對于二叉樹中每一個元素值為x的結點，刪去以它為根的子樹，并釋放相應的空間。8.編寫算法判別T是否為二叉排序樹.9.已知帶頭結點的單鏈表是一個遞增有序表，試寫一算法，刪除表中值大于min且小于max的結點（若表中有這樣的結點），同時釋放被刪除結點的空間，這里min和max是兩個給定的參數(shù)。77Head97b15^502610.編寫一個算法，返回二叉查找樹中的關鍵字最小的元素值。

參考答案判斷題（每題1分）1．√2．×3．√4．×5．√6．√7．×8．×9．×10．×11×12√13×14√15×16√17×18×19.×20.×21.√22.×23.√24.√25.×26.×27.×28.√二、單項選擇題（每題2分）1．A2．B3．B4．D5．C6．A7．C8．C9．C10．B11．A12C13.

B

14.

D

15.

A

16.

A

17.

D

18.

C

19.

C

20.

A

21.

B

22.

A

23.

B

24.

D

25.

C

26.

B

27

C

35.C

三、填空題鏈式存儲結構前驅(qū)結點，后繼結點由一個或多個空格字符組成的串，其包含的空格個數(shù)鄰接矩陣，鄰接表O（n），O(log2n)1044入棧（插入），出棧（刪除）前驅(qū)結點，后繼結點中序序列順序存儲結構，有序的n，n-1最大語句頻度:n(n+1)/2，時間復雜度：O(n2)三元組表，十字鏈表線性結構、樹形結構、圖形結構，非線性結構沒有、1、沒有、1前驅(qū)、1、后續(xù)、任意多個任意多個一對一、一對多、多對多有窮性、確定性、可行性、輸入、輸出s,pq->next,q兩個串的長度相等且對應位置的字符相同200+（6*20+12）=3261000+((18-10)*6+(9-5))*4=1208(1).(b)(2).(d) 2.1;0求矩陣第i列非零元素之和將矩陣第i行全部置為零n9對每個頂點查找其鄰接點的過程；O（e）（e為圖中的邊數(shù)）；O（e）；遍歷圖的順序不同；DFS采用棧存儲訪問過的結點，BFS采用隊列存儲訪問過的結點。（n+1）/2、((n+1)*log2(n+1))/n-1、1+（為裝填因子）哈希表查找法順序存儲結構、有序的1、2、4、8、5、3．7（依題意，構造一棵有序二叉樹，共12個結點，第一層1個結點，第二層2個結點，第三層4個結點，第四層5個結點，則：ASL=（1*1+2*2+3*4+4*5）/12=37/12）O（n）、O(log2n)2、4、3結點個數(shù)n、生成過程二叉排序樹2.2;4;（23，38，15）堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序四、計算與算法應用題１．［解答］平均長度為4.

2、解：畫圖（略）深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g3、解：計算機關鍵碼得到的散列地址關鍵碼1914230168208427散列地址611013761在散列表中散列結果012345678910111214016827192084234.對n個關鍵自序列進行一趟快速排序，要進行n-1次比較，

也就是基準和其他n-1個關鍵字比較。

這里要求10次，而7-1+2*(3-1)=10，這就要求2趟快速排序后，算法結束。

所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4132657

或4137652

或4537612

或4135627.......(2)按自己序列完成012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)(2)搜索成功的平均搜索長度為l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／125．答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca6.在這個AVL樹中刪除根結點時有兩種方案:【方案1】在根的左子樹中沿右鏈走到底,用5遞補根結點中原來的6,再刪除5所在的結點.【方案2】在根的右子樹中沿左鏈走到底,用7遞補根結點中原來的6,再刪除7所在的結點.7.劃分次序劃分結果第一次[38

24

40]46

[56

80

95

79]第二次24

[38

40]46

[56

80

95

79]第三次24

38

40

46

[56

80

95

79]第四次24

38

40

46

56

[80

95

79]第五次24

38

40

46

56

79

[80

95]第六次24

38

40

46

56

79

80

958、

0

1

2

3

4

5

6

7

8

9

10

11

1278

1503

57452031

233612查找成功的平均查找長度：ASLSUCC=14/10=9、此二叉樹的后序遍歷結果是：EDCBIHJGFA10.13／71l／711．2l25[343840]46[795657]8012.12.(A)深度遍歷：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4，廣度遍歷：1，2，4，6，3，5，7，8拓撲序列：1，2，4，6，5，3，7，8最短路徑：1，2，5，7，8關鍵路徑：1，6，5，3，813.ASLsucc=（1+2X2+3X4+4X3）/10=14.源點終點最短路徑路徑長度121，3，21931，31541，3，2，42951，3，52961，3，2，