數(shù)據(jù)結(jié)構(gòu)期末試題

一、選擇題（共30分）

1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的計(jì)算機(jī)操作的（B）和以及它

們之間存在的（D）和操作的學(xué)科。

（DA.數(shù)據(jù)映像B.數(shù)據(jù)元素C.邏輯存儲(chǔ)D.計(jì)算方法

（2）A.結(jié)構(gòu)B.運(yùn)算C.算法D.關(guān)系

2.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將數(shù)據(jù)結(jié)構(gòu)分為：（C）。

A.動(dòng)態(tài)結(jié)構(gòu)和表態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

3.線性表的邏輯順序和存儲(chǔ)順序總是一致的，這種說(shuō)法（B

A.正確B.不正確

4.算法分析的目的是（C）,算法分析的兩個(gè)主要方面是（A）o

（1）A.找了數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性

（2）A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

5.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（B）。

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

C.head->next=headD.head!=NULL

6.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p應(yīng)該滿足（C）o

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

C?p->next=headD.p=head

7.在一個(gè)單鏈表中，刪除p所指的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行語(yǔ)句（A）?

A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；

C.p->next=p->next；D.p=p->next->next；

8.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（D

A.必須連續(xù)B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以

9.對(duì)順序存儲(chǔ)的線性表，設(shè)其表長(zhǎng)為n,且在任何位置插入或刪除操作都是等概率的，則

插入一個(gè)元素平均要移動(dòng)表中（B）個(gè)元素。

A.n/2B.（n+l）/2C.（n-l）/2D.n

10.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是（D）

A.插入刪除操作更容易B.可以進(jìn)行隨機(jī)訪問(wèn)

C.可以省略頭結(jié)點(diǎn)指針D.順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活

11.棧的特點(diǎn)是（B）。插入操作在（C）進(jìn)行，刪除操作在（C）進(jìn)行。

（1）A.先進(jìn)先出B.先進(jìn)后出

C.在棧頂D.在棧底

D.棧頂或棧底E.隨機(jī)位置

12.一個(gè)棧的進(jìn)棧次序?yàn)閍,b,c,d,e,則棧不可能的出棧序列是（C）。

A.edcbaB.decbaC.dceabD.abcde

13.若已知一個(gè)棧的進(jìn)棧序列為l,2,34..n,其出棧序列為Pi,P2,P3v--Pn>若有Pi=n,則

Pi（l=vi〈n）一定為（C）。

A.iB.nC.n-i+1D.不確定

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

A.383B.384C.385D.386

15.先序遍歷和中序遍歷相同的二叉樹為（D）?

A.只有根結(jié)點(diǎn)的二叉樹B.根結(jié)點(diǎn)無(wú)左孩子的二叉樹

C.一般二叉樹

D.只有根結(jié)點(diǎn)的二叉樹和所有結(jié)點(diǎn)只有右子樹的二叉樹

16.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（C）條邊。

A.nB.n（n-l）C.n（n-l）/2D.2n

17.（B）的鄰接矩陣是對(duì)稱矩陣。

A.有向圖B.無(wú)向圖C.AOV圖

18.鄰接表是圖的（B）。

A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)

19.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（C）。

A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)

C.以順序方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序排列

D.以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序排列

20.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（C）0

A.nB.n/2C.（n+l）/2D.（n-l）/2

21.有一個(gè)有序序列（1,2,3,4,5,6）,當(dāng)用二分法進(jìn)行查找值為4的結(jié)點(diǎn)時(shí)，經(jīng)過(guò)（C）次

比較后查找成功。

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

22.二叉樹的第i層最多有（C）個(gè)結(jié)點(diǎn)。

A.2’B.2iC.2“D.2」

23.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（C）倍。

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

24.一個(gè)無(wú)向連通圖（B）最小生成樹。

A.只有一棵B.一棵或多棵C.一定有多棵D.不一定有

25.一個(gè)圖的（B）表示法是唯一的，而（C）表示法是不唯一的。

A.三元組B.鄰接矩陣C.鄰接表D.索引

二、選擇題（每空1分，共30分）

1.線性結(jié)構(gòu)中元素之間存在的關(guān)系，樹形結(jié)構(gòu)中的元素之間

存在的關(guān)系，圖形結(jié)構(gòu)中的元素之間存在的關(guān)系。

2.算法的五個(gè)特點(diǎn)是：,,

3.棧是限定僅在表尾進(jìn)行操作的線性結(jié)構(gòu)。表頭端稱為,表尾的一端

稱為O

4.隊(duì)列是限定僅在表尾進(jìn)行和在表頭進(jìn)行的線性表，其特點(diǎn)

是：O

5.如有如下順序棧的定義

#defineMAXSIZE500

