數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題參考答案

數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案

第一章:

一、1、B,H2、A,B3、D,C4、C5、C,E6、A,B7、A8、D9、

B10、A11、D

二、1、線性、樹型和圖型，非線性2、集合、線性、樹型、圖形結(jié)構(gòu)

3、有窮性、確定性、可行性、輸入和輸出4、時(shí)間復(fù)雜度和空間復(fù)雜度

5、一對(duì)一、一對(duì)多、多對(duì)多6、O(n)7、O(m*n)8、邏輯關(guān)系

9、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對(duì)數(shù)據(jù)施加的操作

10、沒有、一個(gè)11、一個(gè)、一個(gè)、后繼、任意個(gè)12、任意個(gè)13、物理

14、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)15、結(jié)點(diǎn)、記錄、元素、頂點(diǎn)16、順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、

索引存儲(chǔ)、散列存儲(chǔ)17、正確性、可讀性、健壯性、高效性18、時(shí)間復(fù)雜度、空

間復(fù)度、計(jì)算量、存儲(chǔ)量19、問題規(guī)模20、1、log2n.n、n\2"、不可行21、設(shè)

計(jì)、實(shí)現(xiàn)22、數(shù)據(jù)元素23、數(shù)學(xué)模型

、判斷題

1.X2.V3.V4.X5.V6.V7.X8.X

四、計(jì)算題

1、(1)n-2(2)n(n+l)/2(3)n

2^(l)n(2)1(3)n(4)n-l(5)(n-l)(n-2)/2(6)n-1

3、O(n)O(n2)

6、解答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并

被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)

據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系

的數(shù)據(jù)元素的集合。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合。

7、解答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的，存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存

儲(chǔ)到計(jì)算機(jī)中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān)，存儲(chǔ)結(jié)

構(gòu)是數(shù)據(jù)元素及其之間的關(guān)系在計(jì)算機(jī)中的表示。

8、(2/3)”,210,login,yfn,n23,n,nlog2n,n\n\2n,n!

第二章：一、選擇題

kE,A2、C3、B4、D5、B6、A7、C8、B9、A10、B11、C12、

C13、D14、A,C,D15、A16、D17、B18A19、B20、C

21、A22、D23D

二、填空題

1、沒有；1

2、表中一半；該元素的位置

3、(1)FC(2)BIAG

4、(1)HGBJ(2)HFDBJ

5、(1)FAI(2)EGDAI

6、n/2,n/4

7、0(1)O(n)

8、線性表

9、插入和刪除首元素時(shí)不必進(jìn)行特殊處理

10、其直接前趨結(jié)點(diǎn)的鏈域

11q->prior=p;

12、前趨結(jié)點(diǎn)，后繼結(jié)點(diǎn)

13、必定，不一定

14、結(jié)點(diǎn)、第一個(gè)、最后一個(gè)、位置、前驅(qū)、后繼

15、前驅(qū)、前驅(qū)、后繼、后繼

16、線性

17、線性、長(zhǎng)度

18、p-*next=NULL;

三、判斷題

172.x3.V4.x5.V677.x8.V9.x10,x

四、簡(jiǎn)答題

1、宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)樗咕€性表的插入和刪除操作的時(shí)間復(fù)雜度為O(1),兩頁

序存儲(chǔ)結(jié)構(gòu)的為O(n),

2、首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表

的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存線性表的數(shù)據(jù)元素，

其作用是為了對(duì)鏈表進(jìn)行操作時(shí).，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一

的處理。頭指針是指向鏈表第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)或首元結(jié)點(diǎn))的指針。若鏈表中附設(shè)頭

結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。

這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。

3、在等概率前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為(0+1+2+…+n)/(n+l)=n/2。

若元素插在ai與ai+1之間(0<=i<=n-l)的概率為2(n-i)/(n(n+l)),則平均每插入一個(gè)元

素所要移動(dòng)的元素個(gè)數(shù)為：(2n+l)/3

