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

一、單項(xiàng)選擇題（每題2分，共20分）

1.棧和隊(duì)列的共同特點(diǎn)是（）。

A.只允許在端點(diǎn)處插入和刪除元素

B.都是先進(jìn)后出

C.都是先進(jìn)先出

D.沒(méi)有共同點(diǎn)

2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（）.

A.僅修改頭指針B.頭、尾指針都要修改

C.僅修改尾指針D.頭、尾指針可能都要修改

3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）

A.隊(duì)列B.棧C.線性表D.二叉樹(shù)

4,設(shè)有一個(gè)二維數(shù)組A[詞網(wǎng)，假設(shè)A[0][0]存放位置在64410），4⑵⑵存放位置在676（io），每個(gè)元素

占一個(gè)空間，問(wèn)A[3][3]（io）存放在什么位置？腳注（⑼表示用10進(jìn)制表示。

A.688B.678C.692D.696

5.樹(shù)最適合用來(lái)表示（）。

A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)

6.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為（）.

A.2k-lB.2K+1C.2K-1D.2k-'

7.若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[l]中，現(xiàn)進(jìn)行二分查找，則查

找A[3]的比較序列的下標(biāo)依次為（）

A.1,2,3B.9,5,2,3

C.9,5,3D.9,4,2,3

8.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為

A.0（1）B.O（n）C.O（log2n）D.O（n2）

9.對(duì)于線性表（7,34,55,25,64,46,20,10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散

列函數(shù)，則散列地址為1的元素有（）個(gè)，

A.1B.2C.3D.4

10.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。

A.5B.6C.7D.8

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

1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：―、___、和—。

2.一個(gè)算法的時(shí)間復(fù)雜度為（d+dlog,冰14〃）//,其數(shù)量級(jí)表示為。

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

樹(shù)的深度為,樹(shù)的度為——?

4.后綴算式923+-102/-的值為。中綴算式(3+4X)-2Y/3對(duì)應(yīng)的后綴算式為

5.若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這

種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有個(gè)指針域，其中有個(gè)指針域是存放了地址，

有個(gè)指針是空指針。

6.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有

n_個(gè)和個(gè)。

7.AOV網(wǎng)是一種的圖。

8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖

中，包含有條邊。

9.假定一個(gè)線性表為(12,23,74,55,63,40),若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成

為一個(gè)子表，則得到的四個(gè)子表分別為一、一一、

和O

10.向一棵B樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度。

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

雜度為—。

12.在快速排序、堆排序、歸并排序中，___排序是穩(wěn)定的。

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

1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A[Ol.next,試寫(xiě)出該線性表。

A01234567

605078903440

3572041

2.請(qǐng)畫(huà)出圖1的鄰接矩陣和鄰接表。

圖1

3.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。

4.畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)?，每加入一個(gè)數(shù)據(jù)后堆的變化。

四、閱讀算法（每題7分，共14分）

1.LinkListmynote(LinkListL)

{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

if(L&&L->next){

q=L；L=L->next；p=L；

SI：while(p—>next)p=p—>next；

S2：p—>next=q；q—>next=NULL；

)

returnL；

)

請(qǐng)回答下列問(wèn)題：

(I)說(shuō)明語(yǔ)句si的功能；

(2)說(shuō)明語(yǔ)句組S2的功能；

(3)設(shè)鏈表表示的線性表為(al,a2,…,an),寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。

2.voidABC(BTNode*BT)

(

ifBT{

ABC(BT->left);

ABC(BT->right);

cout<<BT->data?'';

}

)

該算法的功能是：

五、算法填空(共8分)

二叉搜索樹(shù)的查找一一遞歸算法：

boolFind(BTreeNode*BST,ElemType&item)

