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

第一章緒論

復(fù)習(xí)內(nèi)容：

(1)基本概念和術(shù)語(yǔ)

(2)抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)

(3)估算算法時(shí)間復(fù)雜度

復(fù)習(xí)題：

1.仿照三元組的抽象數(shù)據(jù)類(lèi)型寫(xiě)出抽象數(shù)據(jù)類(lèi)型有理數(shù)的定義(有理數(shù)是其分子、分母均

為自然數(shù)且分母不為零的分?jǐn)?shù))。

ADTRational_Num{

數(shù)據(jù)小象：D={<el,e2>|el,e2Gn(n為整數(shù)集合)}

數(shù)據(jù)關(guān)系：Rl={〈el,e2>,el是有理數(shù)分子，e2是有理數(shù)分母，且e2W0}

基本操作：

InitRational_Num(&T,vl,v2)

操作結(jié)果：構(gòu)遙了有理數(shù)T,元素el,e2分別被賦以參數(shù)vl,v2的值。

DestroyRationalNum(&T)

操作結(jié)果：有理數(shù)T被銷(xiāo)毀。

Get(T,i,&e)

初始條件：有理數(shù)T已存在，iC{l,2}.

操作結(jié)果：用e返回T有理數(shù)的分子和分母的值，i=l返回分子，i=2返回分母。

Put(&T,i,e)

初始條件：有理數(shù)T已存在，iG{l,2}.

操作結(jié)果：改變有理數(shù)T的分子或分母的值為e,i=l改變分子，i=2改變分母。

AddRational_Num(T1,T2,&T3)

初始條件：有理數(shù)T已存在。

操作結(jié)果：有理數(shù)Tl、T2相加，結(jié)果存入有理數(shù)T3。

SubRational_Num(Tl,T2,&T3)

初始條件：有理數(shù)T已存在。

操作結(jié)果：有理數(shù)Tl、T2相減，結(jié)果存入有理數(shù)T3。

Mu1Rational_Num(Tl,T2,&T3)

初始條件：者理數(shù)T已存在。

操作結(jié)果：有理數(shù)Tl、T2相乘，結(jié)果存入有理數(shù)T3。

DivRational_Num(Tl,T2,&T3)

初始條件：看理數(shù)T已存在。

操作結(jié)果：有理數(shù)Tl、T2相除，結(jié)果存入有理數(shù)T3。

}ADTi=l;k=0;

while(i<=n-l){

@k+=10*i;

i++；

)

答案：n-1

(2)for(i=2;i<=n;++i)

fora=2;j<=i-l;++j)

{++x;a[ij]=x;}

答案：1+2+3+...+n-2=(n-l)(n-2)/2=(n2-3n+2)/2

3.試寫(xiě)一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值。

voidDescendingO

scanf(x,y,z);

if(x<y)

{temp=x;x=y;y=temp;}〃使x>=y

if(y<z)

(

temp=z;z=y;〃使temp>z

if(x>=temp)y=temp;

else{y=x;x=temp;}

)

printf(x,y,z);

}//Descending

第二章」線(xiàn)性表

復(fù)習(xí)內(nèi)容：

(1)線(xiàn)性表的類(lèi)型和定義

(2)線(xiàn)性表的順序表示和實(shí)現(xiàn)

(3)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)

(4)一元多項(xiàng)式的表示及相加

線(xiàn)性表--順序存儲(chǔ)結(jié)構(gòu)--順序表

線(xiàn)性表--鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)---鏈表

線(xiàn)性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)查找、插入和刪除的算法

區(qū)分線(xiàn)性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

復(fù)習(xí)題：

1.(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)【表中一半】元素，具體移動(dòng)的元素

個(gè)數(shù)與【表長(zhǎng)和該元素在表中的位置】有關(guān)。

(2)順序表中邏輯上相鄰的元素的物理位置【必定】緊鄰。單鏈表中邏輯上相鄰的元素的物

理位置【不一定】緊鄰。

2.例2-1假設(shè):有兩個(gè)集合A和B分別用兩個(gè)線(xiàn)性表LA和LB表示，即：線(xiàn)性表中的

數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合A=AUB。

3.簡(jiǎn)述順序表和單鏈表的優(yōu)缺點(diǎn)。

順序表-優(yōu)點(diǎn)：①邏輯相鄰，物理相鄰②可隨機(jī)存取任一元素③存儲(chǔ)空間使用緊湊。缺點(diǎn)：

①插入、刪除操作需要移動(dòng)大量的元素②預(yù)先分配空間需按最大空間分配，利用不充分③表

容量難以擴(kuò)充。

單鏈表-優(yōu)點(diǎn)①它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用②不需預(yù)先分配空間③插

入、刪除操作方便。①單鏈表的缺點(diǎn)②指針占用額外存儲(chǔ)空間③不能隨機(jī)存取，查找速度慢。

4.寫(xiě)出按正位序建立一個(gè)單鏈表的算法。

voidCreateList_L(LinkList&L,intn)

