《數(shù)據(jù)結(jié)構(gòu)與實訓(xùn)（張新顏 第4版） 》習(xí)題參考答案 第1-8章

第一章

1.填空題

(1)在計算機(jī)中的存儲映像(是邏輯結(jié)構(gòu)在計算機(jī)中的實現(xiàn)或存儲表示)數(shù)據(jù)元素的表

示元素之間關(guān)系的表示數(shù)據(jù)元素。

(2)一對一一對多多對多

(3)時、空效率指人對算法閱讀理解的難易程度對于非法的輸入數(shù)據(jù)，算法能給

出相應(yīng)的響應(yīng)，而不是產(chǎn)生不可預(yù)料的后果。

(4)軟硬件環(huán)境問題規(guī)模的

(5)最壞

(6)O(n4)O(n2)

(7)時間復(fù)雜度

”(1+〃)

(8)n2o(n2)

(9)指針

2.判斷題

(1)X(2)X(3)V(4)J(5)V(6)J(7)X(8)X(9)X(10)X(11)X

3.簡答題

(1)略(見教材第3頁的1.2數(shù)據(jù)結(jié)構(gòu)的基本概念)

(2)(a)n-1,O(n)(b)n-1O(n)

(c)ll*n+l,O(n)(n為初始值100)

(d)［五」，o(冊)(e)n,

O(n)

第二章線性表

1,填空題

(1)address+m*i

(2)順序順序順序鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?/p>

(3)亦相鄰不一定

(4)0n

(5)OWiWla的長度WjWlb的長度-1OWkWlc的長度-1

(6)2插入的位置，元素個數(shù)n(順序表長度n)

(7)p的前驅(qū)O(n)

(8)p的前驅(qū)O(n)

(9)p-*next二pfnext—next

(10)head->next==Nullhead==Nullhead—next==headhead二二Null

(11)head-*next=head-*next-*nexthead=head-*next

2.判斷題

(1)X(2)V(3)X(4)X(5)X(6)X(7)V(8)X(9)X(10)X

3.選擇題

(1)A(2)A(3)A(4)D

4.簡答題

(1)

單向循環(huán)鏈表雙向循環(huán)鏈表

存儲密度高低

查找后繼的時間復(fù)雜度0(1)0(1)

查找前驅(qū)的時間復(fù)雜度0(n)0(1)

(2)在帶頭結(jié)點(diǎn)的單鏈表上，查找指針p所指結(jié)點(diǎn)的前驅(qū)。

(3)交換指針p與指針q所指結(jié)點(diǎn)的值。

5.算法設(shè)計題

(1)

voidreverse(SeqList1)

{for(i=0;i<=(l.listlength-l)/2;i++)

l.elem[i]<一>l.elem[Llistlength-1-i];

)

(2)

voiddelete(SeqList1,inti,intk)

/*從順序表中刪除自第i個元素開始的k個元素*/

{if(i<0||i>l.listlength-l||k<0)

{printf(wErrorM);

return;

)

if(i+k<=Llistlength)/*表中從i個元素起到最后一個元素有k個元素*/

{for(j=i+k;j<l.listlength;j++)

Lelem[j-k]=l.elemfj];

Llistlengt=l.listlength-k;

)

else/*表中從i個元素起直到最后一個元素不足k個元素*/

Llistlength=i;

)

(3)

voidinsert(LinkListh,ElementTypex)

/*將x插入到遞增鏈表h中，插入后的鏈表有序性不變*/

