數(shù)據(jù)結構復習資料2015-數(shù)據(jù)結構資料文檔_第1頁
數(shù)據(jù)結構復習資料2015-數(shù)據(jù)結構資料文檔_第2頁
數(shù)據(jù)結構復習資料2015-數(shù)據(jù)結構資料文檔_第3頁
數(shù)據(jù)結構復習資料2015-數(shù)據(jù)結構資料文檔_第4頁
數(shù)據(jù)結構復習資料2015-數(shù)據(jù)結構資料文檔_第5頁
已閱讀5頁,還剩4頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

數(shù)據(jù)結構復習

第一章緒論

復習內容:

(1)基本概念和術語

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

(3)估算算法時間復雜度

復習題:

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

為自然數(shù)且分母不為零的分數(shù))。

ADTRational_Num{

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

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

基本操作:

InitRational_Num(&T,vl,v2)

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

DestroyRationalNum(&T)

操作結果:有理數(shù)T被銷毀。

Get(T,i,&e)

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

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

Put(&T,i,e)

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

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

AddRational_Num(T1,T2,&T3)

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

操作結果:有理數(shù)Tl、T2相加,結果存入有理數(shù)T3。

SubRational_Num(Tl,T2,&T3)

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

操作結果:有理數(shù)Tl、T2相減,結果存入有理數(shù)T3。

Mu1Rational_Num(Tl,T2,&T3)

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

操作結果:有理數(shù)Tl、T2相乘,結果存入有理數(shù)T3。

DivRational_Num(Tl,T2,&T3)

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

操作結果:有理數(shù)Tl、T2相除,結果存入有理數(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.試寫一算法,自大至小依次輸出順序讀入的三個整數(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

第二章」線性表

復習內容:

(1)線性表的類型和定義

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

(3)線性表的鏈式存儲和實現(xiàn)

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

線性表--順序存儲結構--順序表

線性表--鏈式存儲結構---鏈表

線性表在順序存儲結構上實現(xiàn)查找、插入和刪除的算法

區(qū)分線性表的邏輯結構和存儲結構

復習題:

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

個數(shù)與【表長和該元素在表中的位置】有關。

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

理位置【不一定】緊鄰。

2.例2-1假設:有兩個集合A和B分別用兩個線性表LA和LB表示,即:線性表中的

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

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

順序表-優(yōu)點:①邏輯相鄰,物理相鄰②可隨機存取任一元素③存儲空間使用緊湊。缺點:

①插入、刪除操作需要移動大量的元素②預先分配空間需按最大空間分配,利用不充分③表

容量難以擴充。

單鏈表-優(yōu)點①它是一種動態(tài)結構,整個存儲空間為多個鏈表共用②不需預先分配空間③插

入、刪除操作方便。①單鏈表的缺點②指針占用額外存儲空間③不能隨機存取,查找速度慢。

4.寫出按正位序建立一個單鏈表的算法。

voidCreateList_L(LinkList&L,intn)

(

//正序輸入n個數(shù)據(jù)元素,建立帶頭結點的單鏈表

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

L->next=NULL;//先建立一個帶頭結點的單鏈表

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是帶裝頭結點的非空單鏈表,且P結點既不是首元結點,也不是尾元結點,試從下

列提供的答案中選擇合適的語句序列。

(1)刪除P結點的語句序列是【JLGCN】。

(2)刪除尾元結點的語句序列是【IKCN】。

第2頁,共9頁

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.指出以下算法中的錯誤和低效(即費時)之處,并將它改寫為一個既正確又高效的算法。

StatusDeletK(SqList&La,intI,intk)

{〃本過程從順序存儲結構的線性表La中刪除第i個元素起

〃的k個元素

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

//參數(shù)不合法

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

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

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

La.length-;}

returnok;

}//DeleteK

第二個for語句中,元素前移的次序錯誤;

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

改正后的算法:

StatusDeletK(SqList&La,intI,intk)

{〃本過程從順序存儲結構的線性表La中刪除第i個元素起

//的k個元素

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.設指針變量p指向雙向鏈表中結點A,指針變量q指向被插入結點B,要求給

出在結點A的后面插入結點B的操作序列(設雙向鏈表中結點的兩個指針域分

別為prior和next)o

pfnextfprior=q;

qfnext=pfnext;

q->prior=p;

p->next=q;

8.設計在單鏈表中刪除值相同的多余結點的算法。

第三章棧和隊列

復習內容:

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

第3頁,共9頁

(2)棧的應用

(3)隊列的定義及實現(xiàn)

(4)隊列的應用

復習題:

1.棧和隊列的共同特點是(A)0

A.只允許在端點處插入和刪除元素

B.都是先進后出

C.都是先進先出

D.沒有共同點

2.利用棧的結構對列車車廂進行調度則①如果進站的車廂序列為123,則可能得到的出站

車廂序列是什么?[123,132,213,231,321]②如果進站的車廂序列為123456,則能否得到

435612和135426的出站序列,并請說明為什么不能得到或者如何得到(即寫出以'S'表

示進棧和以'X'表示出棧的棧操作序列)。【可以得到135426,不可能得到435612,因為

‘4356'出棧說明12己在棧中,則1不可能在2之前出棧。】

3.寫出檢驗括號匹配的算法。(見作業(yè))

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

和內含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件。

判斷循環(huán)隊列的隊滿:

1.另外設一個標志位以區(qū)別隊空、隊滿

2.少用一個元素空間:

隊空:front==rear隊滿:(rear+l)%M==front

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

5.設順序循環(huán)隊列Q[0:MT]的頭指針和尾指針分別為F和R,頭指針F總是指

向隊頭元素的前一位置,尾指針R總是指向隊尾元素的當前位置,則該循環(huán)隊列

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

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

第四章串

復習內容:

(1)串類型的定義;

(2)串的三種存儲表示:定長順序結構、塊鏈存儲結構和堆分配存儲結構;

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

復習題:

1.設計在順序存儲結構上實現(xiàn)求子串算法。

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

//用Sub返回串S的第pos個字符起長度為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頁,共9頁

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

請問: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ù)組和廣義表

復習內容:

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

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

(3)矩陣的壓縮存儲

(4)廣義表的定義

(5)廣義表的存儲結構

復習題:

1.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。

2.稀疏矩陣的壓縮存儲方法:【三元組順序表,行邏輯鏈接的順序表,十字鏈表】

3.設有一個10階的下三角矩陣A(包括對角線),按照從上到下、從左到右的

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

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

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

4.

三角矩陣

an00........0

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

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

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

按行序為主序:

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.描述采用三元組表存儲表示,求稀疏矩陣M的轉置矩陣T的快速轉置算法。

6.畫出下面矩陣的十字鏈表。

3005

0-100

2000

答:

M.chead

第5頁,共9頁

第六章樹和二叉樹

復習要求:掌握樹和二叉樹的概念、存儲結構,基本運算及其遍歷,掌握哈夫曼樹的概念和

構造方法。

復習內容:

(1)樹的定義和基本術語

(2)二叉樹

(3)遍歷二叉樹和線索二叉樹

(4)樹和森林

(5)哈夫曼樹及其應用

復習題:

1.畫出和下列已知序列對應的樹T

樹的先根次序訪問序列為GFKDAIEBCHJ

樹的后根次序訪問序列為DIAEKFCJHBG

2.畫出和下列己知序列對應的森林F

森林的先序訪問序列為ABCDEFGHIJKL

森林的中序訪問序列為CBEFDGAJIKLH

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

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

二進制表示形式是另一種編碼方案。對于上述實例,比較兩種方案的優(yōu)缺點。

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

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

G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結構并將該樹轉化

成對應的二叉樹。

6.請畫出下面二叉樹的順序存儲表示。

012345678910111213

ABDCEF

7.請畫出上題所示樹的二叉鏈表存儲表示。

8.線索結點的結點結構是什么?

9.樹的三種存儲結構分別是:雙親表示法、孩子鏈表表示法和孩子-兄弟表示法。

10.樹的遍歷有哪三種方式:先根遍歷、后根遍歷和按層次遍歷。

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

第七章圖

第6頁,共9頁

復習要求:掌握圖的有關概念、存儲結構、遍歷算法、生成樹的求法以及拓撲排序的概念及

求法。

復習內容:

(1)圖的定義和術語

(2)圖的存儲結構

(3)圖的遍歷

(4)圖的連通性問題

(5)有向無回圖及其應用

(6)最短路徑

復習題:

1.對于一個具有n個頂點和e條邊的有向圖和無向圖,在其對應的鄰接表中,

所含邊結點分別有e個和2e個。

2.設有6個結點的無向圖,該圖至少應有(A)條邊才能確保是一個連通圖。

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

3.已知如右圖所示的有向圖,請給出該圖的

(1)每個頂點的入/出度;

(2)鄰接矩陣

(3)鄰接表

(4)逆鄰接表

(5)強連通分量

答案:

(3)鄰接表

A

2二--6THTF1

3

4二一0^01^50

5二一迎

6

第7頁,共9頁

(4)逆鄰接表

(5)有3個強連通分量

4.簡述圖的各種存儲結構的適用類型?

答:

鄰接矩陣:有向圖和無向圖

鄰接表(逆鄰接表):有向圖和無向圖

十字鏈表:有向圖

鄰接多重表:無向圖

5

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論