Typedefstruct{

chardata[MAXSIZE];

inttop;

Jsqstack;

sqstackss;

則棧空的條件是，棧滿的條件是，棧頂元素的表達(dá)

式是,棧底元素的表達(dá)式是?

6.在一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（l〈=iv=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)的

元素個(gè)數(shù)數(shù)為。

7.在雙鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向，另一個(gè)指

向o

8.數(shù)據(jù)的邏輯結(jié)構(gòu)包括,,,四種類型；其中和

統(tǒng)稱為非線性結(jié)構(gòu)。

9.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為和。其中要求邏輯上相鄰

的元素物理上也相鄰的存儲(chǔ)方式為o

三、簡(jiǎn)答題（每小題6分，共30分）

1.下列程序段的時(shí)間復(fù)雜度是O（mn）o

for（i=0;i<n;i++）

for（j=O;j<m;j++）

a[i]D]=0；

2.設(shè)將整數(shù)1,2,3,4依次進(jìn)棧，只要出棧時(shí)棧非空，則可將出棧操作按任何次序插入到進(jìn)

棧操作之間,請(qǐng)問(wèn)若進(jìn)棧、出棧的次序?yàn)?push（l）,pop。、push⑵、push⑶、pop。、

pop。、push（4）、pop（）,則出棧的數(shù)字序列是：1324,

3.已知二叉樹的后序遍歷和中序遍歷序列如下，構(gòu)造該二叉樹,并寫出它的先序遍歷序列。

后序：DEBFGCA中序：DBEAFCG答案：先序：ABDECFG

4.如圖所示的有向圖，試給出其拓?fù)渑判颍?36415287。

5.設(shè)有一組關(guān)鍵字（10,20,14,17,19,23,27,15,40,38,35,37）,采用哈希函數(shù)

H（key）=key%13

采用開放地址法的線性探測(cè)再散列方法解決沖突，試在[0-12]的散列地址空間中對(duì)

該關(guān)鍵字序列構(gòu)造哈希表。

四、判斷題（每小題1分，共5分）

1.線性表的順序存儲(chǔ)結(jié)構(gòu)要比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)節(jié)省空間。（）

2.N個(gè)元素進(jìn)棧的次序一定與它們出棧的順序相反。（）

3.在非空二叉樹中，只有最下面一層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。（）

4.在一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要n-1條邊。（）

5.二叉樹的遍歷方法有先序、中序和后序三種。（）

五、編程（共5分）

有如下二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義：

typedefstructnode

{intdata;

structnode*rchild,lchild;

}BITNode,*BiTree;

請(qǐng)完善先序遍歷函數(shù)。

voidPreOrder(BiTreeroot)

一、單選題(每題2分，共20分)

1.1.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下(B)方面的內(nèi)容。

A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度

2.2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)

點(diǎn)，則執(zhí)行(A)0

A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;

C.p->next=HL;p=HL;D.HL=p;p->next=HL;

3.3.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？(B)

A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變

4.4.一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是

(C)

A.231B.321

C.312D.123

5.5.AOV網(wǎng)是一種(D)o

A.有向圖B.無(wú)向圖C.無(wú)向無(wú)環(huán)圖D.有向無(wú)環(huán)圖

6.6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度(B)o

A.低于鏈接法處理沖突B.高于鏈接法處理沖突

C.與鏈接法處理沖突相同D.高于二分查找

7.7.若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為(D)參數(shù)。

A.值B.函數(shù)C.指針D.引用

8.8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具

有相同的(A)o

A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)

9.9.快速排序在最壞情況下的時(shí)間復(fù)雜度為(D)o

A.O(log2n)B.O(nlog2n)C.0(n)D.0(n2)

10.10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為(C)。

2

A.0(n)B.0(1)C.O(log2n)D.0(n)

二、二、運(yùn)算題(每題6分，共24分)

1.1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的聯(lián)系。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N(M：

N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為—圖」

2.2.隊(duì)列的插入操作是在隊(duì)列的_尾_進(jìn)行，冊(cè)此余操作是在隊(duì)列的—首進(jìn)行。

3.3.當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t

表示棧滿的條件是—top=0—（要超出才為滿）_。

4.4.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度

為0（1）_,在表尾插入元素的時(shí)間復(fù)雜度為0（n_。

5.5.設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0

到7,列下標(biāo)j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用128_個(gè)字節(jié)。

W中第6行的元素和第4列的元素共占用_44一個(gè)字節(jié)。若按行順序存放二

維數(shù)組W,其起始地址為100,則二維數(shù)組元素W[6,3]的起始地址為108一。

6.6.廣義表人=俎包,1））,（包,15）?）,則它的深度為_3—,它的長(zhǎng)度為_3—o

7.7.二叉樹是指度為2的.有序—樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)