(

//正序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表

for(i=1;i<n;i++)

(

p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;

L->next=p;〃插入

}

}//CreateList_L

5.己知L是帶裝頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下

列提供的答案中選擇合適的語(yǔ)句序列。

(1)刪除P結(jié)點(diǎn)的語(yǔ)句序列是【JLGCN】。

(2)刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是【IKCN】。

第2頁(yè)，共9頁(yè)

zA\

t|

x7P=P->next;

zB\

(|

x7P->next=P;

zC\

(|

x7P->next=P->next->next;

ZD

eP=P->next->next;

ZE

e

Fwhile(P!=NULL)P=P->next;

while(Q->next!=NULL){P=Q;Q=Q->next;}

z\

?G

tJ

x7while(P->next!=Q)P=P->next;

/H

Kwhile(P->next->next!=Q)P=P->next;

zD

(

xwhile(P->next->next!=NULL)P=P->next;

z

(

\JQ二P；

zx

?

?)

\)KzQ=P->next;

z\

()

\L/P=L;

/f

(l

.ML=L->next;

/\

(N)

Xzfree(Q);

6.指出以下算法中的錯(cuò)誤和低效(即費(fèi)時(shí))之處，并將它改寫(xiě)為一個(gè)既正確又高效的算法。

StatusDeletK(SqList&La,intI,intk)

{〃本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表La中刪除第i個(gè)元素起

〃的k個(gè)元素

If(i<l||k<O||i+k>La.length)returnERROR；

//參數(shù)不合法

else{for(count=l;count<k;count++)//刪除一個(gè)元素

for(j=La.length;j>=i+l;j-)

La.elem[j-l]=La.elem[j];

La.length-;}

returnok;

}//DeleteK

第二個(gè)for語(yǔ)句中，元素前移的次序錯(cuò)誤；

低效之處是每次刪除一個(gè)元素的策略。

改正后的算法：

StatusDeletK(SqList&La,intI,intk)

{〃本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表La中刪除第i個(gè)元素起

//的k個(gè)元素

If((0<i<=a.length)&&(0<=k<=a.length-i))

(

for(j=i+k;j<=La.length;j++)

La.elem[i++]=La.elem[j];

La.length=La.length-k;

returnok;

)

elsereturnERROR；

}//DeleteK

7.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給

出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分

別為prior和next)o

pfnextfprior=q;

qfnext=pfnext;

q->prior=p;

p->next=q;

8.設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。

第三章棧和隊(duì)列

復(fù)習(xí)內(nèi)容：

(1)棧的定義及實(shí)現(xiàn)

第3頁(yè)，共9頁(yè)

(2)棧的應(yīng)用

(3)隊(duì)列的定義及實(shí)現(xiàn)

(4)隊(duì)列的應(yīng)用

復(fù)習(xí)題：

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

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

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

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

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

2.利用棧的結(jié)構(gòu)對(duì)列車(chē)車(chē)廂進(jìn)行調(diào)度則①如果進(jìn)站的車(chē)廂序列為123,則可能得到的出站

車(chē)廂序列是什么？[123,132,213,231,321]②如果進(jìn)站的車(chē)廂序列為123456,則能否得到

435612和135426的出站序列，并請(qǐng)說(shuō)明為什么不能得到或者如何得到(即寫(xiě)出以'S'表

示進(jìn)棧和以'X'表示出棧的棧操作序列)?！究梢缘玫?35426,不可能得到435612,因?yàn)?/p>

‘4356'出棧說(shuō)明12己在棧中，則1不可能在2之前出棧?！?/p>

3.寫(xiě)出檢驗(yàn)括號(hào)匹配的算法。(見(jiàn)作業(yè))

4.假設(shè)將循環(huán)隊(duì)列定義為：以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置

和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件。

判斷循環(huán)隊(duì)列的隊(duì)滿(mǎn)：

1.另外設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿(mǎn)

2.少用一個(gè)元素空間：

隊(duì)空：front==rear隊(duì)滿(mǎn)：(rear+l)%M==front

3.使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)

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

向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列

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

(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M

第四章串

復(fù)習(xí)內(nèi)容：

(1)串類(lèi)型的定義；

(2)串的三種存儲(chǔ)表示：定長(zhǎng)順序結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；

(3)串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用。

復(fù)習(xí)題：

1.設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。

StatusSubString(SString&Sub,SStringS,intpos,intlen){

//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。

〃其中IWposWStrLength(S)且OWlenWStrLength(S)-pos+l

if(pos<l||pos>S[0]||len<0||len>S[0]-pos+l)

returnERROR;

Sub[l.......len]=S[pos...pos+len-1]；

Sub⑼=len；

returnOK;

}//SubString

2.已知下列字符串

a=<THIS,,f='ASAMPLEJ,c='GOOD',d='NE',b=,

s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),

t=Replace(f,SubString(f,3,6),c),

u=Concat(SubString(c,3,1),d),g='IS'

第4頁(yè)，共9頁(yè)

v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),

請(qǐng)問(wèn)：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么?

