數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案

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

A.n-i+1B.i

C.i+1D.n-i

15.若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是[]

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

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

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

A.出隊(duì)B.入隊(duì)

C.取隊(duì)頭元素D.取隊(duì)尾元素

17.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(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.字符串通常采用的兩種存儲(chǔ)方式是[]A.散列存儲(chǔ)和索引存儲(chǔ)B.索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)D.散列存儲(chǔ)和順序存儲(chǔ)19.設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為[]

A.mB.n-m

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

A.429B.432

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

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

C.(f)D.()22.下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹是[]個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有[]

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

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

24.對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為[]

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-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為[]

A.4B.5

C.8D.9

26.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹[]

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

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

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

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

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

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

B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取

C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)

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

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

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

B．每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找

C．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的內(nèi)容

D．選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟

29.下面程序段的時(shí)間復(fù)雜度是[]

I=s=0

While(s<n)

{I++;

s+=I;

}

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

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

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

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

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

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

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

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

A.acb

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

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

>rear==0>front==0

35.設(shè)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層上至多有____個(gè)節(jié)點(diǎn)[]

A．2iB.2i-1

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

A．BDGCEFHA

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

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

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

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

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

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

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

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

45.散列查找是由鍵值______確定散列表中的位置，進(jìn)行存儲(chǔ)或查找[]

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

46.順序文件的缺點(diǎn)是[]

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

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

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

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

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

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

95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。8.

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

已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。10.假定對線性表(38，25，74，52，48，65，36)進(jìn)行散列存儲(chǔ)，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應(yīng)的平均查找長度分別為和。11．假定一組記錄的排序碼為(46，79，56，38，40，80，25，34，57，21)，則對其進(jìn)行快速排序的第一次劃分后又對左、右兩個(gè)子區(qū)間分別進(jìn)行一次劃分，得到的結(jié)果為：。12.下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點(diǎn)V1出發(fā)，深度遍歷圖G所得結(jié)點(diǎn)序列為（A），廣度遍歷圖G所得結(jié)點(diǎn)序列為（B）；G的一個(gè)拓?fù)湫蛄惺牵–）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑為（D）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的關(guān)鍵路徑為（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的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長度。14.已知如圖所示的有向網(wǎng)，試?yán)肈ijkstra算法求頂點(diǎn)1到其余頂點(diǎn)的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。

另外，還要求大家熟練掌握Huffman樹的構(gòu)建方法，樹與二叉樹之間的轉(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查找失敗，無此結(jié)點(diǎn)！\n";elsecout<<"\n查找成功，找到："<<q->key<<endl;78785249294.假定從鍵盤上輸入一批整數(shù)，依次為：786345309134–1，請寫出輸出結(jié)果。#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;}該算法的輸出結(jié)果為：__________________________________________________________.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;}對于結(jié)點(diǎn)類型為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)用該算法后，輸出結(jié)果為：};};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為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。boolFind（BtreeNode*BST，ElemType&item）3.編寫算法，將一個(gè)結(jié)點(diǎn)類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)閍1，……an-1，an，則逆序鏈接后變?yōu)?an，an-1，……a1。4.根據(jù)下面函數(shù)原型，編寫一個(gè)遞歸算法，統(tǒng)計(jì)并返回以BT為樹根指針的二叉樹中所有葉子結(jié)點(diǎn)的個(gè)數(shù)。intCount(BTreeNode*BT)；5.設(shè)A=(a1,...,am)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個(gè)比較A，B大小的算法。6.已知單鏈表a和b的元素按值遞增有序排列,編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。7.編寫遞歸算法，對于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。8.編寫算法判別T是否為二叉排序樹.9.已知帶頭結(jié)點(diǎn)的單鏈表是一個(gè)遞增有序表，試寫一算法，刪除表中值大于min且小于max的結(jié)點(diǎn)（若表中有這樣的結(jié)點(diǎn)），同時(shí)釋放被刪除結(jié)點(diǎn)的空間，這里min和max是兩個(gè)給定的參數(shù)。77Head97b15^502610.編寫一個(gè)算法，返回二叉查找樹中的關(guān)鍵字最小的元素值。

參考答案判斷題（每題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.√二、單項(xiàng)選擇題（每題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

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

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

也就是基準(zhǔn)和其他n-1個(gè)關(guān)鍵字比較。

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

所以，列舉出來的序列，要求在做partition的時(shí)候，正好將序列平分(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.在這個(gè)AVL樹中刪除根結(jié)點(diǎn)時(shí)有兩種方案:【方案1】在根的左子樹中沿右鏈走到底,用5遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除5所在的結(jié)點(diǎn).【方案2】在根的右子樹中沿左鏈走到底,用7遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除7所在的結(jié)點(diǎn).7.劃分次序劃分結(jié)果第一次[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、此二叉樹的后序遍歷結(jié)果是：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拓?fù)湫蛄校?，2，4，6，5，3，7，8最短路徑：1，2，5，7，8關(guān)鍵路徑：1，6，5，3，813.ASLsucc=（1+2X2+3X4+4X3）/10=14.源點(diǎn)終點(diǎn)最短路徑路徑長度121，3，21931，31541，3，2，42951，3，52961，3，2，