4、解答：?jiǎn)窝h(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以任一結(jié)點(diǎn)從遍歷表中其它結(jié)點(diǎn)，

但設(shè)置尾指針時(shí)，若在表尾進(jìn)行插入或刪除操作時(shí)可在0(1)時(shí)間內(nèi)完成，同樣在表頭進(jìn)

行插入或刪除操作時(shí)也可在0(1)時(shí)間內(nèi)完成。但若設(shè)置的是頭指針，表尾進(jìn)行插入或刪

除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為0(n)。

5、解答：能刪除。雙鏈表上刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1),單循環(huán)鏈表上刪除

P所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(n)。

6、解答：如果長(zhǎng)度大于1,則將首元結(jié)點(diǎn)刪除并插入到表尾。

7、解答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配存儲(chǔ)單元，不

能隨著線性表長(zhǎng)度的改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)的申請(qǐng)空間，因此適用于動(dòng)

態(tài)變化表長(zhǎng)的線性表。

8、解答：應(yīng)該用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為0(1)。

9、解答：用單鏈表表示多項(xiàng)式，除指針域外需設(shè)置兩個(gè)數(shù)據(jù)域，一個(gè)用來存儲(chǔ)系數(shù)，一個(gè)

用來存儲(chǔ)指數(shù)。

⑶c—

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

1、

voidsplit(SqListA,SqList&B,SqList&C)