(

if(BST二二NULL)

returnfalse;〃查找失敗

else{

if(item==BST->data){

item=BST->data;〃查找成功

return;}

elseif(item<BST->data)

returnFind(,item);

elsereturnFind(,item);

}//if

六、編寫(xiě)算法(共8分)

統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。

intCountX(LNode*HL,ElemTypex)

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

一、單項(xiàng)選擇題(每題2分，共20分)

1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A

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

1.正確性易讀性強(qiáng)壯性高效率

2.O(n)

3.933

4,-134X*+2Y*3/?

5.2nn-1n+l

6.e2e

7.有向無(wú)回路

8.n(n-l)/2n(n-l)

9.(12,40)()(74)(23,55,63)

10.增加1

11.O(log2n)O(nlog2n)

12.歸并

三'算法簡(jiǎn)答題（每題6分，共24分）

1.線性表為:(78,50,40,60,34,90)

'01110'

10101

11011

10101

2.鄰接矩陣:01110

鄰接表如圖1所示:

圖1

3.用克魯斯卡爾算法得到的最小生成樹(shù)為:

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

5

4.畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。

四、閱讀算法(每題7分，共14分)

1.(1)查詢(xún)鏈表的尾結(jié)點(diǎn)

(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)

(3)返回的線性表為(a2,a3,…,an,al)

2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。

五、算法填空(共8分)

trueBST->leftBST->right

六、編寫(xiě)算法(共8分)

intCountX(LNode*HL,ElemTypex)

{inti=0;LNode*p=HL;〃i為計(jì)數(shù)器

while(p!=NULL)

{if(P->data=x)i++;

p=p->next;

)//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)

returni;

}//CountX

6

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

一、單項(xiàng)選擇題（每題2分，共8分）

1、在一個(gè)長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找

長(zhǎng)度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為（）。

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

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

所指的結(jié)點(diǎn)，則執(zhí)行（）。

Asflink=pflink;p-*link=s;Bp->link=s;s->link=q;

Cpflink=s-link;s-*link=p;Dq~Hink=s;s-*link=p;

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

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

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

為（）

A24B71C48D53

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

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

14.一種抽象數(shù)據(jù)類(lèi)型包括和兩個(gè)部分。

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

a012345678

data

605642387425

next

4376201

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

條件分別為和。

17.用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的

,該循環(huán)隊(duì)列的最大長(zhǎng)度為.

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

鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用表示。

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

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

個(gè)結(jié)點(diǎn)。

21.在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱(chēng)為,通常它包含三個(gè)域：一是

；二是；三是o

7

22.在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的和—

兩項(xiàng)數(shù)據(jù)。

23.假定一棵樹(shù)的廣義表表示為A(B(C,D(E,F,G),II(I,J))),則樹(shù)中所含的

結(jié)點(diǎn)數(shù)為個(gè)，樹(shù)的深度為樹(shù)的度為,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)

為,孩子結(jié)點(diǎn)為o

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

排序過(guò)程的時(shí)間復(fù)雜度為o

25.在對(duì)m階的打樹(shù)插入元素的過(guò)程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)(葉子結(jié)點(diǎn)中

的索引項(xiàng)為關(guān)鍵字和空指針)后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于個(gè)，則必須把它分裂

為個(gè)結(jié)點(diǎn).

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

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

速排序的每一次劃分結(jié)果。

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

散列函數(shù)為H(key)=key%13并用線性探查法解決沖突，請(qǐng)畫(huà)出散列表，并計(jì)算等

概率情況下查找成功的平均查找長(zhǎng)度。

7.已知一棵二叉樹(shù)的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷的結(jié)果是

EBCDAF1IIGJ,試寫(xiě)出這棵二叉樹(shù)的后序遍歷結(jié)果。

8.已知一個(gè)圖的頂點(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)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫(xiě)出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索

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

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

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

鄰接矩陣表示時(shí)

鄰接表表示時(shí)

四、閱讀算法(每題8分，共16分)

1、假定從鍵盤(pán)上輸入一批整數(shù)，依次為：786345309134-1,請(qǐng)寫(xiě)出輸出

結(jié)果。

#include<iostream.h>

ttinclude<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(istackempty(a))

cout<<pop(a)?,M,;

cout?endl;

)

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

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

Template<calsstype>voidBinTree<Type>：：

unknown(BinTreeNode<Type>*t){

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

if(p!=NULL){

temp=p-leftchild;

pfleftchild=pfrightchild;

pfrightchild=temp;

unknown(p->leftchiId);

undnown(p-*rightchild);

)

}

9

該算法的功能是：_________________________________

五、算法填空(共10分)

對(duì)順序存儲(chǔ)的有序表進(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

}

六、編寫(xiě)算法(共8分)

編寫(xiě)算法，將一個(gè)結(jié)點(diǎn)類(lèi)型為L(zhǎng)node的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素

的次序?yàn)閍i,.......an.i，an?則逆序鏈接后變?yōu)?a”ae，……ai?

Voidcontrary(Lnode*&HL)

10

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

一、單項(xiàng)選擇題（每題2分，共8分）

題號(hào)1234

答案CDAB

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

1：集合、線性、樹(shù)、圖；

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

3：（38,56,25,60,42,74）；

4：HL-next=NULL；HL=HL-next；

5：前一個(gè)位置；n-1；

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

