數(shù)據(jù)結(jié)構(gòu)試卷及答案

東華理工大學(xué)2022—2022學(xué)年第一學(xué)期考試摹

擬試卷A

一、填空題（50分）

1、數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的重?fù)?jù)元盍_以及它們之間關(guān)系和

運(yùn)算等的科學(xué)。（2分）

2、數(shù)據(jù)結(jié)構(gòu)的類型通常分為：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)或者網(wǎng)狀結(jié)構(gòu)：

從邏輯上可以把它們分成：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

3、數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系；數(shù)據(jù)的存儲(chǔ)（物理）

結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)。

4、算法分析的目的是分析算法的效率以求改進(jìn)，算法分析的兩個(gè)主要方面是空I巫

復(fù)雜度和時(shí)間復(fù)雜度?

A

5、計(jì)算機(jī)算法是解決問(wèn)題的有限運(yùn)算序列，它必須具備輸入、輸出、確定性、有窮性

和穩(wěn)定性等5個(gè)方面的特性。

6、線性結(jié)構(gòu)中元素之間的關(guān)系存在?對(duì)一關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間的關(guān)系存在;

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

7、試寫(xiě)出以下算法的時(shí)間復(fù)雜度

i=s=0

while（s<n）{

i++；

s+=i;

I

。而

7、試寫(xiě)出以下算法的時(shí)間復(fù)雜度

i=1

while(i<=n)

i=i*2

O(log2n)

8、抽象數(shù)據(jù)類型的定義由三元組來(lái)定義：(D,S,P)其中，D是數(shù)據(jù)對(duì)象，S是D上的

關(guān)系集，P是對(duì)D的基本操作集。

9、寫(xiě)出抽象數(shù)據(jù)類型線性表的定義

ADTList{

數(shù)據(jù)對(duì)象：D={ai|aiElemset,i=l,2,...,n,n0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}

基本操作：

InitList(&L)〃構(gòu)造一個(gè)空的線性表L

DestroyList(&L)〃消毀線性表L

ListLength(L)//返回L中數(shù)據(jù)元素的個(gè)數(shù)

ListInsert(&L,i,e)//1<i<ListLength(L)+l,在L中第i個(gè)位置之前插入數(shù)據(jù)元素e,L長(zhǎng)度

加1

ListDelete(&L,i,&e)//1<i<ListLength(L)刪除L中的第i個(gè)元素，并用e返回

ListTraverse(L,visit())//挨次對(duì)L的每一個(gè)元素調(diào)用函數(shù)visit()

}ADTList

10、指出線性表順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。

答：順序存儲(chǔ)優(yōu)點(diǎn)：邏輯上相鄰，物理位置也相鄰，可以隨機(jī)存取表中任一元素：缺點(diǎn)：插

入和刪除元素時(shí)需要挪移大量元素。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)：插入、刪除元素時(shí)不需要挪移元素；缺點(diǎn)：邏輯上相鄰，物理位置

不一定相鄰，不能隨機(jī)存取表中元素，需要挨次查找，求線性表的長(zhǎng)度時(shí)不如順序存儲(chǔ)結(jié)構(gòu)

方便，需要逐個(gè)結(jié)點(diǎn)搜索計(jì)算，或者設(shè)置帶頭結(jié)點(diǎn)的線性鏈表。

11、完成下列在單鏈表中刪除元素算法

StatusListDelete_L(LinkLisl&L,inti,ElemType&e){〃刪除第i個(gè)元素e

p=L;j=0;〃p指向頭結(jié)點(diǎn)

while(p->next&&j<i-l)(

p=p->next;++j

}//尋覓第i個(gè)結(jié)點(diǎn)，并令P指向其前驅(qū)

if(!(p->next)||j>i-l)returnERROR;〃刪除位置不正確

q=p->next;p->next=q->next;〃刪除與釋放結(jié)點(diǎn)e=q-

>data;

free(q);

returnOK;

)