{〃采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

intI;B.length=C.length=O;

for(I=0;I<AS.length;I++)

{if(A.elem[i]>O){B.elem[B.length]=A.elem[i];B.length++;}

else

{C.elem[C.length]=A.elem[i];C.length++;}

statusListInsert(SqList&L,ElemTypee)

{ElemType*p,*q,*newbase;

intj;

if(L.length>=L.listsize){

newbase=(ElemType)realloc(L.elem,

(L.listsize+LISTINCRMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.Iistsize=+LISTINCRMENT;}

For(j=L.length-l;j>=0&&e<L.elem|j];j-)L.elem|j+l]=L.elem|j];

L.elem[j+l]=e;

++L.length;

returnOK;

)

3、提示：兩個(gè)表的公共元素指的是既存在于A表中，也存在于B表中的元素，為了操作方

便，先讓單鏈表C帶有一?個(gè)頭結(jié)點(diǎn)c,再后將其刪除。

LinkListInter_eq(LinkLista,LinkListb)

{LinkListp,q,r,c;

c二(LinkList)malloc(sizeof(LNode));〃建立單鏈表C的頭指針

r=c;p=a;q=b;

while(p&&q)

{if(p.data<q.data)p=p.next;

elseif(p.data>q.data)q=q.next;

else〃找到元素值相同的結(jié)點(diǎn)

{s=(LinkList)malloc(sizeof(LNode));

s.data=p.data;r.next=s;r=s;〃把s結(jié)點(diǎn)鏈到c的末尾，r始終指向鏈表C的最

后一個(gè)結(jié)點(diǎn)

while(p.data==p.next.data)p=p.next;〃跳過相同的值的結(jié)點(diǎn)

p=p.next;

while(q.data==q.next.data)q=q/next;

q=q.next;

)

)

r.next=NULL;

s=c;c=c.next;free(c);〃刪除C鏈表的頭結(jié)點(diǎn)

return(c);

)

4、參考程序：

voidoutmin(LinkListL)

{LinkListp=L,q=L;

inttemp;

while(q)

{if(p.data>q.data)p=q;

q=q.next;

)

printf("％d”,p.data);

if(p.next)

{if(p.data%2==l){temp=p.data;p.data=p.next.data;p.next.data=temp;}

else

{q=p.next;p.next=q.next;free(q);}

第三章:

一、選擇題

1、A2、B3、C4、C5、B6、D7>B8、C9、C10、A11、A12、A13、

B14、C15、D16、C17、B18、B19、B20、A21、A22、C23、A

二、判斷題

1.V2,X3.X475..X6.X7.X8.V9.X10.V

三、填空題

1、先進(jìn)后出先進(jìn)先出2、線性；任何；棧頂；隊(duì)尾；隊(duì)首3、srack

4、HS==NULL5、存入元素，移動(dòng)棧頂指針6、移動(dòng)棧頂指針，取出元素

7、1和n；1和18、先取出元素，后移動(dòng)對(duì)尾指針9、前一個(gè)位置

10、n-1IkHQ.front==HQ.rear12>313、char14、18

三、簡(jiǎn)答題

1、利用棧的“后進(jìn)先出”的特點(diǎn),共有如下5種情況:

A進(jìn)A出B進(jìn)B出C進(jìn)C出產(chǎn)生輸出序列ABC

A進(jìn)A出B進(jìn)C進(jìn)C出B出產(chǎn)生輸出序列ACB

A進(jìn)B進(jìn)B出A出C進(jìn)C出產(chǎn)生輸出序列BAC

A進(jìn)B進(jìn)B出C進(jìn)C出A出產(chǎn)生輸出序列BCA

A進(jìn)B進(jìn)C進(jìn)C出B出A出產(chǎn)生輸出序列CBA

2、（1）利用棧s將數(shù)組a中的元素逆置。（2）利用棧t將棧s中的數(shù)據(jù)元素e刪除。

3、將si棧的棧底置為0,棧頂由低向高移動(dòng)；將s2的棧底置為m-1,棧頂由高向低移動(dòng)。

4、print(4)的輸出結(jié)果為：

1

22

333

4444

5、算法的功能：利用棧的輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。

6、當(dāng)元素d,e,b,g,h入隊(duì)后，rear=4,front=0,元素d和e出隊(duì)，rear=4,front=2；元素

入隊(duì)，rear=10,front=2；元素b出隊(duì)，rear=10,front=3；此時(shí)若再讓n?o,p,q,r入隊(duì)時(shí)，由于

(rear+1)%10=front,故棧上溢。

7、解答：

序號(hào)Optr棧Opnd棧輸入字符操作

1#9push(0pnd/9,)

2#9-push(Optr,,~,)

3#-92push(Opnd/2,)

4#-92*push(Optr,'*')

5#-*924push(Opnd/4,)

6#-*924+push(Opnd,operate(,2\,*\,4,)

7#-98push(Opnd,operate(,9\,-,/8,)

8#1push(Optr,,+,)

9#+1(push(Optr,'(')

10#+(18push(Opnd,,8,)

11#+(18+push(Optr/+5)

12#+(+181push(Opnd/r)

13#+(+181)push(Opnd,operate(,8\,+\,1')

14#+19/push(Optr,7,)

15#+/193push(Opnd,,3,)

16#+/193#push(Opnd；9\7\,3,)

17#+13push(Opnd,T,'+','3')

18#4retum(,4,)

8、解答:S=(6,4,2,l,3,5,7)。其中7為棧頂元素。

9、解答：該遞歸過程不能簡(jiǎn)單的改寫成一個(gè)遞推形式的過程，從它的執(zhí)行過程可見，其輸

出的順序恰好和輸入相反，則必須用一個(gè)輔助結(jié)構(gòu)保存其輸入值，然后逆向取之，所以用棧

最為合適。

voidditui(int*sum)

{StackS;

intx;

scanf(x);

Stacklnit(S);

while(x)

{Push(S,x);scanf(x);}

sum=0;

printf(sum);

while(Pop(S,x))

{sum+=x;printf(sum);}

)

)

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

1、intcount(LinkListHS)

{Linklistp;intn=0;p=HS;

while(p){n++;p=p->next;}

return(n);)

2、(1)遞歸算法如下：

intgcd(intm,intn)

{intk;if(n==0)return(m);

elseretum(gcd(n,m%n));}

(2)非遞歸函數(shù)如下：

intgcd2(intm,intn)

{intr;do{r=m%n;m=n;n=r;}while(r);retum(m);}

⑶略

3、本題實(shí)質(zhì)上就是簡(jiǎn)答題5。

Queueinverse(QueueQe)

{Stacks;SetEmpty(s);while(!IsEmptyQ(Qe))push(s,DeQueue(Qe));

while(!IsEmptyS(s))EnQueue(Qe,Pop(s));

return(Qe);}

4、定義單鏈表結(jié)點(diǎn)類型如下：

typedefstructLnode{

ElemTypedata;

StructLnode*next;

}Lnode,*LinkNode;

根據(jù)單鏈表的特點(diǎn)，實(shí)現(xiàn)隊(duì)列的5種運(yùn)算的函數(shù)如下：

voidsetnull(LinkNodefront,LinlNoderear)

{front=NULL;rear==NULL;}

statusgetfirst(LinkNodefront,LinkNoderear,ElemTypex)

{if(front==NULL)returnFALSE;

else

{x=front->data;retumOK;})

statusenqueue(LinkNodefront,LinkNoderear,ElemTypex)

{LinkNodep;

if(rear==NULL){rear=(LinkNode)malloc(sizeof(LNode));rear->data=x;front=rear;}

else

{p=(LinkNode)malloc(sizeof(LNode));

p->data=x;p->next=NULL;rear->next=p;rear=p;}

returnOK;}

statusDequeue(LinkNodefront,LinkNoderear)

{LinkNodep;

if(front==rear)returnFALSE;

else

{p=front;front=front->next;free(p);retumOK;}}

intQueueEmpty(LinkNodefront)

{if(front==NULL)return(1);elseretum(O);}

第四章

一、選擇題

1、D2、B3、E4、D5、B6、B7、B

二、判斷題

1.x2.V3.V

三、填空題

k142、零個(gè)字符的串零3、，GOODBYE!，4、兩個(gè)串的長(zhǎng)度相

等且對(duì)應(yīng)位置字符相同5、順序存儲(chǔ)方式和鏈接存儲(chǔ)方式

6、有一個(gè)或多個(gè)空格組成的串、串中空格字符的個(gè)數(shù)

7、匹配

8、交換律、結(jié)合律

四、簡(jiǎn)答題

1、

s=,thissampleis,;t=,agoodone,;u=,one,;

v=,thissampleisagoodone';

length(s)=14;index(v,g)=3;index(u,g)=0

2.

T=,thesearebooks9;v=,yxy,;u='xwxwxw'

3.

14,4,'student','o',3,0,1amaworker','agoodstudent'

4.

sl=substr(s,l,5)//sl=,(xyz)^

s2=substr(s,3,l)//s2=,y,

s3=substr(s,6,l)〃s3='+'

s4=substr(s,7,l)〃s4='*，

replace(s1,3,1,s3)//sl='(x+y)'

s=sllls4lls2

五、設(shè)計(jì)題

1.intsearch(Hstrings,Hstringt)

{intI=O,flag=l;

while(I<s.length&&I<t.length&&flag)

{if(s.ch[i]!=t.ch[i])flag=O;I++}

if(flag)return-1;

elsereturn1-1;

2.intdelij(Hstring&s,intI,intj)

{intk;

if(I<0llj<0)return0

if(I+j>s.length)j=s.length-I;

for(k=I+j;k<s.length;k++)s.ch[k-j]=s.ch[k];

s.length-=j;

return1;

)

3.intcompare(Hstringx,Hstringy)

{intI=O,flag=l;

if(x.length!=y.length)return0;

else

{while(I<x.length&&I<y.length&&flag)

{if(x.ch[i]!=y.ch[i])flag=O;

1++;}

Returnflag;

)

)

第五章答案：

-、IB、2B、3B、4C、5C、6B>7B、8CC、9CD、10BC、HAD,12CB、13B、14D、

15D、16D17B18C

二、判斷題

1.X2.V3.X4.X5.V6.V7.V8.x9.x

三、1、最大整數(shù)的遞歸定義為：f(k)=a|O](k=O時(shí))llf(k)=max(f(k-l),a[k])(k>0時(shí))

最小整數(shù)的遞歸定義為：f(k)=a[O](k=O0t)llf(k)=min(f(k-l),a[k])(k>O時(shí))

2、1056

3、loc(A[0][0])+(n*I+j)*k

4、深度

5、Head(L)=();Tail(L)=(());L的長(zhǎng)度為2,L的深度為2

6、原子或子表，鏈表

7、((a)),()

8、(a),(((b),c),(((d))))

9、(a,b)

10、a,((c,d))>A或(a,b,c)

[怨當(dāng)E

H卜”+l)+i,當(dāng)『<j

12、

rowcole

132

213

33-1

345

13、n(n+l)/2

14、(dl-cl+l)*(d2-c2+l)*(d3-c3+l)

15、913

16、2210

四、計(jì)算題

1、A[2][4][5]的存儲(chǔ)地址為loc(2,4,5)=loc(0,0,0)+(2*6*9+4*9+5)*5=54+149*5=799

2、(1)存儲(chǔ)量=(6*8)*6=288

(2)數(shù)組A的最后一個(gè)元素a57的地址：1000+288-6=1282

(3)按行存儲(chǔ)時(shí)，al4的地址：1000+(1*8+4)*6=1072

(4)按列存儲(chǔ)時(shí),a47的地址：1000+(7*6+4)*6=1276

3、(1)100(2)772(3)1784(4)4416

4、四維數(shù)組A的按行優(yōu)先順序在內(nèi)存中的存儲(chǔ)次序?yàn)椋篈0000,AOOOKA0010,A001K

A0100、A0101,A0110,AOllkA1000,A100KA1010,A1011,A1100、AllOKA1110.

AHU；按列優(yōu)先存儲(chǔ)順序?yàn)?A0000>A1000,A0100、Al100,A0010、A1010、Al110、

A0001>A1001>AOIOkA110UA0011,A1011,A011KAllll

10、k=(I-l)(2n-I+2)/2+j-I+l(I<=j時(shí))和k=(j-l)(2n-j+2)/2+I-j+l(I>j時(shí))

11、略

四、簡(jiǎn)答題

1、廣義表是線性表的推廣，形式上定義為L(zhǎng)S=(ai,a2,國(guó)可以是單個(gè)元素，也可

以是廣義表，并分別稱為廣義表的原子和子表。

主要區(qū)別是：線性表中元素只能是單個(gè)元素，而廣義表中元素可以是單個(gè)元素，

也可以是廣義表；線性表中各元素是獨(dú)立的，而廣義表中元素可以為其他表或子表共享，特

別地，廣義表可以是一個(gè)遞歸的表，即廣義表也可以是其本身的一個(gè)子表。

2、Head(Tail(Tail(Ll)))=studentHead(Tail(Head(Tail(L2))))=student

3、

4、

5、

6、(1)

深度為4

(2)

深度為4

7、脩：(1)((x,(y)),(((())),(),(z)))

(2)(((a,b,()),()X(a,(b)),())

五、設(shè)計(jì)題

1、(1)intsuml(intA[m][n])

{ints=O,I,j;

for(I=0;I<m;I++)s=s+(A[i][O]+A[i][n-l]);

for0=1;j<n-l;j++)s=s+(A[O][j]+A[m][j]);

returns;}

(2)intsum2(intA[m][n])

{ints=O,I,j;

for(I=0;I<m;I+=2)

for(j=0;j<n;j+=2)}s+=A[i][j];

for(I=l;I<m;I+=2)

for(j=l；j<n;j+=2)}s+=A[i][j];

returns;}

