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

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)總結(jié)《數(shù)據(jù)結(jié)構(gòu)》期末考試題型及分值

（1）簡(jiǎn)答題6題*5分=30分簡(jiǎn)要回答要點(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）表示=存儲(chǔ)結(jié)構(gòu)體實(shí)現(xiàn)=算法（基本操作）算法分析=時(shí)光、空間復(fù)雜度}

考試概念有：1.數(shù)據(jù)結(jié)構(gòu){一、線性表（棧-隊(duì)-列-串-數(shù)組-廣義表-規(guī)律結(jié)構(gòu)-存儲(chǔ)結(jié)構(gòu)-運(yùn)算結(jié)構(gòu)）

二、非線性表（集合-樹(shù)-圖）}

2.抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象-數(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

簡(jiǎn)答題實(shí)例

（1）

（2）

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

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

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

data605078903440

next

357204

1

線性表為：（78，50，40，60，34，90）???????

??

???????01

1

1

1010111011101010111

2.請(qǐng)畫(huà)出下圖的鄰接矩陣和鄰接表。

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

用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。

用克魯斯卡爾算法得到的最小生成樹(shù)為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

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

圖12

圖11

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

1.LinkListmynote(LinkListL)

{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(LABC(BT->right);coutdatadata){

item=BST->data;//查找勝利

return__true__;}

elseif(itemdata)

returnFind(___BST->left__,item);

elsereturnFind(____BST->right__,item);

}//if

}

六、編寫(xiě)算法（共8分）

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

intCountX(LNode*HL,ElemTypex)

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)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(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)的兩個(gè)指針域分離為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í)的比較次數(shù)并計(jì)算出查找勝利時(shí)的平均查找長(zhǎng)度。

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

4．設(shè)一棵樹(shù)T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。

樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略

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

集合。

E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

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

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

1．設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)光復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。

設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)光復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。

voidquickpass(intr[],ints,intt)

{

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

while(inext)

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

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

}

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

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

1.已知二叉樹(shù)的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫(huà)出此二叉樹(shù)，并畫(huà)出它的后序線索二叉樹(shù)。

A

E

B

F

G

C

D

H

FK

J

NULL

2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生矛盾采納線性探查法處理，試：H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….矛盾

H(15)=15mod7=1;….矛盾H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;

H(22)=22mod7=1;….矛盾

（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫(xiě)出散列表：