7：531

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

9：索引值域、開(kāi)始位置域；

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

11：0（loginO（nlog2n）;

12：m、m-1

三、算法簡(jiǎn)答題（每題6分，共24分）

1、

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

第一次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

2、

0123456789101112

78150357452031233612

查找成功的平均查找長(zhǎng)度：ASLSUCC=14/10=1.4

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

4、

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

鄰接矩陣表示時(shí)0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9

鄰接表表示時(shí)0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5

四、閱讀算法(每題8分，共16分)

1、該算法的輸入結(jié)果是：349130456378

2、該算法的功能是：交換二叉樹(shù)的左右子樹(shù)的遞歸算法。

五、算法填空(共8分)

1：(low+high)/2;

2：Binsch(A,low,mid-1,K);

3：Binsch(A,mid+1,high,K);

4：-1；

六、編寫(xiě)算法(共12分)

Voidcontrary(Lnode*&HL)

(

Lnode*P=HL;

HL=NULL;

While(p!=null)

(

Lnode*q=p;

P=pfnext;

q-*next=HL;

HL=q;

)

)

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

一、單項(xiàng)選擇題(每題2分，共30分)

1.算法指的是()

12

A.計(jì)算機(jī)程序B.解決問(wèn)題的計(jì)算方法

C.排序算法D.解決問(wèn)題的有限運(yùn)算序列

2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址()

A.必須是不連續(xù)的

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)

3.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為()

A.0(1)B.O(n)C.O(m)D.O(m+n)

4.由兩個(gè)棧共享一個(gè)向量空間的好處是：()

A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率

B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率

C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率

D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率

5.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針,

則執(zhí)行出隊(duì)操作后其頭指針front值為()

A.front=front+1B.front=(front+1)%(m-1)

C.front=(front-l)%mD.front=(front+l)%m

如下陳述中正確的是()

A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零

C.串中元素只能是字母D.空串就是空白串

7.若目標(biāo)串的長(zhǎng)度為n,模式串的長(zhǎng)度為[n/3],則執(zhí)行模式匹配算法時(shí)，在最壞情況

下的時(shí)間復(fù)雜度是()

n

A.0(3)B.0(n)C.O(n2)D.0(n3)

8.一個(gè)非空廣義表的表頭()

A.不可能是子表B.只能是子表

C.只能是原子D.可以是子表或原子

9.假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表

對(duì)應(yīng)的稀疏矩陣是()

-0-8060-806

70007000

0000B.-5040

-50400000

00000300

13

■()-806

0-806

0000

0000

C.0200D.7000

-5040-5040

00000300

10.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)

點(diǎn)個(gè)數(shù)為（）

A.4B.5C.6D.7

11.在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）

A.eB.2eC.n2—eD.n2—2e

12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的

所有弧的時(shí)間復(fù)雜度是（）

A.O（n）B.0（e）C.O（n+e）D.O（n*e）

13.用某種排序方法對(duì)關(guān)鍵字序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序

時(shí)，序列的變化情況如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則所采用的排序方法是（）

A.選擇排序B.希爾排序C.歸并排序D.快速排序

14.適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）

A.有序表B.分塊有序表C.三叉排序樹(shù)D.線性鏈表

15.不定長(zhǎng)文件是指（）

A.文件的長(zhǎng)度不固定B.記錄的長(zhǎng)度不固定

C.字段的長(zhǎng)度不固定D.關(guān)鍵字項(xiàng)的長(zhǎng)度不固定

二、填空題（每題2分，共20分）

1.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無(wú)關(guān)，是獨(dú)立于

計(jì)算機(jī)的。

2.在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針

head可用p表示為head=。

3.棧頂?shù)奈恢檬请S著操作而變化的。

4.在串S="structure”中，以t為首字符的子串有個(gè)。

5.假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B[0]存

14

儲(chǔ)矩陣中第1個(gè)元素as,則B[31]中存放的元素是。

6.已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有個(gè)葉子結(jié)點(diǎn)。

7.已知一個(gè)圖的廣度優(yōu)先生成樹(shù)如右圖所示，則與此相

應(yīng)的廣度優(yōu)先遍歷序列為o???

8.在單鏈表上難以實(shí)現(xiàn)的排序方法有和o

9.在有序表(12,24,36,48,60,72,84)中二分查找關(guān)犍字72時(shí)所需進(jìn)行的關(guān)鍵

字比較次數(shù)為。

10.多重表文件和倒排文件都?xì)w屬于文件。

三、算法簡(jiǎn)答題(每題5分，共20分)

