數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)

《數(shù)據(jù)結(jié)構(gòu)》期末考試題型及分值

（1）簡答題6題*5分=30分簡要回答要點(diǎn)

（2）分析題6題*5分=30分給出結(jié)果

（3）設(shè)計(jì)題1題*10分=10分設(shè)計(jì)思想及結(jié)果

（4）編程題1題*10分=10分完整代碼

（5）綜合題1題*20分=20分抽象數(shù)據(jù)類型的定義、表示、實(shí)現(xiàn)、算法分析

｛定義=功能（ADT）表示=存儲結(jié)構(gòu)體實(shí)現(xiàn)=算法（基本操作）算法分析=時間、

空間復(fù)雜度｝

考試概念有：1.數(shù)據(jù)結(jié)構(gòu)｛一、線性表（棧-隊(duì)-列-串-數(shù)組-廣義表-邏輯結(jié)構(gòu)-存儲

結(jié)構(gòu)-運(yùn)算結(jié)構(gòu)）

二、非線性表（集合-樹-圖）｝

2.抽象數(shù)據(jù)類型數(shù)據(jù)對象-數(shù)據(jù)關(guān)系-基本操作

3.算法性質(zhì)-要求（設(shè)計(jì)人效率（度量）

4.實(shí)例查找：高效查找算法

排序：高效的排序算法

分析題考試題目參考

(1)1-2-3-4-5-6順序建BBST

(2)6-5-4-3-2-1順序建BBST

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

一、填空題

1.1據(jù)結(jié)構(gòu)是一門研究非數(shù)非計(jì)算的程序設(shè)計(jì)問題中計(jì)中機(jī)的螺作對象以及它們之間的關(guān)丁

和運(yùn)算等的學(xué)科.

2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D.R）,其中D是被犯兀索的有限集R是D上的關(guān)系有限集

合.

3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的小羯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個方面的內(nèi)容。

4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和耳線性結(jié)構(gòu)-

5.線性結(jié)構(gòu)中元素之間存在二雙二關(guān)系，樹形結(jié)構(gòu)中元素之向存在二對芟關(guān)系，圖形結(jié)構(gòu)中元素之間存在

多對多關(guān)系。

6.在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)」LfcJV驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn);最后一個結(jié)點(diǎn)3

宜_屈續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn).

2

7.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),其余每個結(jié)點(diǎn)有且只有個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有

后續(xù)結(jié)點(diǎn),其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個.

8.在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個.

9.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序.鏈?zhǔn)健⑺饕痛媪?

10.數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除.修改、查找、排序.

11.一個尊法的效率可分為時間效率和空間效率.

12.在順序表中插入或刪除一個元素，需要平均移動表中一半元素,具體移動的元素個數(shù)與表長和該元

素在表中的的位有關(guān).

13.線性表中結(jié)點(diǎn)的集合是有限的,結(jié)點(diǎn)間的關(guān)系是一對一的。

14.向一個長度為n的向量的第i個元素UWi與n+1)之前插入一個元素時，需向后移動mi+1個元素。

15.向一個長度為n的向景中刪除第i個元素(IWiWn)時，需向前移動n-i個元素.

簡答題實(shí)例

2.簡述順序表和進(jìn)衣存儲方式的特點(diǎn).

答：順序表的優(yōu)點(diǎn)是可以隨機(jī)訪問數(shù)據(jù)元素,缺點(diǎn)是大小固定.不利增減結(jié)點(diǎn)(增減結(jié)點(diǎn)

操作需要移動元素屋鏈表的優(yōu)點(diǎn)是乘用指針方式增減結(jié)點(diǎn)，非常方便(只需改變指針指向.

不移動結(jié)點(diǎn))。其缺點(diǎn)是不能進(jìn)行隨機(jī)訪問,只能順序訪問。另外，每個結(jié)點(diǎn)上增加指針域,

造出額外存儲空間增大.

頭結(jié)點(diǎn)的作用出

［空表與非空表處理?樣

3.時鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？(至少說出兩條好處)

2.結(jié)點(diǎn)之附操作更方便。

答：其好處行:

(1)對帶頭結(jié)點(diǎn)的鏈表.隹表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都

是修改前一個結(jié)點(diǎn)的指針域，因?yàn)槿魏卧亟Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)(若鏈表沒有頭結(jié)點(diǎn)，則首元

素結(jié)點(diǎn)沒有前驅(qū)結(jié)京.在其前插入結(jié)點(diǎn)和刪除以給力:時操作復(fù)雜些)。