(3)intsum3(maxixA)

{intI,s;

if(m!=n)printf(4tm!=n’')；

else

{s=0;for(i=0;i<m;i++)s+=A[i|[i];

for(i=0;i<n;i++)s+=A[n-i-l][i];

returns;}

2、#definem3

#definen4

voidminmax(intA[m][n])

{intI,j,have=0;

intmin[m],max[n];

for(I=0;I<m;I++){min[i]=A[i][0];

for(j=l;j<n;j++)if(A[i]|j]<min[i])min[i]=A[i][j];}

for(j=0;j<n;j++){max[j]=A[0][j];

for(I=l;I<m;I++)if(A[i][j]>max[j])max[j]=A[i][j];}

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

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

if(min[i]==max[j]){printf(**(%d,%d):%d\n,,,I,j,A[i][j]);

have=1;)

if(!have)printf(“沒有馬鞍點(diǎn)\n")；

}

該算法由三個(gè)并列的嵌套循環(huán)構(gòu)成，其時(shí)間復(fù)雜度為O(m*n)

第六章：樹與二叉樹

一、選擇題:

IB、2B、3C、4C、5C、6EGBGL7D、8BD、9B、10C、11B、12D、13B、16B、17A、18A、19C、20DE、

21D、22C、23C、24A、25DE、26D、27B、28A、29C、30D、31D、32A、33C、34A、35D、36B、37B、

38C、39C、40B、41B、42B、43C、44B、45D、46B

31.B32.C33.B34.B35.C36.C37.B38.B39.D40.B

二、判斷題

1.x273.J4.V5,x6.V7.x8.x9710.x

11.V12.x13.x14.V15.V16.V17.V18.V19.x20.x

三、填空題：

(1)后繼、任意多個(gè)(2)3,4,6,1,1,2,A,F,G(3)3iJ

(n(kIH1)kklk2kk

(4)n(k-l)+l(5)n,logk--(6)2-l,2,2-+l,2-l(7)k,2-l(8)n/2,n/2+l

(9)n2+l(10)2ln/2,n/2(11)20,1,10(12)n/2(13)2n,n-l,n+l(14)完全Jog2(n+1),最大1n

(15)右(16)可以采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的問題。(17)空樹，

空的二叉樹(18)I,F(19)前序序列為EACBDGF,森林包括一?棵樹(20)中序(21)

2n-l(22)55(23)n+1

補(bǔ)充填空題：

1.層次、根、雙親

2.子孫、祖先

3.2，T

4.2k-1

5.幾？+1

6.最大值、完全

7.[log2rtj+l

8.[_log2zj=L10g2JJ

9.⑴根、[i/2]

(2)左孩子、右孩子、2i

(3)右孩子、2i+l

10.順序、鏈?zhǔn)?/p>

11.根

12.根

13.2n>n-1>n+l

14.99

15.二叉鏈表、三叉鏈表

16.虛結(jié)點(diǎn)

17.7

18.512

19.前序

20.1、n、

21.n-1

22.n-2m+l

23.59

24.5

25.91

26.12

27.8

28.4

29.A、

E,J,K,G,L,O,P,Q,R,N,I、

3、4、5、

J,K、

C

30.不一定、不一定、一定

31.前驅(qū)、唯一路徑

32.n+l、2"

33.21、21'-1

四、附加判斷題：1對(duì)、2對(duì)、3對(duì)、4錯(cuò)、5對(duì)、6錯(cuò)、7錯(cuò)、8對(duì)、9錯(cuò)、10錯(cuò)、11錯(cuò)

五、簡(jiǎn)答題：1一14略

15、解答:

三個(gè)結(jié)點(diǎn)的樹:三個(gè)結(jié)點(diǎn)的二叉樹:

（1）a是根結(jié)點(diǎn)

（2）d,f,g,h,j,k是葉子

（3）g的雙親是c

（4）g的祖先是a,c

（5）e的子孫是i,j,k

（6）f的兄弟是g,h

（7）b的層次是2,j的層次是5

（8）樹的深度是5

（9）樹的度是3

17、證明：設(shè)度為1的結(jié)點(diǎn)數(shù)為m，度為2的結(jié)點(diǎn)數(shù)為明，總分支數(shù)為B,則有

\'2其中總分支數(shù)8=+2?〃2,即

B+l=?12

m+〃]+%=〃

12，解之可得出二根一1

九i+2n2+1=n

二叉鏈衣

123456789101112

ABC0DE00060F

順序存儲(chǔ)

19、解答:

前序序列：ABCDEF

中序序列：CBEFDA

后序序列：CFEDBA

19、解答：

森林的前序序列為：ABDGCEFHIJK

中序序列為：DGBAECIHJKF

23、解答:

哈夫曼編碼為:

2：10000

3：10001

6：1001

7：1010

10：1011

32：11

19：00

21：01

24、解答：前綴式為前序遍歷二叉樹所得到的遍歷序列，即為：一*3+xa/n*xx

后綴式為后序遍歷二叉樹所得到的遍歷序列，即為：3網(wǎng)+*?雙*/-

QA

25、解寫也『吸號(hào)熠學(xué)符號(hào)趣m不為前綴。所以｛00,01,10,11｝,｛0,10,110,111｝是前綴碼,

而在｛0,（3）111+））的市（二）1是11的前綴，所以不是前綴碼。

26、解答：樹Q

??

前序前驅(qū)線索化：后序后繼線索化：中序全線索化：

、NULL^yZ、、本NULL

J;

第七章答案:

一、選擇題

12345678

CABADCDA

91()111213141516

ACAGCDBBDDCBB

1718192021222324

ACDBABADCB

2526272829303132

CBDBDBB

二、判斷題

1.V2.X3.X4.V5.X6.V7.V8.V9.X

三、填空題

1n-L最少13無環(huán)，前馱，所有以它為尾的弧

22e,主對(duì)角線14生成樹

3任意多個(gè)15關(guān)鍵路徑

4416i，j

50,n(n-1)/2,0,n(n-1),n(n-l)/2,n(n-l)172e,e

61,0IS1,0

7119第i列的元素之和、使第i行的元素值為0

8求矩陣第I列非零元素之和20

0、n(n-1)/2>0、n(n-l)

9出度數(shù)，度數(shù)2119、22、9、036789

10221.弧、始、終、邊

Vlv2V3V6v5v4>V]V2V5V4V3V6

11N(n-l),n-l23連通、連通圖

12等于124極大

25n+2e>n>2e

262.n+e、n、e

27第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)、第i個(gè)鏈表中的結(jié)

點(diǎn)數(shù)、i-1

2X深度、廣度

四、簡(jiǎn)答題

1、(1)n條邊(2)n-1條邊

2、根據(jù)鄰接表中表向量的大小確定鄰接矩陣的行列數(shù)；由第I個(gè)頂點(diǎn)指向的單鏈表中結(jié)點(diǎn)j來確定鄰

接矩陣中第I行j列元素為1,其余為0。

3、略

4、圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。

借助于鄰接矩陣容易判斷任意兩個(gè)頂點(diǎn)是否有邊/弧相連，并容易求出頂點(diǎn)的度。對(duì)無向圖，頂點(diǎn)

vi的度是鄰接矩陣中第I行或第j列的元素之和；對(duì)有向圖，第I行的元素之和為頂點(diǎn)vi的出度，第

j列的元素之和為頂點(diǎn)vj的入度。

在無向圖的鄰接表中，第I個(gè)鏈表中表結(jié)點(diǎn)個(gè)數(shù)恰好為頂點(diǎn)vi的度；而在有向圖中，第I個(gè)鏈表

中表結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度。

利用十字鏈表容易求得頂點(diǎn)的出度和入度。

鄰接多重表適合于對(duì)邊進(jìn)行操作，如在遍歷時(shí)對(duì)邊作記號(hào)或在拓?fù)渑判蛑袑?duì)邊進(jìn)行刪除。