12、在一個(gè)長(zhǎng)度為n的線性鏈表中第i個(gè)元素(1in)之前插入一個(gè)元素時(shí)，需向后挪移n?i+l

個(gè)元素。

13、在一個(gè)長(zhǎng)度為n的線性鏈表中刪除第i個(gè)元素(1in)時(shí)，需向前挪移n-i個(gè)元素。

14、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=p->next和

p->next=s的操作。

15、在單鏈表中，插入或者刪除一個(gè)結(jié)點(diǎn)元素時(shí)，僅需要修改指針而不需要挪移元素。

16、棧(Stack)是限定僅在表尾進(jìn)行插入和刪除操作的線性表，

17、棧鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中刪除棧頂元素，并用e返回，完成下列算法

StatusPop(ListStack&S,SElemType&e){

if(S.top=NULL)returnERROR;〃棧無(wú)元素

p=S.top;

S.top=S.top->next;

e=p->data;

free(p);〃釋放節(jié)點(diǎn)批p

S.len—;

returnOK;

)

17、設(shè)有一隊(duì)列，(al,a2,…,an)則對(duì)頭元素是al隊(duì)尾元素是an。

18、假設(shè)隊(duì)列以帶頭結(jié)點(diǎn)的鏈?zhǔn)奖硎?，則刪除一不元素并返回給e的算法如下:

StatusDeQueue(LinkQueue&Q,QElemType&e){

if(Q.front==Q.rear)returnEEROR;

p=Q.front->next;//p為需要?jiǎng)h除的結(jié)點(diǎn)

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;〃隊(duì)列中惟獨(dú)一個(gè)元素被刪除時(shí)，隊(duì)尾等于隊(duì)頭

free(p);

returnOK;

}

19、循環(huán)隊(duì)列中，假設(shè)少用一個(gè)元素，則插入元素到隊(duì)尾的算法

StatusEnQueue(SqQueue&Q,QElemTypee){

if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;〃隊(duì)滿

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;//Q.rear前移

returnOK;

)

20、循環(huán)隊(duì)列中，假設(shè)少用一個(gè)元素，則/刪除隊(duì)頭元素并賦給e的算法如下

StatusDeQueue(SqQueue&Q,QElemType&e){

if(Q.front=Q.rear)returnERROR;〃隊(duì)空

e=Q.base[Q.Oont];

Q.front=(Q.front+1)%MAXQSIZE;//Q.rear前移

returnOK;

)

21、判定一個(gè)隊(duì)列QU(最多元素為MaxSize)為空的條件是：QU->front==QU->rear；為

滿隊(duì)列的條件是：QU->rear-QU->front==MaxSize。

22、SUABCDEFG's2=TQRST\假設(shè)con(x,y)為連接兩字符串函數(shù)，subs(s,i,j)返回串s

中從第i個(gè)位置起的j個(gè)字符，len(s)返回串s的長(zhǎng)度，則