1.畫(huà)出下列廣義表的共享結(jié)構(gòu)圖形表示

P=(((z),(x,y)),((x,y),x),(z))

2.請(qǐng)畫(huà)出與下列二叉樹(shù)對(duì)應(yīng)的森林。

3.已知一個(gè)無(wú)向圖的頂點(diǎn)集為｛a,b,c,d,e｝，其鄰接矩陣如下所示

01001

1(X)1()

0(X)11

01101

10110

(1)畫(huà)出該圖的圖形；

(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫(xiě)出相應(yīng)的遍

歷序列。

4.已知一個(gè)散列表如下圖所示：

3520334859

0123456789101112

15

其散列函數(shù)為卜(1^丫)=1<?丫％13,處理沖突的方法為雙重散列法，探查序列為：

hi=(h(key)+i*hl(key))%mi=O,l,…，m—1

其中

h1(key)=key%11+1

回答下列問(wèn)題：

(1)對(duì)表中關(guān)鍵字35,20,33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？

(2)該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？

四'閱讀算法(每題6分，共18分)

1.下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：

-1當(dāng)S|<S2

<0當(dāng)S|=s,

1當(dāng)S|>s2

comstr(sl,s2)=

請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。

intcomstr(LinkStringsi,LinkStrings2)

{//si和s2為兩個(gè)鏈串的頭指針

while(sl&&s2){

if(sl->date<s2->date)return_1；

if(sl—>date>s2—>date)return1；

①；

②；

if(③)return—1；

if(?)returnl；

⑤；

①

②

③

④

16

⑤

2.假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間(參見(jiàn)右下圖)，

“"⑴浮吟:"""

其類(lèi)型Queue2定義如下：即⑼

typedefstruct{

DateTypedata[MaxSize]；

intfront[2],rear[2]；

)Queue2；

對(duì)于i=0或1,fronts和rear[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法

填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。

intEnQueue(Queue2*Q,inti,DateTypex)

{//若第i個(gè)隊(duì)列不滿(mǎn)，則元素X入隊(duì)列，并返回1；否則返回0

if(i<O||i>l)returnO；

if(Q->rear[i]==Q—>front[①]returnO；

Q—>data[②]=x；

Q->rear[i]=[③];

return1；

)

@

②

③

33.已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。

typedefstructnode{

DateTypedata；

Structnode*next；

JListNode；

typedefListNode*LinkList；

LinkListLeafhead=NULL；

17

VoidInorder(BinTreeT)

LinkLists；

If(T){

Inorder(T—>lchild)；

If((!T->lchild)&&(!T->rchild)){

s=(ListNode*)malloc(sizeof(ListNode))；

s—>data=T—>data；

s->next=Leafhead；

Leafhead=s；

)

Inorder(T—>rchild)；

)

對(duì)于如下所示的二叉樹(shù)

(1)畫(huà)出執(zhí)行上述算法后所建立的結(jié)構(gòu);

(2)說(shuō)明該算法的功能。

五、編寫(xiě)算法(共8分)

閱讀下列函數(shù)arrange()：

intanange(inta[],intl,inth,intx)

{//l和h分別為數(shù)據(jù)區(qū)的下界和上界

inti,j,t；

i=l；j=h：

while(i<j){

18

while(i<j&&a[j]>=x)j—；

while(i<j&&a[j]>=x)i++；

if(i<j)

{t=a[j]；a[j]=a[i]；a[i]=t；}

)

if(a[i]<x)returni；

elsereturni_1；

)

(1)寫(xiě)出該函數(shù)的功能；

(2)寫(xiě)一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組b[n]中的元素進(jìn)行重新

排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若

有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。

19

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

一'單項(xiàng)選擇題（每題2分，共30分）

1.D2.B3.C4.B5.D

6.A7.C8,D9,A10.C

11.D12.C13.D14.C15.B

二、填空題（每小題2分，共20分）

1：存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)）

2：p—>next—>next

3：進(jìn)棧和退棧

4：12

5：34,8

6：384

7：abefcdg

8：快速排序、堆排序、希爾排序

9：2

10：多關(guān)鍵字

三、算法簡(jiǎn)答題（每題4分，共20分）

3、

(1)

20

(2)深度優(yōu)先遍歷序列為：abdce

廣度優(yōu)先遍歷序列為：abedc

4、

(1)對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1；

(2)平均查找長(zhǎng)度

^=3+2+1+1+29

55

四、閱讀算法(每題6分，共18分)

1、@S1=S1—>next

②s2=s2—>next

③s2(或s2!=NULL或s2&&!sl)

④si(或sl!=NULL或sl&&!s2)

?return0

2、①(i+l)%2(或l—i)

②Q—>rear[i]

③(Q—>rear[i]+)%Maxsize

3、

針的逆序單鏈表(或按二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表)。

五、編寫(xiě)算法(共12分)

(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a口中的元素并返回分界值i,使所有Vx的元素

均落在a[l..i]±,使所有?x的元素均落在a[i+l..h]±o

(2)intf(intb[],intn)或intf(intb[],intn)

intp,q；intp,q；

21

p=arrange(b,O,n—1,0)；p=arrange(b,0,n—1,1)；

q=arrange(b,p+l,n—1,1)；q=arrange(b,0,pT0)；

returnq—p；returnp—q；

}}

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

一、單項(xiàng)選擇題(每題2分，共20分)

1.組成數(shù)據(jù)的基本單位是()。

(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類(lèi)型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

2.設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D={1,2,3,4},R={r},r={<b2>,<2,3>,<3,

4>,<4,1>),則數(shù)據(jù)結(jié)構(gòu)A是()。

(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合

3.數(shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。

(A)線性表(B)棧(C)隊(duì)列(D)樹(shù)

4.二叉樹(shù)中第i(i?l)層上的結(jié)點(diǎn)數(shù)最多有()個(gè)。

(A)2i(B)2i(C)2i-l(D)2i-l

5.設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為()。

(A)p->next=p->next->next(B)p=p->next

(C)p=p->next->next(D)p->next=p

6.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素El、E2、E3、E4、E5和E6依次通過(guò)棧S,

一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則

棧S的容量至少應(yīng)該是()。

(A)6(B)4(C)3(D)2

7.將10階對(duì)稱(chēng)矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長(zhǎng)度最少為()。

(A)100(B)40(C)55(D)80

8.設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn),則結(jié)點(diǎn)B的度數(shù)數(shù)為()。

(A)3(B)4(C)5(D)1

9.根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有()種不同的形態(tài)。

(A)4(B)5(C)6(D)7

10.設(shè)有以下四種排序方法，則()的空間復(fù)雜度最大。

22

(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序

二、填空題(每題2分，共20分)

1.設(shè)順序循環(huán)隊(duì)列Q[0：m-1]的隊(duì)頭指針和隊(duì)尾指針?lè)謩e為F和R,其中隊(duì)頭指針F

指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)

列的語(yǔ)句為F=；o

2.設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度

為，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為。

3.設(shè)一棵二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共

有個(gè)指針域，個(gè)空指針域。

4.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)B,則在結(jié)點(diǎn)A

的后面插入結(jié)點(diǎn)B的操作序列為Q

5.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對(duì)應(yīng)的鄰接表中有個(gè)表頭結(jié)點(diǎn)

和個(gè)表結(jié)點(diǎn)。

6.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條動(dòng)，所有頂點(diǎn)的度數(shù)之和為m,則e和m有

關(guān)系。

7.設(shè)一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹(shù)的后序遍歷

序列為。

8.設(shè)一棵完全二叉樹(shù)中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開(kāi)始

順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是,編號(hào)為8的左孩子結(jié)點(diǎn)的編

號(hào)是o

9.下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)

句。

intindex(chars[],chart[])

(

i=j=0;

while(i<strlen(s)&&j<strlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i=;j=;}

if(j==strlen(t))retum(i-strlen(t));elsereturn(-1);

)

10.設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則其最小生成樹(shù)上有條邊。

三、運(yùn)算題(每題6分，共30分)

1.設(shè)完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE,要求給出該二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)

構(gòu)并給出該二叉樹(shù)的前序、中序和后序遍歷序列。

23

2.設(shè)給定一個(gè)權(quán)值集合W=(3,5,7,9,11),要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫

曼樹(shù)并計(jì)算哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。

3.設(shè)一組初始記錄關(guān)鍵字序列為(19,21,16,5,18,23),要求給出以19為基準(zhǔn)的一

趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。

4.設(shè)一組初始記錄關(guān)鍵字集合為(25,10,8,27,32,68),散列表的長(zhǎng)度為8,散列

函數(shù)H(k)=kmod7,要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。

5.設(shè)無(wú)向圖G(所下圖所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出

該圖的最小生成樹(shù)。

四、算法設(shè)計(jì)題(每題10分，共30分)

1.設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱(chēng)算法。

2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹(shù)的算法。

3.設(shè)計(jì)判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法。