5、在AOE網(wǎng)中完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，這條路徑長(zhǎng)度最長(zhǎng)的路

徑叫關(guān)鍵路徑。

其它題答案略。

五、補(bǔ)充應(yīng)用題

1.解答：鄰接矩陣為鄰接表為

-01010'

10011

00011

11100

01100

2.解答：鄰接矩陣為:

"01110-

00000

00010

01000

01100

逆鄰接表為：

3.解答：深度優(yōu)先搜索序列為：V5v4v3v2v,,廣度優(yōu)先搜索序列為：V5V4V2V3V,?

4.解答:

5.解答：（1）

8.解答：(1)匕丫2V3V5V4V6

(2)v1v2v4v5v3v6

(3)

9.解答：利用Prim算法得到的最小生成樹為

利用Kruskal算法得到的最小生成樹為

10.解答：⑴是。

(2)TD(v,)=3OD(V])=2ID(i，|)=l,

TD(V2)=2OD(V2)=1ID(V2)=1

TD(v3)=2OD(v3)=1ID(匕)=1,TD(V4)=3OD(V4)=1ID(V4)=2

（3）鄰接矩陣為：鄰接表為:

逆鄰接表為:

11.解答：DFS遍歷采用棧暫存結(jié)點(diǎn)，BFS遍歷采用隊(duì)列暫存結(jié)點(diǎn)。