(2)對帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針,因此空表與非空表的處理是

一樣的。

設(shè)計(jì)題：

(1)

3

1.設(shè)計(jì)計(jì)算二義樹中所行結(jié)點(diǎn)值之和的兌法。

voidsum(bitree*bt.uit&s)

(

if(bt!=O){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}

)

(2)

設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。

voidsunpleselectsorlklist(lklist*&head)

(

Iklist*p.*q.*s;intmm.t;

if(head=O|head->iiext==O)retunii

fbr(q=head:q!=0:q=q->next)

(

iiiiii=q->data:s=q:

fbr(p=q->next:p!=01p=p->next)if(iiiiii>p->data){mm=p->data:s=p:}

if(s!=q){t=s->datais->data=q->data:q->data=t:}

)

)

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

三、計(jì)算題(每題6分，共24分)

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

A01234567

605078903440

3572041

()1110

10101

11011

10101

線性表為：為8,50,40,60,34,90)L01110J

2.請畫出下圖的鄰接矩陣和鄰接表。

3.已知一個圖的頂點(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,

4

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

用兄魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

四、閱讀算法(每題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；

)

請回答下列問題：

⑴說明語句S1的功能；

查詢鏈表的尾結(jié)點(diǎn)

(2)說明語句組S2的功能；

鬟第一個結(jié)型接到疊蓑的尾部，作為新的尾結(jié)占

⑶設(shè)鏈表表小的線性表為⑶如，…,a”)，寫出執(zhí)行后的返回值所表示的線

I土/<O

返回的線性表為(a?辿，二W型L

2.voidABC(B亍Node*BT)

(

ifBT{

ABC(BT->left);

ABC(BT->right);

cout?BT->data?''；

)

5

該算法的功能是：

遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?/p>

五、算法填空(共8分)

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

boolFind(BTreeNode*BST,ElemType&item)

(

if(BST=NULL)

returnfalse;〃查找失敗

else{

if(item==BST->data){

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

returntrue:)

elseif(item<BST->data)

returnFind(BST->left,item);

elsereturnFind(BST->right,item);

}//if

)

六、編寫算法(共8分)

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

intCountX(LNode*HL,ElemTypex)

intCoimtX(LNode*HL,ElemTypex)

(inti=0;LNodQp=HL;〃i為計(jì)數(shù)器

while(p!=NULL)

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

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

_______returni;

}〃CountX

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

三、應(yīng)用題(36分)

1.設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇

排序和第4趟直接插入排序后的結(jié)果。

(22,40,45,48,80,78),(40,45,48,80,22,78)

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

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

rlink)。

q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;

3.設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用

二分查找，要求計(jì)算出查找關(guān)鍵字62時的比較次數(shù)并計(jì)算出查找成功時的平均查找長

度。

2,ASL=91*l+2*2+3*4+4*2)=25/9

4.設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求

用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。

6

樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略

5.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的

E={(L3),(1,2),(3,5),(5,6),(6,4)}~j——1

6.設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給

出構(gòu)造過程。

四、算法設(shè)計(jì)題(16分)

1.設(shè)有一組初始記錄關(guān)鍵字序列(K,心，…，K,,),要求設(shè)計(jì)一個算法能夠在0(n)的時

間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于K,,右半部分

的每個關(guān)鍵字均大于等于K：。

設(shè)有一組初始記錄關(guān)鍵字序列(R,K2,K?),要求設(shè)計(jì)一個算法能夠在0(n)的時間復(fù)

雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于凡，右半部分的每個關(guān)

鍵字均大于等于

voidquickpass(intr[],ints,intt)