點(diǎn)的度的總和是

8.8.對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)有序序列一。

對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該

算術(shù)表達(dá)式的—后綴表達(dá)式一。

9.9.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_2n_

個(gè)，其中n-l_個(gè)用于指向孩子_n+l個(gè)指針是空閑的。

10.10.若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存

儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類推，則A[i]

元素的左孩子元素為2i+l_,右孩子元素為_2i+2_,雙親元素為___（i-l）/2o

11.11.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有開放定址法和一

鏈接法_兩種。

12.12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用

排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序

是穩(wěn)定時(shí)，宜采用排序。

三、三、運(yùn)算題（每題6分，共24分）

1.1.已知一個(gè)6x5稀疏矩陣如下所示，

00001

00000

0-1000

0000-2

50000

00700

試：

(1)(1)寫出它的三元組線性表；

(2)(2)給出三元組線性表的順序存儲(chǔ)表示。

2.2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起,

逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹、

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

1.1.intPrime(intn)

(

inti=l;

intx=(int)sqrt(n);

while(-H-i<=x)

if(n%i=0)break;

if(i>x)return1;

elsereturn0;

}

(1)(1)指出該算法的功能；

(2)(2)該算法的時(shí)間復(fù)雜度是多少？

2.2.寫出下述算法的功能：

voidAJ(adjlistGL,inti,intn)

{

QueueQ;

InitQueue(Q);

cout?i?**;

visited[i]=true;

QInsert(Q,i);

while(!QueueEmpty(Q)){

intk=QDelete(Q);

edgenode*p=GL[k];

while(p!=NULL)

{

intj=p->adjvex;

if(!visited[j])

(

cout<<j?,

visited[j]=true;

QInsert(Q,j);

p=p->next;

五、五、算法填空(共8分)

如下為二分查找的非遞歸算法，試將其填寫完整。

IntBinsch(ElemTypeA[],intn,KeyTypeK)

{

intlow=0;

inthigh=n-l;

while(low<=high)

{

intmid=；

if(K==A[mid].key)returnmid;〃查找成功，返回元素的下標(biāo)

elseif(K<[mid].key)

__________________________________；〃在左子表上

繼續(xù)查找

else;〃在右子表

上繼續(xù)查找

)

return-1;〃查找失敗，返回

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

HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。

ElemTypeDeleFront(LNode*&HL)

參考答案

一、單選題(每題2分，共20分)

1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C

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

1.1.聯(lián)系圖(或圖結(jié)構(gòu))

2.

圖7

8.8.有序序列后綴表達(dá)式(或逆波蘭式)

9.9.2nn-1n+1

10.10.2i+l2i+2(i-l)/2

11.11.開放定址法鏈接法

12.12.快速歸并

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

1.1.(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)

(a)(b)(c)(d)(e)(f)

圖8

(2)三元組線性表的順序存儲(chǔ)表示如圖7示。

2.2.如圖8所示。

3.3.DFS：①②③④⑤

BFS：②③④⑤①

4.4.拓樸排序?yàn)椋?365721

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

1.1.(1)判斷n是否是素?cái)?shù)(或質(zhì)數(shù))

(2)O()

2.2.功能為：從初始點(diǎn)片出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。

五、五、算法填空(8分)

(low+high)/2high=mid-1low=mid+l

六、六、編寫算法(8分)

ElemTypeDeleFront(LNode*&HL)

(

if(HL==NULL){

cerrvv”空表“wendl;

exit(1);

}

LNode*p=HL;

HL=HL->next;

ElemTypetemp=p->data;

deletep;

returntemp;

一、單選題(每題2分，共20分)

1.1.棧和隊(duì)列的共同特點(diǎn)是(A)0

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

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

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

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

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

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

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

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

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

4.4.設(shè)有一個(gè)二維數(shù)組河[川，假設(shè)A[0][0]存放位置在644（io），A[2][2]

存放位置在67加0）,每個(gè)元素占一個(gè)空間，問(wèn)A[3][3]（io）存放在什么位置？

腳注（⑼表示用10進(jìn)制表示。

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

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

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

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

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

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

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

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

9.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.10.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（）條邊才能確保是一個(gè)

連通圖。

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

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

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

和O

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

3.3.假定一棵樹的廣義表表示為A（C,D（E,F,G）,H（I,J））,則樹中

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

4.4.后綴算式923+-102/-的值為。中綴算式（3+4X）-2Y/3

對(duì)應(yīng)的后綴算式為?

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

右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有個(gè)

指針域，其中有個(gè)指針域是存放了地址，有個(gè)指

針是空指針。

6.6.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表

中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。

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

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

有n個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。

9.9.假定一個(gè)線性表為(12,23,74,55,63,40),若按Key%4條件進(jìn)行劃分，使

得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為

和O

10.10.向一棵B_樹插入元素的過(guò)程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹

比原樹的高度o

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

，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為。

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

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

1.1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A[0].next,試寫

出該線性表。

A01234567

data605078903440

next3572041

2.2.請(qǐng)畫出圖10的鄰接矩陣和鄰接表。

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

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};

用克魯斯卡爾算法得到最小生成樹，試寫出

在最小生成樹中依次得到的各條邊。

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

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

1.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è)鏈表表示的線性表為…,a。，寫出算法執(zhí)行后的返回值所

表示的線性表。

2.2.voidABC(BTNode*BT)

{

ifBT{

ABC(BT->left);

ABC(BT->right);

cout?BT->data?'

i

i

}

該算法的功能是：

五、五、算法填空(共8分)

二叉搜索樹的查找——遞歸算法：

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

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

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

intCountX(LNode*HL,ElemTypex)

參考答案

一、一、單選題(每題2分，共20分)

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

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

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

2.2.O(n)

3.3.933

4.4.-134X*+2Y*3/-

5.5.2nn-1n+1

6.6.e2e

7.7.有向無(wú)回路

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

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

10.10.增加1

11.11.O(log2n)O(nlog2n)

12.12.歸并

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

1.1.線性表為：(78,50,40,60,34,90)

01110

10101

11011

10101

01

2.2.鄰接矩陣：L110

鄰接表如圖11所示：

圖11

圖12

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

1.1.（1）查詢鏈表的尾結(jié)點(diǎn)

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

（3）返回的線性表為（a2,a3/-,an,a1）

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

五、五、算法填空（每空2分，共8分）

trueBST->leftBST->right

六、六、編寫算法（8分）

intCountX（LNodc*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

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

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

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

都相等）為（）0

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

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

插入一個(gè)s所指的結(jié)點(diǎn)，則執(zhí)行（）o

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

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

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

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

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

帶權(quán)路徑長(zhǎng)度為（）

A24B71C48D53

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

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

_____四種。

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

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

該線性表為。

a012345678

data

605642387425

next

4376201

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

斷鏈表為空的條件分別為和o

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

向隊(duì)首元素的,該循環(huán)隊(duì)列的最大長(zhǎng)度為。

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

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

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

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

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

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

8、8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為,通常它包含三個(gè)域:

一是；二是；三是O

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

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

10、10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H

(I,J))),則樹中所含的結(jié)點(diǎn)數(shù)為個(gè)，樹的深度為,

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

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

雜度為，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為。

12、12、在對(duì)m階的B_樹插入元素的過(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)。

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

1、1、已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫

出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。

2、2、一個(gè)線性表為B=(12,23,45,57,20,03,78,31,15,36),設(shè)

散列表為HT[0..12],散列函數(shù)為H(key)=key%13并用線性探查法解

決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。

3、3、已知-一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷

的結(jié)果是EBCDAFHIGJ,試寫出這棵二叉樹的后序遍歷結(jié)果。

4、4、已知一個(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í)，分別寫出從頂點(diǎn)V。出發(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í)

四、四、閱讀算法，回答問(wèn)題(每小題8分，共16分)

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

寫出輸出結(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!=-l){

push(a,x);

cm?x;

while(!stackempty(a))

cout?pop(a)

cout?end1;

)

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

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

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);

)

)