{if(h~*nex仁二Null)/*空表時*/

{q=(linklist)malloc(sizeof(ListNode));

q—next二Null;

q->data=x;

h—next=q;

)

pl=h_*next;p2=h;

while(pl-next!=Null&&pl->data<x)

{p2=pl；

pl=pl-*-next;

)

if(pl-*next==Null&&pl-*data<x)

{q=(linklist)malloc(sizeof(ListNode));

q->next=Null;

q-*data=x;

pl-next=q;

)

else/*(pl-*next==Null&&pl->data>=x)||(pl-*next!=Null&&pl-?data>=x)*/

{q=(LinkList)malloc(sizeof(ListNode);

q-*data=x;

p2->next=q;

q-*next=pl;

)

)

(4)

voiddelete(LinkListp)

/*在不帶頭結(jié)點(diǎn)且長度大于1的單向循環(huán)鏈表中，p指向某結(jié)點(diǎn)，刪除p的前驅(qū)結(jié)點(diǎn)*/

{ppp=p-*next;

while(ppp-*next->next!=p)

ppp=ppp—next;

/*刪除p的前驅(qū)結(jié)點(diǎn)*/

pp=ppp--next;

ppp-*next=pp->next;

free(pp);

)

(5)

voiddelete(LinkListh)

/*h為帶頭結(jié)點(diǎn)的，非降序排列的單鏈表的頭指針，刪除表中值相同的結(jié)點(diǎn)，使之只保留一

個*/

{p=h-*next;

if(!p)return;

x=pfdata;

while(pfnext)

if(x!=pfnextfdata)

{x=p-*next-*data;

p=pfnext

)

else

{q=p->next;

pfnext=pfnexLnext;

free(q);

voiddelete(LinkListh)

/*刪除帶頭結(jié)點(diǎn)的單鏈表h(指向頭結(jié)點(diǎn))中值為X的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)*/

{if(!(h~*next))return;

if(!(h-*next-*next))return;

p1=hfnexLnexl;

p2=h;

while(plfnext&&pl-*data!=x)

{pl=pl->next;

p2=p2-*next;

)

if(plfdata==x)

{q=p2—next;

p2->next=pl;

free(q);

)

)

(7)

Linklistsubtraction(LinkListla,LinkListlb)

/*la,lb分別為表示集合A,B的帶頭結(jié)點(diǎn)的單鏈表的頭指針，A-B由la鏈表返回*/

{if(!(]afnext))

return(la);

else

{pal=la-*next;

pa2=la;

)

if(!(lb->next))return(la);

while(pal)

{pb=lb-*next;

while(pb&&pal-*data!=pb-*data)

pb=pb->next;

if(pb)/*pal—data==pbfdata*/

{pa2->next=pal-^next;

free(pal);

pal=pa2fnext;

)

else

{pal=pal-*next;

pa2=pa2->next;

return(la);

(8)

LinkListintersection(LinkListla,LinkListlb)

/*la,lb,lc分別為表示集合A,B,C的帶頭結(jié)點(diǎn)的遞增有序的單鏈表的頭指針，C=ACB由1c鏈

表返回*/

{lc=(LinkList)malloc(sizeof(LinkNode));

lc-*next=null;

tail=lc;/*tail指向1c鏈的尾結(jié)點(diǎn)*/

if(!(la->next))

retum(lc);

else

pa=la-*nexl;

if(!(lb-next))return(lc);

while(pa)

{pb=lb-*next;

while(pb&&pa->data!=pb->data)

pb二pbfnext;

if(pb)insert(lc,tail,pa->data);

pa=pa—next;

)

return(lc);

)

voidinsert(LinkList1,LinkListtail,ElemenTypex)

/*將值X插入到單鏈表1的尾部*/

{p=(LinkList)malloc(sizeof(LinkNode))

pfdata=x;

p-*next=null;

tail->next=p;

tail=p;

1

SeqListintersection(SeqListla,SeqListlb)

/次集合A,B,C對應(yīng)的順序遞增表為la,lb,lc,C=AAB由1c表示*/

{lc.listlength=O;

if(la.listlength==O||lb.listlength==O)return(lc)

for(a=0;a<la.listlength;a++)

{for(b=0;b<lb.listlength&&lb.elem[b]!=la.elemfa];b++)

if(b<lb.listlength)

{lc.elem[lc.listlength]=la.elem[a];

lc.listlength++;

retuen(lc);

(9)

voiddelete(LinkListh,ElementTypeminElementTypemax)

/*h是帶頭結(jié)點(diǎn)的無序單鏈表的頭指針，刪除結(jié)點(diǎn)值大于min小于max的結(jié)點(diǎn)*/

{if(!(h-*next))return;

pl=hfnext;

p2=h;

while(pl)

if(plfdata>min&&pl-*data<max)

{p2->next=p1fnext;

free(pl);

pl=p2->next;

)

else

{pl=plfnext;

p2=p2fnext;

)

)

(10)

voidseparation(LinkListh,LinkList*phl,LinkList*ph2)

/*h為帶頭結(jié)點(diǎn)的單鏈表的頭指針，該表中含有兩類字符數(shù)據(jù)元素：字母與數(shù)字，拆分h為

兩條帶頭結(jié)點(diǎn)的單項循環(huán)鏈表*phl、*ph2,其中*phi鏈中存放字母，*ph2鏈中存放數(shù)字*/

{if(!(h-*next))return;

p=h-*next;

free(h);

*phl=(LinkList)malloc(sizeof(LinkNode));

(*phl)fnext=*phl;

*ph2=(LinkList)malloc(sizeof(LinkNode));

(*ph2)-*next=*ph2;

while(p)

{h=p;

p=p—next;

if(h-data〉='O'&&hfdata<='9')/*數(shù)字字符插入至U*ph2鏈*/

{h-*next=(*ph2)-*next;

(*ph2)fnext=h;

)

else/*字母字符插入到*phi鏈*/

{h"*next=(*ph1)-next;

(*phl)fnext二h;

(11)

intDelList(SeqList*L,intx,inty)

(

inti=O,k=O;

while(i<L->listlength)

if(L->elem[i]>=x&&L->elem[i]<=y)

{k++;i++;}

else

{L->elem[i-k]=L->elem[i];

i++；

)

L->listlength=L->listlength-k;

return(OK);

)

(12)

intDelList(SeqList*L)

(

inti=0,j=1;

while(j<=listlength-1)

if(L->elem[i]==L->elem[j])

{j++;}

else

{i++；

L->elem[i]=L->elem[j];

j++;

)

L->listlength=i+1;

return(OK);

)

第三章堆棧和隊列

1.填空題

(1)1,3,51

(2)push,pop,push,push,pop,push,pop,pop

（3）?？諚M

(4)0(1)0(1)

(5)=s.top-l=s.top+l

(6)s

(7)空

（8）棧底棧頂

（9）隊尾隊首（頭）

（10）是否為空是否為滿

(11)21

(12)front-*next==rear

(13)front==rear(rear+1)%MAX==frontrear+MAX-frort

2.判斷題

(1)V(2)X(3)V(4)V(5)X(6)J(7)V(8)X(9)V(10)V

3.選擇題

(1)C(2)C(3)C(4)D(5)C(6)B

4.簡答題

(1)當(dāng)進(jìn)行入隊操作時，隊尾指針的值已經(jīng)到達(dá)數(shù)組空間的最大下標(biāo)(MaxSize-l),而隊

首指針的值卻大于0,這時就產(chǎn)生了假溢出現(xiàn)象。

(2)使棧s中的元素順序置逆。

(3)借助于另一鏈棧t,使得鏈棧s去掉指定的元素e。

5.算法設(shè)計題

(1)

(

*5

$$3$3$3$3

(2)

對于輸入序列1,2,3,4,對應(yīng)的24種排列是：

1,2,3,41,2,4,31,3,2,41,3,4,214231,4,3,2

2,1,3,42』,4,32,3,1,42,3,4,12,41,32,4,3,1

3,1243,1423,2,1,43,2,4,1341,23,4,2,1

4,1234,L3,2421,3423,143,124,3,2,1

無下劃線的序列可以通過相應(yīng)的入、出棧得到?？梢酝ㄟ^入、出棧得到的輸出序列中的每一

個數(shù)，在它后面的比它小的數(shù)應(yīng)是降序排列的。

(3)

#defineMaxSize隊列可能達(dá)到的最大長度

typedefstruct

{ElementTypeelem[MaxSize];

intfront,count;/*隊首指示器,counl初值為0*/

}CirQueue;

voidAddQueue(CirQueue*Queue,ElementTypee)

/*入隊*/

{if(Queue->count==MaxSize)

{printf(“\noverflow^^);

return;

)

Queue->elem[(Queue->front+Queue->count)%MaxSize]二e;

Queue->count++;

)

ElementTypeDeleteQueue(CirQueue*Queue)

/*出隊*/

{if(Queue->counl==0)return(nil);

e=Queue->elem[Queue->front];

Queue->front=(Queue->front+1)%MaxSize;

Queue->count-;

return(e);

)

(4)

①A,D是合法的

②

intlegality(SeqList1)

/*入、出棧序列存放在l.elem口數(shù)組中，該序列合法返回1,否則返回0*/

{count=0;

for(i=0;i<l.listlength;i++)

if(l.elem[i]==,r

count++;

else

{count—;

if(count<0)return(O);/*?？諘r出棧*/

if(count==0)

return(l);

else

return(O);/*棧不空(沒有回到初始狀態(tài)*/

)

(5)

typedefstructQnode

{ElementTypedata;

StructQnode*next;

}QueueNode;

typedefQueueNode*LinkQueue;

voidAddQueue(LinkQueue*rear,ElementTypee)

/*帶頭結(jié)點(diǎn)的循環(huán)鏈表隊列，只有指向尾結(jié)點(diǎn)的指針rear,對其實現(xiàn)入隊操作*/

{p=(LinkQueue)malloc(sizeof(QueueNode));

p-*data=e;

p-*next=(*rear)fnext;

(*rear)fnext=p;

(*rear)=p;

)

ElementypeDeleteQueue(LinkQueue*rear)

/*帶頭結(jié)點(diǎn)的循環(huán)鏈表隊列，只有指向尾結(jié)點(diǎn)的指針rear,對其實現(xiàn)出隊操作*/

{if((*rear)-next==*rear)

{printf(4€\nempty")；

return(nil);

)

p=(*rear)next-*next;

e=p->data;

(*rear)->next-*next=(*rear)fnext-*next-*next;

free(p);

return(e);

1

(6)

①

voidAddQueue(Cii*Queueq,ElementTypee)

/*借助于堆棧si,s2實現(xiàn)隊列q的入隊*/

{Push(sl,e);

)

②

ElementTypeDeleteQueue(CirQueueq)

/*借助于堆棧si、s2實現(xiàn)隊列q的出隊*/

{if(Empty(s1)&&Empty(s2))

{printf(t4\nempty^^);

return(nil);

else

if(!Empty(s2))

Pop(s2);

else

{while(!Empty(si))

Push(s2,Pop(sl));

Pop(s2);

(7)

#defineMAXSIZE50

typedefstruct

{QueueElementTypeelem[MAXSIZE];

intfront,rear,tag;/*將標(biāo)志tag設(shè)置為隊列的一個成員，便于數(shù)據(jù)的傳遞tag=0表示隊列

為空，tag二l表示隊列不空*/

(CirQueue;

voidInitQueue(CirQueue*q)

{q->front=q->rear=0;

q->tag=0;

)

intAddQueue(CirQueue*q,ElementTypee)

/*入隊*/

{if(q->tag==1&&q->rear==q->front)

{printf(t4\noverflow");

returnERROR;

)

if(q->tag==0&&q->rear==q->front)

q->tag=l;/*有元素入隊，則隊列一定不空，將tag置1*/

q->elem|q->rear]=e;

q->rear=(q->rear+l)%MAXSIZE;

returnOK;

)

intDeleteQueue(CirQueue*q,QueueElementType*e)

/*出隊*/

{if(q->tag==0&&q->rear==q->front)returnERROR;

*e=q->elem[q->front];

q->front=(q->front+1)%MaxSize;

if(q->rear==q->front)q->tag=O;

/*有元素出隊后，隊頭和隊尾相等，隊列為空，則將tag置0*/

returnOK;

第四章

1.填空題

(1)字符

(2)0空格的個數(shù)

(3)14"becadcabcadfabc""abc"81(true)“becad

ebeadf'"abebecadcabcadf'"beadcabcadf

(4)197

(5)三維數(shù)組arr[6][2][3]的每個元素的長度為4個字節(jié)，如果數(shù)組以行優(yōu)先的順序存儲，

且第1個元素的地址是4000,那么元素arr[5][0]⑵的地址是4000+4*(5*2*3+0*3*2)=4128

2.判斷題

(1)X(2)V(3)X(4)V(5)V(6)J(7)X(8)V(9)X(10)V

3.

(1)

0(當(dāng)/=；+1)

?=<I(當(dāng)i=j)

2(當(dāng)i=j-1)

V=j

⑵符號表

s30

t53

u78

堆

01234567891011

abcXabcyzXab

cyz

t

free

(3)最壞情況下的時間復(fù)雜度為O(m*n),其中m為串s的長度，n為串t的長度

(4)三維數(shù)組arr⑹⑵⑶的每個元素的長度為4個字節(jié)，該數(shù)組要占6*2*3*4=144個字節(jié)，

若數(shù)組以列優(yōu)先的順序存儲，設(shè)第一個元素的首地址是4000,則元素arr[5][0][2]的存儲地

址是4029。

(5)

k=X(5-/)+(i-j)-5

①，=。

②((0,0』),(0,3,2),(1』,3),(2,3,5),(3,0,2),(3,2,5))

(6)

行優(yōu)先：

a0,0,0,0a0,0,0,1a0,0,0,2a0,0,1,0a0,0,1,1a0,0,1,2

a0,1,0,0a0,1,0,1a0,1,0,2a0,1,1,0a0,1,1,1a0,1,1,2

a0,2,0,0a0,2,0Ja0,2,0,2a0,2,1,0a0,2,1,1a0,2,1,2

a1,0,0,0a1,0Ala1,0,0,2a1,0,1,0a1,0,1,1a1,01,2

a1,1,0,0a1,1,0,1a1,1,0,2a1,1,1,0a1,1,1,1a1,1,1,2

a1,2,0,0a1,2,0,1a1,2,0,2a1,2,1,0a1,2,1,1a121,2

列優(yōu)先：

a0,0,0,0a1,0,0,0a0,1AOa1,1,0,0a0,2,0,0a1,2,0。

a0,0,1,0a1,0,1,0a0,1,1,0a1,1,1,0a0,2,1,0a1,2,1,0

a0,0,0,1a1,0,0,1a0,1,0,1a1,1,0,1a0,2,0,1a1,2,0,1

a0,0,1Ja1,0,a0,1,1,1al,U,1a0,2,1,1a1,2,1,1

a0,0,0,2a1,0,0,2a0,1.0,2a1,1,0,2a0,2,0,2al,2,0,2

a0,0,1,2a1,0,1,2a0,1,1,2a1,1,1,2a0,2,1,2a1,2,1,2

(7)稀疏矩陣壓縮存儲后會失去隨機(jī)存取的功能，因為稀疏矩陣不能根據(jù)元素在矩陣中的位

置求得在其在三元組順序表中的位置，而特殊矩陣則可以。

n^m

t<------

⑻當(dāng)3t<m*n即3時，三元組的表示才有意義。

(9)

①i=j或i+j=n+l

,12("1)(當(dāng)i=/)

②1)+1(當(dāng)i+j=〃+l)

4、算法設(shè)計題

(1)

voidAssign(BlockLink*s,chart[])

/次將存放在字符數(shù)組t中常量賦給s*/

{ss=s;

for(i=0;t[0]!=,\0,;i++)

{if(i%NodeNum==0)

{j=o；

p=(BlockLink*)malloc(sizeof(BlockLink));

pfnext=Null;

ss—next=p;

ss=p;

}

p-datafj]=t[i];

j++；

}

while(j!=NodeNum-l)

{pfdata[j]='#';

j++；

)

(2)

voidfrequency(intnum[])

/*統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。*/

{

for(i=0；i<26；i++)num[i]=0；/*初始化*/

while((ch=getchar())!='#')/*表示輸入字符串結(jié)束。*/

if(ch>='a'&&ch<='z')/*小寫字母*/

{i=ch—97;

num[i]++；

)

elseif(ch>=，A'&&ch<='Z')/*大寫字母*/

{i=ch-65+10;

num[i]++；

)

(3)

①

intJudgEqual(inga[][],intm,intn)

/*判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。*/

{for(i=0;i<m;i++)

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

{for(p=j+l;p<n;p++)/*和同行其它元素比較*/

if(a[i][j]—a[i][p])retum(O);

for(k=i+l;k<m;k++)/*和第i+1行及以后元素比較*/

for(p=0;p<n;p++)

if(a[il[j]==afk][p])return(O);

)

return(1);/*元素互不相同*/

)

②

二維數(shù)組中的每一個元素同其它元素都比較一次，數(shù)組中共m*n個元素，第1個元素同其

它m*n-l個元素比較，第2個元素同其它m*n-2個元素比較，，第m*n-l個元素同最

后一個元素(m*n)比較一次，所以在元素互不相等時總的比較次數(shù)為(m*n-l)+(m*n-2)+…

+2+1=(m*n)(m*n-l)/2。在有相同元素時，可能第一次比較就相同，也可能最后一次比較時相

同,設(shè)在每個位置上均可能相同，這時的平均比較次數(shù)約為(m*n)(m*n-l)/4,總的時間復(fù)雜

度是O(m2*n2)?

(4)

#defineMaxSize線性表可能的最大長度

typedefstruct

(inirow,column;

}element

typedefstruct

{elementelemfMaxSize];

intlistlength;

}SeqList;

voidGetSaddle(intA[],intm,intn,SeqlLists[])

/*求矩陣A,“x”中的鞍點(diǎn)，鞍點(diǎn)的位置存放在順序表S中*/

(

s.listlength=O;

for(i=0;i<m;i++)

{

for(min=A[i][0],j=0;j<n;j++)

if(A[i][j]<min)求一行中的最小值*/

for(j=0;j<n;j++)

if(A[i皿=二min)/*判斷這個(些)最小值是否鞍點(diǎn)*/

(

for(flag=l,k=0;k<m;k++)

if(min<A[k][j])flag=0;/*不是鞍點(diǎn)*/

if(flag)/*是鞍點(diǎn)*/

{s.elem[listlength].row=i;

s.elem[listlength].column=j;

s.listlength++;

(5)

[題目分析]矩陣中元素按行和按列都已排序，要求比較次數(shù)不超過m+n,因此不能采用常規(guī)

的二層循環(huán)的查找?？梢韵葟挠疑辖?i=0,j=n)元素與x比較,只有三種情況:一是A[i,j]>x,

這情況下向j小的方向繼續(xù)查找;二是A[i,j"x,下步應(yīng)向i大的方向查找;三是A[i,j]=x,

查找成功。否則，若下標(biāo)已超出范圍，則查找失敗。

voidsearch(ElementTypeA[][],intm,intn,ElementTypex,int*row,int*column)

/*m*n的矩陣b,本算法查找x在矩陣b中的位置(*row,"column)*/

{i=0;j=n;flag=0;/*flag是成功查到x的標(biāo)志*/

while(i<=m&&j>=0&&!flag)

if(b[i][j]==x)

flag=l;

elseif(b[i][j]>x)

j-；

else

i++；

if(flag)

{*row=i;

*column=j;

else

*row=-l;

*column=-l;

[算法討論]算法中查找x的路線從右上角開始,向下(當(dāng)x>b[i,j])或向左(當(dāng)x<b[i,j])o

向下最多是m,向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角(b[m,0]),

比較m+n次。

(6)

voidTSMatrixAddto(TSMatrix&A,TSMatrixB)〃將三元組矩陣B加到A上

for(i=0;i<A.nums;i++)

/*把A的所有元素都移到尾部以騰出位置*/

A.data[MaxSize-A.nums+i]=A.data[i];

pa二MaxSize-A.nums;pb=0;pc=0;

for(x=0;x<A.rows;x++)/*對矩陣的每一行進(jìn)行加法*/

(

while(A.data[pa].r<x)

pa++;

while(B.data[pb].r<x)

pb++;

while(A.data[pa].r==x&&B.data[pb].r=x)/*行值相等的元素*/

(

if(A.data[pa].c==B.data[pb].c)/*列值也相等*/

ne=A.data[pa].d+B.data[pb].d;

if(ne)/*和不為0*/

A.data[pc].r=x;

A.data[pc].c=A.data[pa],c;

A.data[pc].d=ne;

pa++;pb++;pc++;

elseif(A.data[pa].c>B.data[pb].c)

A.data[pc].r=x;

A.data[pc].c=B.data[pb].c;

A.data[pc].d=B.data[pb].d;

pb++;pc++;

)

else

A.data[pc].r=x;

A.data[pc].c=A.data[pa],c;

A.data[pc].d=A.data[pa].d

pa++;pc++;

)

)

while(A.data[pa]==x)/*插入A中剩余的元素(第x行)*/

(

A.data[pc].r=x;

A.data[pc].c=A.data[pa],c;

A.data[pc].d=A.data[pa].d

pa++;pc++;

)

while(B.data[pb]==x)/*插入B中剩余的元素(第x行)*/

(

A.data[pc].r=x;

A.data[pc].c=B.data[pb].c;

A.data[pc].d=B.data[pb].d;

pb++;pc++;

)

)

A.nums=pc;

for(i=A.nums;i<MaxSize;i++)

/*清除原來A中的元素*/

{A.data[i].r=-l;

A.data[i].c=-l;

A.data[i].d=nil;

)

}

第五章習(xí)題答案

1.填空題

(1)

am,n,d,j,k,hf

(2)非線性根

(3)5

(4)加+1

(5)完全I(xiàn)log2n1+1最大n

(6)2k-l2k-l

(7)2nn-1n+1

(8)a在b的左邊

(9)2m-l

(10)58

2.判斷題

(1)X(2)X(3)X(4)V(5)V(6)J(7)V(8)V(9)V(10)

3.選擇題

(1)C(2)B(3)A(4)C(5)B

4.簡答題

(1)雙親數(shù)組表示法：

dataparent

0a-1

1b0

2c0

3d1

4e1

5f2

6g2

7h2

8i4

9j6

10k6

1117

12m8

13n8

孩子鏈表表示法:

（2）能唯一確定這棵二叉樹。二叉樹為:

若給定先序序列和后序序列無法唯一確定一棵二叉樹，因為根據(jù)先序序列雖可以確定

根，但不可以根據(jù)后序序列確定左子樹和右子樹。如下面兩棵二叉樹，它們的先序序列和后

序序列相同，但卻確定了兩棵不同的二叉樹。

(3)總結(jié)點(diǎn)數(shù)n=no+ni+ri2+…+nm-i+nm①

因為度為1的結(jié)點(diǎn)發(fā)出1個分支，度為2的結(jié)點(diǎn)發(fā)出2個分支，…，度為m的結(jié)點(diǎn)發(fā)出m

個分支，葉結(jié)點(diǎn)不發(fā)出分支，所以，總分支數(shù)B為：B=rn+2n2+...+m*nm②

又因除根之外，其它結(jié)點(diǎn)有且僅有一個分支進(jìn)入，因此，總分支數(shù)應(yīng)等于總結(jié)點(diǎn)數(shù)減1,即

B=n-1③

由②③得：n=m+2n2+_+m*nm+1④

由①④得葉結(jié)點(diǎn)數(shù)：no=n2+2n3…+(m-1)*nm

非終端結(jié)點(diǎn)數(shù)為:n)+n?+...+nm.i+nm

(4)①a.空二叉樹；b.只有一個根結(jié)點(diǎn)的二叉樹c.任一結(jié)點(diǎn)均無左子樹的非空二叉樹

②a.空二叉樹；b.只有一個根結(jié)點(diǎn)的二叉樹c.任一結(jié)點(diǎn)均無右子樹的非空二叉樹

③a.空二叉樹；b.只有一個根結(jié)點(diǎn)的二叉樹

(5)①第i層的結(jié)點(diǎn)數(shù)為k」(其中i=l,2,....h)

②當(dāng)i不等于1時，i的雙親為I(i-2)/k1+1(其中k>=2)

③編號為i的非葉子結(jié)點(diǎn)的第j個孩子結(jié)點(diǎn)的編號是(iT)*k+j+l。

④編號為i的結(jié)點(diǎn)有右兄弟的條件是(iT)%k〈>0,其右兄弟的編號是i+lo

(6)(a)先序序列：12345中序序列：24531后序序列：54321

(b)先序序列：12345中序序列：13542后序序列：54321

(c)先序序列：123578624中序序列：17583624后序序列：78563421

(d)先序序列：124735689中序序列：472153869后序序列：742589631

先序線索樹：中序線索樹：后序線索樹：

后序線索樹

(7)①a的先序序列：ABCDEFa的后序序列：BDEFCA

b的先序序列：GHIJKb的后序序列：IJKHG

c的先序序列：LMPQRNOc的后序序列：QRPMNOL

②森林的先序序列：ABCDEFGHIJKLMPQRNO

森林的后序序列：BDEFCAI.JKHGQRPMNOL

③轉(zhuǎn)換后的二叉樹：

④題中圖5-35改為5-36

雙親數(shù)組表示：

孩子兄弟表示法:

易于求子孫

root

(a)(b)(c)

(10)

A

（11）哈夫曼樹及編碼為:

5.算法設(shè)計題

(1)

voidPreOrderz(BinTreeroot)

{BinTrees[M];〃設(shè)棧的容量足夠大

top=-1;p=root;

do

{while(p!=NULL)

{printfC4%c,,,p->data);s[++top]=p;p=p->child;}

if(top!=-1)

{p=s[top-];p=p->rchild;}

[while((top!=-1)||(p!=NULL));

)

(2)

intcount=0;

voidcountnode1(BinTreeroot)

{if(root==NULL)

return;

if((root->lchild!=NULL&&root->rchild==NULL)||

(root->lchild==NULL&&root->rchild!=NULL))

count++;

countnodel(root->lchild);

countnodel(root->rchild);

)

(3)

intcount(BinTreeroot)

{if(root==NULL)

return0;

if(root->lchild==NULL&&root->rchild==NULL)

return1;

returncount(root->lchild)+count(root->rchild);

}

(4)

intlevel(BinTreeroot,ElemTypex)

〃在以root為根的二叉樹中按先序查找值為x的結(jié)點(diǎn)，找到返回其所在層數(shù)否則返回0

{BinTreep,f,stackl[50];〃設(shè)棧的容量足夠大

inth,stack2[50]//stack2用來保存p結(jié)點(diǎn)所在的層數(shù)

inttop=-l;〃置空棧。stackl和stack2可共用一個棧頂指針

p=root;h=l;〃根為第一層

do

{while(p!=NULL&&p->data!=x)

{stackl[++top]=p;stack2[top]=h;p=p->lchild;h++;}

if(p!=NULL)

returnh;

else

if(top!=-l)

{p=stackl[top];h=stack2[top-];p=p->rchild;h++;}

[while(p!=NULL)||(top!=-l);

return0;

)

(5)①在先序線索樹中查找*p的先序后繼

若*P有左孩子即ltag=0,則左孩子為后繼；若*p無左孩子即ltag=l,則右孩子為后

繼

ThBinTreePreOrderSucc(ThBinTreeroot)

{if(root->ltag==0)

returnroot->lchild;

else

returnroot->「child;

)

②在后序線索樹中查找*p的后序前驅(qū)

若*P有右孩子即rtag=0,則右孩子為前驅(qū)；若*p無右孩子即rtag=1,則左孩子為前

驅(qū)。

ThBinTreePreOrderPre(ThBinTreeroot)

{if(root->rtag=0)

returnroot->rchild;

else

returnroot->lchild;

)

(7)

intzhengze(BinTreeroot)

(

if(root!=NULL)

(

if(root->lchild!=NULL&&root->rchild==NULL||

root->lchild==NULL&&root->rchild!=NULL)

{returnFalse;}

else{

returnzhengze(root->lchild)&&zhengze(root->rchild);

)

)

elsereturnTrue;

)

寫法二：

intflag=l；/*定義一個標(biāo)志flag,運(yùn)行函數(shù)后，若flag為1表示其為嚴(yán)格二叉樹，若flag

為0表示其不是嚴(yán)格二叉樹*/

voidzhengze(BiTreeroot)

(

if(root!=NULL)

(

if(root->lchild!=NULL&&root->rchild==NULL||

root->lchild==NULL&&root->rchild!=NULL)

{flag=0;return;}

zhengze(root->lchild);

zhengze(root->rchild);

)

)

第六章習(xí)題答案

1.填空題

⑴e=-SD(V,)

2fr

i

(2)-n(n-l)

2

⑶入度

(4)先序?qū)哟?/p>

(5)n-1

(6)O(n2)O(elog2e)kruskal

(7)4

⑻邊的數(shù)目

(9)n2-e

(10)n+l

2.判斷題

(1)X(2)J(3)V(4)X(5)V(6)V(7)X(8)X(9)J(10)X

3.簡答題

(1)①

②鄰接矩陣:

,01010、

10011

00011

11100

I。1100)

鄰接表:

③TD(Vi)=2TD(V2)=3TD(V3)=2TD(V4)=3TD(V5)=2

(2)鄰接矩陣為：

,000000、

100100

000001

001011

100000

110010-^

鄰接表為:

②若鄰接矩陣A中的元素A[i]5的值為非零，則頂點(diǎn)V,和V1之間有邊相連

③對于任意一個頂點(diǎn)i,它的度為鄰接矩陣第i行（或第i列）的非零（或非8）元

素數(shù)目。

（4）題中無向圖改為有向圖。

①邊（?。?shù)為鄰接表中所有單鏈表的邊結(jié)點(diǎn)數(shù)目。

②若第i個單鏈表中存在一個邊結(jié)點(diǎn)，其adjvex域的值為J,則頂點(diǎn)V,和明之間有邊

（?。┫噙B

③對于任意一個頂點(diǎn)i,它的入度為所有單鏈表中adjvex域的值為i的邊結(jié)點(diǎn)數(shù)目，

它的出度為第i個單鏈表中邊結(jié)點(diǎn)數(shù)目。

（5）①鄰接表：

②把題中修改V。。

深度優(yōu)先搜索：Vo,Vt,V3,V=V2,V5,V6

廣度優(yōu)先搜索：V。，V,,V2,V3,V.?Vs,V6,V7

（6）①

③權(quán)值：1+2+2+4+5=14

(7)題中圖的頂點(diǎn)標(biāo)記改為數(shù)字,如下圖，且求從1到其它頂點(diǎn)的最短路徑。

①

(8201588