《數(shù)據(jù)結(jié)構(gòu)》模擬試題02

《數(shù)據(jù)結(jié)構(gòu)》模擬試題02

一、單項選擇題（每題2分，共8分）

1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與

元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為（）。

AnBn/2C（n+l）/2D（n-l）/2

2、在一個單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入一個s所指的結(jié)點(diǎn),

則執(zhí)行（）。

As-*link=p-*link;p-*link=s;Bp-*link=s;s—link=q;

Cpflink=link;s->link=p;Dq->link=s;s->link=p;

3、棧的插入和刪除操作在（）進(jìn)行。

A棧頂B棧底C任意位置D指定位置

4、由權(quán)值分別為11,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）

A24B71C48D53

二、填空題（每空1分，共32分）

1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、、和______四種。

2.一種抽象數(shù)據(jù)類型包括和兩個部分。

3.在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0],next,則該線性表為

a012345678

605642387425

4376201

4.在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為

和O

5.用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的,

該循環(huán)隊列的最大長度為o

6.當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用------------表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)

時，棧頂元素的值可用一表示。

7.一棵高度為5的二叉樹中最少含有個結(jié)點(diǎn)，最多含有個結(jié)點(diǎn)；

8.一棵高度為5的理想平衡樹中，最少含有.個結(jié)點(diǎn)，最多含有個結(jié)點(diǎn)。

9.在圖的鄰接表中，每個結(jié)點(diǎn)被稱為,通常它包含三個域：一是；二

是;三是。

10.在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的和兩項數(shù)據(jù)。

11.假定一棵樹的廣義表表示為A（B（C,D（E,F,G）,H（I,J）））,則樹中所含的結(jié)點(diǎn)數(shù)為

個，樹的深度為，樹的度為,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為，孩子結(jié)點(diǎn)為

12.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為，整個堆排序過程的時

間復(fù)雜度為。

13.在對m階的B_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項(葉子結(jié)點(diǎn)中的索引項為關(guān)鍵

字和空指針)后，若該結(jié)點(diǎn)的索引項數(shù)等于_____個，則必須把它分裂為個結(jié)點(diǎn)。

三、算法簡答題(每題6分，共24分)

1.已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫出對其進(jìn)行快速排序的每一

次劃分結(jié)果。

2.一個線性表為B=(12,23,45,57,20,03,78,31,15,36),設(shè)散列表為HT[0..12],散列

函數(shù)為H(key)=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成

功的平均查找長度。

3.已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試寫出

這棵二叉樹的后序遍歷結(jié)果。

4.已知一個圖的頂點(diǎn)集V各邊集G如下：

V=[0,1,2,3,4,5,6,7,8,9}；

E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,

9),(6,7),(7,8),(8,9)}

當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)

序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。

假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。

圖深度優(yōu)先序列廣度優(yōu)先序列

鄰接矩陣表示時

鄰接表表示時

四、閱讀算法（每題8分，共16分）

1,假定從鍵盤上輸入一批整數(shù)，依次為：786345309134-1,請寫出輸出結(jié)果。

#include<iostream.h>

#include<stdlib.h>

consstintstackmaxsize=30;

typedefintelemtype;

structstack{

elemtypestack[stackmaxsize];

inttop;

);

#include“stack,h”

Voidmain()

(

stacka;

initstack(a);

intx;

cin?x;

while(x!=-1){

push(a,x);

cin?x;

)

while(!stackempty(a))

cout<<pop(a)<<"";

cout<<endl;

)

該算法的輸出結(jié)果為：

2、閱讀以下二叉樹操作算法，指出該算法的功能。

Template<calsstype>voidBinTree<Type>：：

unknown(BinTreeNode<Type>*t){

BinTreeNode<Type>*p=t,*temp;

if(p!=NULL){

temp=p—leftchild;

pfleftchild=pfrightchild;

p—rightchild=temp;

unknown(p-*-leftchild);

undnown(p->rightchiId);

)

)

該算法的功能是：

五、算法填空(共10分)

對順序存儲的有序表進(jìn)行二分查找的遞歸算法。

intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)

if(low<=high)

intmid=1

if(K==A[mid].key)

returnmid;

elseif(K<A[mid].key)

return2__

else

return3__

}

else

return4

)

六、編寫算法(共8分)

編寫算法，將一個結(jié)點(diǎn)類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序?yàn)?/p>

ai，.......an.i，an,則逆序鏈接后變?yōu)?，a”an-i,........ai.

Voidcontrary(Lnode*&HL)

《數(shù)據(jù)結(jié)構(gòu)》模擬試題02參考答案

一、單項選擇題(每題2分，共8分)

題號1234

答案CDAB

二、填空題(每空1分，共32分)

1：集合、線性、樹、圖；

2：數(shù)據(jù)描述、操作聲名；

3：(38,56,25,60,42,74)；

4：HL—next=NULL；HL二HL—next；

5：前一個位置；n-1；

6：S.stack[S.top];HS->data;

7：531

8：邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；

9：索引值域、開始位置域；

10：10、3、3、B、I和J；

11：0(log2n)、O(nlog2n);

12：m、m-1

三'算法簡答題(每題6分，共24分)

劃分次序劃分結(jié)果

第一次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

2、

0123456789101112

78150357452031233612

查找成功的平均查找長度：ASLSUCC=14/10=1.4

3、此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA

4