con(subs(sl,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串為：BCDEFEF

23、什么是稀疏矩陣？如何衡量？舉例采用三元子順序表示已稀疏矩陣。

答：當(dāng)矩陣中的非零元素比較少，且分布沒(méi)有一定的規(guī)律，稱為稀疏矩陣。稀疏矩陣的衡量

標(biāo)準(zhǔn)，可以用稀疏因子表示，通常認(rèn)為當(dāng)W0.05是稱為稀疏矩陣

t

mn

24、深度為5的二叉樹(shù)最多有31個(gè)結(jié)點(diǎn)。

25、深度為k的徹底二叉樹(shù)至少有2k-l個(gè)結(jié)點(diǎn)，至多有2k-l個(gè)結(jié)點(diǎn)，若自上而下，從

左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編號(hào)最小的葉結(jié)點(diǎn)的編號(hào)是2k-1。

26、己知一棵二叉樹(shù)的中序遍歷序列為cbedahgijf,后序遍歷序列為cedbjigfa,畫(huà)出該二

叉樹(shù)。

二、設(shè)有下列一棵樹(shù)，回答下列問(wèn)題：（15分）

1）該樹(shù)的根結(jié)點(diǎn)是A:

2）這棵樹(shù)的葉結(jié)點(diǎn)是G、E、F、I、J；

3）該樹(shù)的非終端結(jié)點(diǎn)是A、C、B、D、H；

4）D結(jié)點(diǎn)的度是1；

5）該樹(shù)的度是3；樹(shù)深度是4；

6）將該樹(shù)轉(zhuǎn)換成二叉樹(shù)。（5分）

7）假設(shè)對(duì)該樹(shù)進(jìn)行先根遍歷、后根遍歷，寫(xiě)出該樹(shù)的先根序列、后根系列。（5分）

先根序列：ACGDHIJBEF

后根系列：GCIJHDEFBA

2、數(shù)據(jù)邏輯結(jié)構(gòu)包括：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)三種類型，樹(shù)形結(jié)構(gòu)和圖

形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。（4分）

3、下列程序段的時(shí)間復(fù)雜度是0（n）。（2分）

i=s=0;

while（s<n）{

i++；

s+二i;

）

4^判斷一個(gè)循環(huán)隊(duì)列QU（最多元素為mO）為滿隊(duì)列的條件是QU->front==（QU->rear+1）%

mOo（2分）

5、帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是head->next==NULL。（2分）

6、假設(shè)線性表采用單鏈表存儲(chǔ)結(jié)構(gòu),完成下列插入元素的算法（5分）

StatusListInsert_L（LinKLis&tL,inti,ElementTypee）

{/在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素

P=L;j=0;

while(p&&j<i-1)p={p->next;++j}

if(!p||j>i-l)returnERRORs=(

LinkLismtaDloc(sizeof(LNode));s->data=

e；

s->next-p->next;一

p->next=s;returnOK

)

7、若x和y是兩個(gè)采用順序結(jié)構(gòu)存儲(chǔ)的串，編寫(xiě)并完成比較兩個(gè)串是否相等的函數(shù)。(6分)int

Issame(orderstring*x,orderstring*y)

(

inti=0;tag=1;

if(x->len!=y->len)retum(O);

else

(

while(ivx->len&&tag)

(

if(x->vec[i]!=y->vec[i]t)ag=0;

i++;

)

return(tag);

)

)

8、已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每一個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)

元素的存儲(chǔ)地址是LOC(A[0]⑼)，則用的地址是LOC(A⑼[0])+(n*i+j)*k。(2分)

10、下圖所示的4棵二叉樹(shù)，是平衡二叉樹(shù)的樹(shù)是B、D。(4分)

11、深度為k的徹底二叉樹(shù)至少有2口個(gè)結(jié)點(diǎn)，至多有27個(gè)結(jié)點(diǎn)，若

從上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編號(hào)最小的葉結(jié)點(diǎn)的編號(hào)是

）2+1。（3分）.

12、有向徹底圖：具有n（n-l）條邊的有向圖稱為有向徹底圖。（2分）

13、對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排

列°（4分）

14、一組記錄的排序碼為（17,48,2435,69,8223,79,3）6,,其72中含有5個(gè)長(zhǎng)度為2的有序表，按歸并

排序的方法對(duì)該序列進(jìn)行一趟歸并排序后的結(jié)果為：

17,24,35,48,23,69,79,82,36,72。（6）

15、己知系列｛503,87,512,61,908,170,897,275,653,462）,以第一個(gè)記錄為樞

軸（基準(zhǔn)），寫(xiě)出采用快速排序法對(duì)該序列作升序排序時(shí)的第一趟的結(jié)果：（5分）[462,87,

275,61,170]503[89,7908,653,503]。

三、已直一棵二叉樹(shù)的中序遍歷系列為kbedohgijf,后序遍歷系列為kedbhjigfb,畫(huà)出該二叉

樹(shù)。（5分）

四、稀疏矩陣有什么特點(diǎn)？假設(shè)用三元組順序表來(lái)表示稀疏矩陣，試設(shè)計(jì)該方法的存儲(chǔ)結(jié)構(gòu)。

寫(xiě)出下列稀疏矩陣的三元組表示。（10分）

0020

3000

0015

0000

答：實(shí)際非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的個(gè)數(shù)（0.05）。

三元組順序表示存儲(chǔ)結(jié)構(gòu)可設(shè)計(jì)如下:

#MAXSIZE12500;

typedefstruct{

intij;

Elemtypee;

JTriple;

typedefstruct{

Tripledata[MAXSIZE+1]；

intmu,nu,tu;

JTSMatrix;

將下列樹(shù)轉(zhuǎn)換成二叉樹(shù)

①

已知有5個(gè)字符(4b,cd)e,它們浮現(xiàn)的權(quán)值分別是｛12,4,5,2。，3｝試構(gòu)建一

個(gè)赫夫曼樹(shù)，并求它們的赫夫曼編碼。

a(0),b(100),c(101),d(110),e(lll)

徹底圖:對(duì)于有n頂點(diǎn)的無(wú)向圖，邊E的取值范圍是0?n(n-l)/,2當(dāng)n個(gè)

頂點(diǎn)的無(wú)向圖有n(n-l)/2條邊時(shí)稱為徹底圖

有向徹底圖:對(duì)于有n頂點(diǎn)的無(wú)向圖，邊E的取值范圍是0?n(n-l),當(dāng)n

個(gè)頂點(diǎn)的有向圖有n(n-l)條邊時(shí)稱為有向徹底圖采用鄰接表存

儲(chǔ)圖的深度優(yōu)先遍歷法算類似與二叉樹(shù)的先序遍歷，

而廣度優(yōu)先遍歷算法類似與二叉樹(shù)的層序遍歷。

已知一個(gè)有向圖用鄰接矩陣表示，則計(jì)算第i結(jié)點(diǎn)入度的方法是求

矩陣第i列非0元素之和。

圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列是不惟一的。

三、圖的存儲(chǔ)結(jié)構(gòu)有哪幾種？請(qǐng)用鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)表示下圖。(10分)

參考答案:

（1）圖的存儲(chǔ)結(jié)構(gòu)有有：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表四種表

示方法。（2分）

（2）鄰接矩陣儲(chǔ)結(jié)構(gòu)如下：（4分）

01000

10101

01011

00101

01110

（3）鄰接表存儲(chǔ)結(jié)構(gòu)如下：（4分）

五、用Dijstra方法求下圖中從V0點(diǎn)到各終點(diǎn)的最短路徑，并在表格中填寫(xiě)求

解過(guò)程。（12分）

參考答案：

（1）在表格中填寫(xiě)算過(guò)程（8分）

從V0點(diǎn)到各終點(diǎn)的D值和最短路徑的求解過(guò)程

線占

八、、

1=11=21=31=41=5

1

VI

(vO,vl)

2

V2

{v0,vl,v2}

553

V3

(v0,v3)(v0,v3)(v0,vl,v2,v3)

V4無(wú)

34

44

V5

(v0,v5)(v0,vl,v5)

(v0,vl,v5)(v0,vl,v5)

V1vz-

VJV3V5

IvOvl!IvOvlv?l

S{v0,vl,v2,v3,v5}

(2)闡述丫0到各點(diǎn)的路徑(4分)

vO到vl點(diǎn)的最短路徑為1,頂點(diǎn)為(vO,vl)

vO到v2點(diǎn)的最短路徑為2,頂點(diǎn)為(v0,vl,v2)

vO到v3點(diǎn)的最短路徑為3,頂點(diǎn)為(v0,vl,v2,v3)

vO到v4點(diǎn)之間無(wú)路徑

vO到v5點(diǎn)的最短路徑為4,頂點(diǎn)為(v0,vl,v5)

五、試找出下列有向無(wú)環(huán)網(wǎng)的關(guān)鍵路徑。(10分)

頂點(diǎn)veV1邊e11-e

VI00al099

V2413a2077

V3613