(

inti=s,j=t,x=r[s];

while(i<j){

while(i<j&&r[j]>x)j=j-l;if(i<j){r[i]=r[j];i=i+l;}

while(i<j&&r[i]<x)i=i+l;if(i<j){r[j]=r[ij;j=j-l;}

r[i]=x;

2.設(shè)有兩個集合A和集合B,要求設(shè)計(jì)生成集合C=AAB的算法，其中集合A、B和C用鏈

式存儲結(jié)構(gòu)表示。

設(shè)有兩個集合A和集合B,要求設(shè)計(jì)生成集合C=AnB的算法，其中集合A、B和C用鏈?zhǔn)?/p>

存儲結(jié)構(gòu)表示。

typedefstructnode{intdata;structnode*next;}lklist;

voidintersectiondklist*hajklist*hbjklist*&hc)

(

Iklist

for(p=ha,hc=0;p!=0;p=p->next)

{for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;

if(q!=O){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}

7

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

三、計(jì)算題(每題10分，共30分)

I.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫出

此二叉樹，并畫出它的后序線索二叉樹。

NULL<,

2.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為[0??6],假定

選用的散列函數(shù)是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：

H(36)=36mod7=1;Hi(22)=(l+1)mod7=2;???.沖突

H(15)=15mod7=1;…?沖突H2(22)=(2+l)mod7=3;

Hi(15)=(l+1)mod7=2;

H(40)=40mod7=5;

H(63)=63mod7=0;

H(22)=22mod7=1;????沖突

(1)計(jì)算出每?個元素的散列地址并在下圖中填寫出散列表:

(2)求出在查找每個元素概率相等情況下的平均查找長度。

3.已知序列(10,18,4,3,6,12,1,9,18,8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。

(8,9,4,3,6,1),10,(12,18,18)

(1,6,4,3),8,(9),10,12,(18,18)

1,(3,4,6),8,9,10,12,18,(18)

1,3,(4,6),8,9,10,12,18,18

1,3,4,6,8,9,10,12,18,18

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

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

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

typedefintdatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voiddelredundant(lklist*&head)

8

iklist*p,*q,*s;

for(p=head;p!=0;p=p->next)

for(q=p->next,s=q;q!=0;)

if(q->data==p->data){s->next=q->next;free(q);q=s->next;}

else{s=q,q=q->next;}

)

}

2.設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。

設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

bitree*q[20];intr=0,f=0,flag=0;

voidpreorder(bitree*bt,charx)

(

if(bt!=O&&flag==0)

if(bt->data==x){flag=l;return;}

else{r=(r+l)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}

)

voidparent(bltree*bt,charx)

(

inti;

preorder(bt,x);

for(i=f+l;i<=r;i++)if(q[i]->lchild->data==xIIq[i]->rchild->data)break;

if(flag==O)printf(Mnotfoundx\nn);

elseif(i<=r)printf(M%c'\bt->data);elseprintf(Mnotparent'*);

)

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

三、計(jì)算題(每題10分，共30分)

1、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。

2、下圖所示的森林：

(1)求樹(a)的先根序列和后根序列;

(l)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹;

9

(2)求森林先序序列和中序序列;

ABCDEF;BDEFCA；

(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;

(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹;

3、設(shè)散列表的地址范圍是[0..9],散列函數(shù)為H(key)=(key2+2)MOD9,并采用鏈

表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。

H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

10

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

1.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈

表中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。

設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表

中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voidsplit(lklist*headjklist*&ha,lklist*&hb,lklist*&hc)

(

Iklist*p;ha=0,hb=0,hc=0;

for(p=head;p!=0;p=head)

(

head=p->next;p->next=0;

if(p->data>='A,&&p->data<='Zr){p->nexl=ha;ha=p;)

elseif(p->data>='Or&&p->data<=9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}

)

)

2.設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。

設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。

typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;

voidswapbitree(bitree*bt)

(

bilree*p;

if(bt==O)return;

swapbitree(bt->lchild);swapbitree(bt->rchild);

p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;

)

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立?棵二叉排序樹。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。

#definen10

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidbstinsert(bitree*&bt,intkey)

(

if(bt==O){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=O;}

elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild?key);

)

voidcreatebsttree(bitree*&bt)

(

inti;

for(i=l;i<=n;i++)bstinsert(bt,random(100));

11

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

三、應(yīng)用題(32分)

1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,

要求給H1該二叉樹的的后序遍歷序列。

DEBCA

2.設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并

計(jì)算最小生成樹各邊上的權(quán)值之和。

E={(1,5),(5,2),(5,3),(3,4)},W=1O

3.設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計(jì)算出成功查找時

的平均查找長度。

ASL=(1*1+2*2+3*4)77=17/7

4.設(shè)散列表的長度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)鍵字序列為(25,31,8,27,

13,68),要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

ASL1=7/6,ASL2=4/3

四、算法設(shè)計(jì)題(28分)

1.設(shè)計(jì)判斷兩個二叉樹是否相同的算法。

設(shè)計(jì)判斷兩個二叉樹是否相同的算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

intjudgebitree(bitree*btl,bitree*bt2)

(

if(bt1==0&&bt2==0)return(1);

elseif(btl==OIIbt2==0llbt1->data!=bt2->data)return(O);

elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));

)

2.設(shè)計(jì)兩個有序單鏈表的合并排序算法。

設(shè)計(jì)兩個有序單鏈表的合并排序算法。

voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)

|

Iklist*s=hc=O;

while(ha!=0&&hb!=O)

if(ha->data<hb->data){if(s==O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}

else{if(s==O)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}

if(ha==O)s->next=hb;elses->next=ha;

)

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

四、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

12

structrecord{intkey;intothers;};

intbisearch(structrecordr[],intk)

intlow=0,mld,high=n-l;

while(low<=high)

(

mid=(low+high)/2;

if(r[midj.key==k)return(mid+l);elseif(r[mid].key>k)high=mid-l;else

low=mid+l;

)

return(O);

)

2.設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。

設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。

intminnum=-32768,flag=l;

typedefstructnode{intkey;structnode*lchild9*rchild;}bitree;

voidinorder(bitree*bt)

{

if(bt!=O){inorder(bt->lchild);if(minnum>bt->key)flag=O;

minnum=bt->key;inorder(bt->rchild);)

)

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法

在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法

voidstraightinscrtsort(lklist*&head)

(

Iklist*s,*p,*q;intt;

if(head==0IIhead->next==O)return;

elsefor(q=head,p=head->next;p!=0;p=q->next)

(

for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;

if(s==q->next)q=p;

else{q->next=p->next;p->next=s->next;s->next=p;

t=p->data;p->data=s->data;s->data=t;}

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

四、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。

設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。

voidsimpleselectsorlklist(lklist*&head)

(

Iklist*p,*q,*s;intmin,t；

if(head==0llhead->next==0)return;

13

for(q=head;q!=O;q=q->next)

(

min=q->data;s=q;

for(p=q->next;p!=O;p=p->next)if(mln>p->data){min=p->data;s=p;}

if(s!=q){t=s->data;s->data=q->data;q->data=t;}

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

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

voidsubstring(chars[],longstart,longcount,chart[])

(

longij,length=strlen(s);

if(start<lIIstart>length)printf(uThecopypositioniswrong11);

elseif(start+count-l>length)printf(MToocharacterstobecopied'1);

else{for(i=start-lj=0;i<start+count-l;i++J++)t[jj=sli];t[jj=AO*;}

}

3.設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。

設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。

intlev=0;

typedefstructnode{intkey;structnode*lchild,*rchild;Jbitree;

voidlevel(bitree*bt,intx)

{

if(bt!=O)

{lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);else

level(bt->rchild,x);}

)

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

四、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個數(shù)的算法。

設(shè)計(jì)一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個數(shù)的算法。

voidcountnode(bitree*bt,int&count)

(

if(bt!=O)

{count++;countn(>de(bt->lchild9count);countnode(bt->rchild,count);}

)

2.設(shè)計(jì)一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。

設(shè)計(jì)一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。

typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;

typedefstructnodel{intinfo;intadjvertex;structnodel*nextarc;}glinklistnode;

typedefstructnode2{intvertexinfo;glinkllstnode*firstarc;}glinkheadnode;

voidadjmatrixtoadjlist(gadjmatrixgH],glinkheadnodeg2[])

14

intij;glinklistnode*p;

for(i=0;i<=n-l;i++)g2[i].firstarc=0;

for(i=0;i<=n-l;i++)for(j=0;j<=n-l;j++)

if(gl.edge[i](j]==l)

(

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;

p->nextarc=g[i].firstarc;g[ij.firstarc=p;

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;

p->nextarc=g[jj.firstarc;g|j].firstarc=p;

}

)

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

五、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。

設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。

voidsum(bitree*bt,int&s)

(

if(bt!=O){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}

)

2.設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。

設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。

voidquickpass(intr[],ints,intt)

(

inti=sj=t,x=r[s];

while(i<j)

{

while(i<j&&r[j]%2==0)j=j-l;if(i<j){r[i]=r[j];i=i+l;}

while(i<j&&r[i]%2==l)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

)

r[i]=x;

}

3.設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。

設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。

intisriselk(lklist*head)

(

if(head==0llliead->next==0)return(l);else

for(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(O);

return(l);

數(shù)據(jù)結(jié)構(gòu)試卷（十）

15

三、算法設(shè)計(jì)題(22分)

1.設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。

設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。

voidmergelklist(lklist*ha9lklist*hb9lklist*&hc)

(

iklist*s=hc=0;

while(ha!=0&&hb!=0)

if(ha->data<hb->data){if(s==O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}

else{if(s==O)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}

if(ha==0)s->next=hb;elses->next=ha;

2.設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。

設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。

bitree*bstsearchl(bitree*t,intkey)

(

bitrec*p=t;

while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;else

p=p->rchild;

return(O);

)

3.設(shè)關(guān)鍵字序列(k”k2,…，ke)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k“k2,k??X)調(diào)

整為堆。

設(shè)關(guān)鍵字序列(k“k2,…，kn-J是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k|,k2,kz,X)調(diào)

整為堆。

voidadjustheap(intr[],intn)

(

intj=n,i=j/2,temp=r[j-l];

while(i>=l)if(temp>=r[i-l])break;else{r[j-l]=r[i-l];j=i;i=i/2;}

r[j-l]=temp;

數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案

三、計(jì)算題（每題6分，共24分）

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

01110

10101

11011

10101

2.鄰接矩陣:01110

鄰接表如圖11所示:

16

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

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

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

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

2.遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?/p>

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

trueBST->leftBST->right

六、編寫算法(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)時i中的值即為x結(jié)點(diǎn)個數(shù)

returni;

}//CountX

數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案

四、算法設(shè)計(jì)題

1.設(shè)有一組初始記錄關(guān)鍵字序列（絡(luò),

心，…，K,,）,要求設(shè)計(jì)一個算法能夠在o（n）的時

間復(fù)雜度內(nèi)將線性表劃分成兩部分，

其中左半部分的每個關(guān)鍵字均小于A,右半部分

的每個關(guān)鍵字均大于等于Kio

voidquickpass(intr[],ints,intt)

inti=s,j=t,x=r[s];

while(i<j){

while(i<j&&r(j]>x)j=j-l；if(j<j){r[i]=r[j];i=i+l；}

17

while(i<j&&r[i]<x)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

)

r[i]=x;

)

2.設(shè)有兩個集合A和集合B,要求設(shè)計(jì)生成集合C=ACB的算法，其中集合A、B和C用

鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。

typedefstructnode{intdata;structnode*next;}lklist;

voidintersection(lklist*ha,lklist*hb,lklist*&hc)

(

Iklist

for(p=ha,hc=0;p!=0;p=p->next)

{for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;

if(q!=O){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}

)

)

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

三、計(jì)算題

1.

2、H(36)=36mod7=1;Hi(22)=(l+1)mod7=2;....沖突

H(15)=15mod7=1;.…沖突H2(22)=(2+l)mod7=3;

Hi(15)=(l+l)mod7=2;

H(40)=40mod7=5;

H(63)=63mod7=0;

H(22)=22mod7=1;….沖突

(1)0123456

6336152240

1+2+1+1+3

(2)ASL==1.6

5

3、(8,9,4,3,6,1),10,(12,38)

(1,6,4,3),8,(9),10,12/18,18)

1,(3,4,6),8,9,10,12,18,(18)

13(4,6),8910,12,居18

1,3,4,6,8,9,10,12,18,18

18

四、算法設(shè)計(jì)題

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

typedefinidatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voiddelredundant(lklist*&head)

(

Iklist*p,*q,*s;

for(p=head;p!=0;p=p->next)

(

for(q=p->next,s=q;q!=0;)

if(q->data==p->data){s->next=q->next;free(q);q=s->next;}

else{s=q,q=q->next;}

)

)

2.設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

bitree*q[20];intr=O,f=O,flag=O;

voidpreorder(bitree*bt,charx)

(

if(bt!=O&&flag==0)

if(bt->data==x){ilag=l;return;}

else{r=(r+l)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}

)

voidparent(bitree*bt,charx)

(

inti;

preorder(bt,x);

for(i=f+l;i<=r;i++)if(q[i]->lchild->data==xIIq[i]->rchild->data)break;

if(flag==0)printf(nnotfoundx\nH);

elseif(i<=r)printf("%cH,bt->data);elseprintf("notparent");

)

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

三、計(jì)算題

1.

LS4I|八|

111AlA

|0|e|——>1—>

FoTbl[oT7|國

2.

19

(l)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹;

3.H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

0

1

2

3

二

4

5

6-^rr=hFn

7

8

9

四、算法設(shè)計(jì)題

i.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表

中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc)

(

Iklist*p;ha=0,hb=0,hc=0;

for(p=head;p!=0;p=head)

(

head=p->next;p->next=0;

if(p->data>='A,&&p->data<='Z,){p->next=ha;ha=p;}

elseif(p->data>=,0'&&p->data<=9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}

)

)

2.設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。

typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;

voidswapbitree(bitree*bt)

(

bitree*p;

if(bt==O)return;

swapbitree(bt->lchild);swapbitree(bt->rchild);

p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;

)

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。

20

#definen10

typedefstructnode{intkey;structnode*lchild,*rchild;Jbitree;

voidbstinsert(bitree*&bt,intkey)

(

if(bt==O){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=O;}

elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);

)

voidcreatebsttree(bitree*&bt)

(

inti;

for(i=l;i<=n;i++)bstinsert(bt,random(100));

)

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

四、算法設(shè)計(jì)題

1.設(shè)計(jì)判斷兩個二叉樹是否相同的算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

intjudgebitree(bitree*btl,bitree*bt2)

(

if(btl==O&&bt2==0)return(l);

elseif(btl==OIIbt2==0IIbt1->data!=bt2->data)return(O);

elseretum(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));

)

2.設(shè)計(jì)兩個有序單鏈表的合并排序算法。

voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)

(

Iklist*s=hc=0;

while(ha!=0&&hb!=O)

if(ha->data<hb->data){if(s==O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}

else{if(s==O)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}

if(ha==0)s->next=hb;elses->next=ha;

)

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

四、算法設(shè)計(jì)題

1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

structrecord{intkey;intothers;};

intbisearch(structrecordr[],intk)

(

intlow=0,mid,high=n-l;

while(low<=high)

(

mid=(low+high)/2;

if(r[mid].key==k)retum(mid+l);elseif(r[mid].key>k)high=mid-1;elselow=mid+l;

21

return(O);

2.設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。

intminnum=-32768,flag=l;

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidinorder(bitree*bt)

(

if(bt!=O){inorder(bt->lchild);if(minnum>bt->key)flag=O;

minnum=bt->key;inorder(bt->rchild);}

)

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法

voidstraightinsertsort(lklist*&head)

(

Iklist*s,*p,*q;intt;

if(head==0IIhead->next==O)return;

elsefor(q=head,p=head->next;p!=0;p=q->next)

(

for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;

if(s==q->next)q=p;

else{q->next=p->next;p->next=s->next;s->next=p;

t=p->data;p->data=s->data;s->data=t;}

)

)

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

四、算法設(shè)計(jì)題

1.設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法。

voidsimpleselectsorlklist(lklist*&head)

(

Iklist*p,*q,*s;intmin,t;

if(head==0llhead->next==O)return;

for(q=head;q!=0;q=q->next)

(

min=q->data;s=q;

for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}

if(s!=q){t=s->data;s->data=q->data;q->data=t;}

}

}

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

voidsubstring(chars[J,longstart,longcount,charJ)

(

longi,j,length=strlen(s);

if(start<lIIstart>length)printf("Thecopypositioniswrong");

elseif(start+count-1>length)printf("Toocharacterstobecopied'1);

22

else{for(i=start-l,j=0;i<start+count-1;i++,j++)t[j]=s[i];t|j]=W;}

3.設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。