答：s='THISSAMPLEIS'；t='AGOOD'；v='THISSAMPLEISAGOODONE'；StrLength(s)=14；

Index(v,g)=3；Index(u,g)=0o

第五章數(shù)組和廣義表

復(fù)習(xí)內(nèi)容：

(1)數(shù)組的類(lèi)型定義

(2)數(shù)組的順序表示和實(shí)現(xiàn)

(3)矩陣的壓縮存儲(chǔ)

(4)廣義表的定義

(5)廣義表的存儲(chǔ)結(jié)構(gòu)

復(fù)習(xí)題：

1.稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。

2.稀疏矩陣的壓縮存儲(chǔ)方法：【三元組順序表，行邏輯鏈接的順序表，十字鏈表】

3.設(shè)有一個(gè)10階的下三角矩陣A(包括對(duì)角線(xiàn))，按照從上到下、從左到右的

順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則

A[5][4]地址與A[0][0]的地址之差為(B)o

(A)10(B)19(C)28(D)55

4.

三角矩陣

an00........0

叫1a220........0

............................0

3nlMan3..........%

按行序?yàn)橹餍颍?/p>

alla21a22|a31a32anlanp|

K=012~3^~n(n-l)/2n(n+l)/2-I

Loc(aij)=?

答案：Loc(aij)=Loc(all)+[i*(i-l)/2+(j-l)]*L

5.描述采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T的快速轉(zhuǎn)置算法。

6.畫(huà)出下面矩陣的十字鏈表。

3005

0-100

2000

答：

M.chead

第5頁(yè)，共9頁(yè)

第六章樹(shù)和二叉樹(shù)

復(fù)習(xí)要求：掌握樹(shù)和二叉樹(shù)的概念、存儲(chǔ)結(jié)構(gòu)，基本運(yùn)算及其遍歷，掌握哈夫曼樹(shù)的概念和

構(gòu)造方法。

復(fù)習(xí)內(nèi)容：

(1)樹(shù)的定義和基本術(shù)語(yǔ)

(2)二叉樹(shù)

(3)遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)

(4)樹(shù)和森林

(5)哈夫曼樹(shù)及其應(yīng)用

復(fù)習(xí)題：

1.畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T

樹(shù)的先根次序訪(fǎng)問(wèn)序列為GFKDAIEBCHJ

樹(shù)的后根次序訪(fǎng)問(wèn)序列為DIAEKFCJHBG

2.畫(huà)出和下列己知序列對(duì)應(yīng)的森林F

森林的先序訪(fǎng)問(wèn)序列為ABCDEFGHIJKL

森林的中序訪(fǎng)問(wèn)序列為CBEFDGAJIKLH

3.假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為

0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0-7的

二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。

WPL1=2.61WPL2=3方案1優(yōu)于方案2

5.設(shè)一棵樹(shù)T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,

G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化

成對(duì)應(yīng)的二叉樹(shù)。

6.請(qǐng)畫(huà)出下面二叉樹(shù)的順序存儲(chǔ)表示。

012345678910111213

ABDCEF

7.請(qǐng)畫(huà)出上題所示樹(shù)的二叉鏈表存儲(chǔ)表示。

8.線(xiàn)索結(jié)點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)是什么？

9.樹(shù)的三種存儲(chǔ)結(jié)構(gòu)分別是：雙親表示法、孩子鏈表表示法和孩子-兄弟表示法。

10.樹(shù)的遍歷有哪三種方式：先根遍歷、后根遍歷和按層次遍歷。

11.森林的遍歷有哪兩種方式：先序遍歷和中序遍歷。

第七章圖

第6頁(yè)，共9頁(yè)

復(fù)習(xí)要求：掌握?qǐng)D的有關(guān)概念、存儲(chǔ)結(jié)構(gòu)、遍歷算法、生成樹(shù)的求法以及拓?fù)渑判虻母拍罴?/p>

求法。

復(fù)習(xí)內(nèi)容：

(1)圖的定義和術(shù)語(yǔ)

(2)圖的存儲(chǔ)結(jié)構(gòu)

(3)圖的遍歷

(4)圖的連通性問(wèn)題

(5)有向無(wú)回圖及其應(yīng)用

(6)最短路徑

復(fù)習(xí)題：

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

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

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

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

3.已知如右圖所示的有向圖，請(qǐng)給出該圖的

(1)每個(gè)頂點(diǎn)的入/出度；

(2)鄰接矩陣

(3)鄰接表

(4)逆鄰接表

(5)強(qiáng)連通分量

答案:

(3)鄰接表

A

2二--6THTF1

3

4二一0^01^50

5二一迎

6

第7頁(yè)，共9頁(yè)

(4)逆鄰接表

(5)有3個(gè)強(qiáng)連通分量

4.簡(jiǎn)述圖的各種存儲(chǔ)結(jié)構(gòu)的適用類(lèi)型？

答：

鄰接矩陣：有向圖和無(wú)向圖

鄰接表(逆鄰接表)：有向圖和無(wú)向圖

十字鏈表：有向圖

鄰接多重表：無(wú)向圖

5