`0123456

63

36

15

22

40

（2）求出在查找每一個(gè)元素概率相等狀況下的平均查找長(zhǎng)度。ASL=

6.15

3

1121=++++

3．已知序列（10，18，4，3，6，12，1，9，18，8）請(qǐng)用迅速排序?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,181,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)

{

lklist*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ì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){

if(bt!=0return;}

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

voidparent(bitree*bt,charx){

inti;

preorder(bt,x);

for(i=f+1;ilchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");

elseif(idata);elseprintf("notparent");}

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

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

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

>>>>>11

11

1

11

11^

^^

^00^000e

a

b

c

d

LS

2、下圖所示的森林：

(1)求樹(shù)（a）的先根序列和后根序列；

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

A

GB

C

D

E

FH

I

J

K

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

ABCDEF;BDEFCA；

（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；

A

BC

DEF

G

H

IJK

(a)(b)

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

A

G

B

C

D

E

FH

I

J

K

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

表處理矛盾，請(qǐng)畫(huà)出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。

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

0123456789

45

369

8

27

^

^

^^

^

^

^

^

^

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

1．設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。

設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voidsplit(lklist*head,lklist*ha=0,hb=0,hc=0;

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

{

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

if(p->data>='A'ha=p;}

elseif(p->data>='0'hb=p;}else{p->next=hc;hc=p;}

}

}

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

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

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

voidswapbitree(bitree*bt)

{

bitree*p;

if(bt==0)return;

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

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

}

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

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

#definen10

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

voidbstinsert(bitree*bt->key=key;bt->lchild=bt->rchild=0;}

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

}

voidcreatebsttree(bitree*

for(i=1;idata!=bt2->data)return(0);

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

}

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

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

voidmergelklist(lklist*ha,lklist*hb,lklist*

while(ha!=0else{s->next=ha;s=ha;};ha=ha->next;}

else{if(s==0)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ì)題(20分)

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

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

structrecord{intkey;intothers;};

intbisearch(structrecordr[],intk)

{

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

while(lownext==0)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*intmin,t;

if(head==0||head->next==0)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ì)在挨次存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。

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

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

{

longi,j,length=strlen(s);

if(startlength)printf("Thecopypositioniswrong");

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

else{for(i=start-1,j=0;ikey==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}

}

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

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

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

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

voidcountnode(bitree*bt,intcountnode(bt->lchild,count);countnode(bt->rchild,count);}

}

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

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

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

typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;

typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;

voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[])

{

inti,j;glinklistnode*p;

for(i=0;iadjvertex=j;

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

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

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

}

}

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

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

1．設(shè)計(jì)計(jì)算二叉樹(shù)中全部結(jié)點(diǎn)值之和的算法。

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

voidsum(bitree*bt,intsum(bt->lchild,s);sum(bt->rchild,s);}}

2．設(shè)計(jì)將全部奇數(shù)移到全部偶數(shù)之前的算法。

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

voidquickpass(intr[],ints,intt)

{

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

while(inext==0)return(1);else

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

return(1);

}

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

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

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

voidmergelklist(lklist*ha,lklist*hb,lklist*

while(ha!=0else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}

2．設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。bitree*bstsearch1(bitree*t,intkey){

bitree*p=t;

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

return(0);}

3．設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)

整為堆。

設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)節(jié)為堆。

voidadjustheap(intr[],intn){

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

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

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

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

1.線性表為：（78，50，40，60，34，90）

2.鄰接矩陣：?????????

???????01

1

1

10101110111010101110

鄰接表如圖11所示：

圖11

3.用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

4.見(jiàn)圖12

圖12

四、讀算法（每題7分，共14分）1.（1）查詢鏈表的尾結(jié)點(diǎn)

（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)（3）返回的線性表為（a2,a3,…,an,a1）2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。五、法填空（每空2分，共8分）

trueBST->leftBST->right六、編寫(xiě)算法（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)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX

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

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

1.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)

間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){

inti=s,j=t,x=r[s];while(inext)

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

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

}

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

三、計(jì)算題1．

A

E

B

F

G

C

D

H

FK

J

NULL

2、H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….矛盾

H(15)=15mod7=1;….矛盾H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;

H(22)=22mod7=1;….矛盾

（1）0123456

63

36

15

22

40

（2）ASL=

6.15

3

1121=++++

3、(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,181,3,4,6,8,9,10,12,18,18

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

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

typedefintdatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*

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ì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){

if(bt!=0return;}

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

voidparent(bitree*bt,charx){

inti;

preorder(bt,x);

for(i=f+1;ilchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");

elseif(idata);elseprintf("notparent");}

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

三、計(jì)算題1．1

>>>>>11

11

1

11

11^

^^

^00^000e

a

b

c

d

LS

2．

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

A

G

B

C

D

E

FH

I

J

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

0123456789

45

369

8

27

^

^

^^

^

^

^

^

^

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

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

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

typedefchardatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voidsplit(lklist*head,lklist*ha=0,hb=0,hc=0;

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

{

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

if(p->data>='A'ha=p;}

elseif(p->data>='0'hb=p;}else{p->next=hc;hc=p;}

}

}

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

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

voidswapbitree(bitree*bt)

{

bitree*p;

if(bt==0)return;

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

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

}

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

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

voidbstinsert(bitree*bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);

}

voidcreatebsttree(bitree*

for(i=1;idata!=bt2->data)return(0);

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

}

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

voidmergelklist(lklist*ha,lklist*hb,lklist*

while(ha!=0else{s->next=ha;s=ha;};ha=ha->next;}

else{if(s==0)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-1;

while(lowk)high=mid-1;elselow=mid+1;

}

}

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

intminnum=-32768,flag=1;

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

voidinorder(bitree*bt)

{

if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}

}

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

voidstraightinsertsort(lklist*intt;

if(head==0||head->next==0)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*intmin,t;

if(head==0||head->next==0)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ì)在挨次存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。

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

{

longi,j,length=strlen(s);

if(startlength)printf("Thecopypositioniswrong");

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

else{for(i=start-1,j=0;ikey==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}

}

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

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

1.設(shè)計(jì)一個(gè)在鏈?zhǔn)?/p>