該算法的功能是：__________________________________

五、五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(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

編寫算法（10分）

編寫算法，將一個(gè)結(jié)點(diǎn)類型為L(zhǎng)node的單鏈表按逆序鏈接，即若原單鏈表中

存儲(chǔ)元素的次序?yàn)榭?，……an.1，an,則逆序鏈接后變?yōu)?a.,……a,o

Voidcontrary（Lnode*&HL）

數(shù)據(jù)結(jié)構(gòu)試題（答案）

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

題號(hào)1234

答案CDAB

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

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

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：索引值域、開始位置域；

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

11：O（log2n）>O（nlog2n）;

12：m>m-1

三、運(yùn)算題（每小題6分，共24分）

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

第?次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

0123456789101112

78150357452031233612

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

3、此二叉樹的后序遍歷結(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

四、閱讀算法，回答問(wèn)題（每小題8分，共16分）

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

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

五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)

1>1是：(low+high)/2;

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

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

4是：-I；

六、編寫算法(10分)

根據(jù)編程情況，酌情給分。

(

Lnode*P=HL;

HL=NULL;

While(p!=null)

{

Lnode*q=p;

P=pfnext;

qfnext=HL;

HL=q;

第一部分選擇題（30分）

一、一、項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的

四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題

后的括號(hào)內(nèi)。

1.算法指的是（）

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.O(1)B.O(n)C.O(m)