要求連通圖的生成樹高度最小時(shí)采用BFS遍歷。

DFS生成森林為：BFS生成森林為:

選

集合S

頂距離

初值(}2150088

1{1}21581232

2{1,2}5152732

3{1,2,5)32725

4{1,2,5,3}627

5{125,3,6}

4

6{125,3,6,4}

13.解答：拓?fù)湫蛄袨関5v6v1v0v2v3v4

14.解答：(1)

頂點(diǎn)vevl

100

234

322

466

567

688

(2)最少需要的單位時(shí)間為8。

(3)關(guān)鍵路徑為(1,3,4,6)

V

關(guān)鍵活動(dòng)為e2、e5>e7

15.解答：?

13

G

深度優(yōu)先遍歷序列為:12345；廣度優(yōu)先遍歷序列為：12345；

最小生成樹為：

@-7

(2)還需增加2條邊

00009500CO95

10036D")=10036

00200632006

000080000CO800

001195001195

1003610036

。⑵=。⑶=

3200632006

11108001110800

18.解答:

頂點(diǎn)vevl

V00

A119

B623

C1725

D318

E2533

F48

G33

H1313

I17

J3131

K2222

W4343

活動(dòng)e11-e

ai01818

a201717

a301515

044

關(guān)鍵路徑為：VGHKJW

a000

關(guān)鍵活動(dòng)為：35'314'3|9'321'^225

36066

11918

a7

17

a8623

18

a9315

aio32522

an42521

312484

at32219

a14330

ai5176

ai617258

31713218

^18132714

a1913130

32025338

^2122220

22231310

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

1.寫出將一個(gè)無向圖的鄰接表轉(zhuǎn)換成鄰接矩陣的算法。

2.寫出根據(jù)有向圖的鄰接表建立有向圖的逆鄰接表的算法。

3.試以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，分別寫出連通圖的深度優(yōu)先和廣度優(yōu)先搜索算法。

4.G為一n個(gè)頂點(diǎn)的有向圖，其存儲(chǔ)結(jié)構(gòu)分別為：

(1)鄰接矩陣；

(2)鄰接表。

請(qǐng)寫出相應(yīng)存儲(chǔ)結(jié)構(gòu)上的計(jì)算有向圖G出度為0的頂點(diǎn)個(gè)數(shù)的算法。

5.試寫一個(gè)算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)叫到頂點(diǎn)苗的路徑

假設(shè)分別基于下述策略：圖的深度優(yōu)先搜索；圖的廣度優(yōu)