數(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、時間復(fù)雜度和空間復(fù)雜度

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

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

10、沒有、一個11、一個、一個、后繼、任意個12、任意個13、物理

14、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項15、結(jié)點、記錄、元素、頂點16、順序存儲、鏈?zhǔn)酱鎯Α?/p>

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

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

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

、判斷題

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

四、計算題

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ī)程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)

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

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

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

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

構(gòu)是數(shù)據(jù)元素及其之間的關(guān)系在計算機(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、插入和刪除首元素時不必進(jìn)行特殊處理

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

11q->prior=p;

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

13、必定，不一定

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

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

16、線性

17、線性、長度

18、p-*next=NULL;

三、判斷題

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

四、簡答題

1、宜采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為它使線性表的插入和刪除操作的時間復(fù)雜度為O(1),兩頁

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7、解答：應(yīng)選用鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為順序表是靜態(tài)存儲結(jié)構(gòu)，只能預(yù)先分配存儲單元，不

能隨著線性表長度的改變而變化。而鏈表則可根據(jù)需要動態(tài)的申請空間，因此適用于動

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

8、解答：應(yīng)該用順序存儲結(jié)構(gòu)。因為順序存儲結(jié)構(gòu)存取元素操作的時間復(fù)雜度為0(1)。

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

用來存儲指數(shù)。

⑶c—

四、設(shè)計題

1、

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

{〃采用順序存儲結(jié)構(gòu)實現(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、提示：兩個表的公共元素指的是既存在于A表中，也存在于B表中的元素，為了操作方

便，先讓單鏈表C帶有一?個頭結(jié)點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é)點

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

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

后一個結(jié)點

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

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é)點

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、線性；任何；棧頂；隊尾；隊首3、srack

4、HS==NULL5、存入元素，移動棧頂指針6、移動棧頂指針，取出元素

7、1和n；1和18、先取出元素，后移動對尾指針9、前一個位置

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

三、簡答題

1、利用棧的“后進(jì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,棧頂由低向高移動；將s2的棧底置為m-1,棧頂由高向低移動。

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

1

22

333

4444

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

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

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

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

7、解答：

序號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、解答：該遞歸過程不能簡單的改寫成一個遞推形式的過程，從它的執(zhí)行過程可見，其輸

出的順序恰好和輸入相反，則必須用一個輔助結(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è)計

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、本題實質(zhì)上就是簡答題5。

Queueinverse(QueueQe)

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

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

return(Qe);}

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

typedefstructLnode{

ElemTypedata;

StructLnode*next;

}Lnode,*LinkNode;

根據(jù)單鏈表的特點，實現(xiàn)隊列的5種運算的函數(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、零個字符的串零3、，GOODBYE!，4、兩個串的長度相

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

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

7、匹配

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

四、簡答題

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è)計題

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時)llf(k)=max(f(k-l),a[k])(k>0時)

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

2、1056

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

4、深度

5、Head(L)=();Tail(L)=(());L的長度為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

四、計算題

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

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

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

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

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

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

4、四維數(shù)組A的按行優(yōu)先順序在內(nèi)存中的存儲次序為：A0000,AOOOKA0010,A001K

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

AHU；按列優(yōu)先存儲順序為: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時)和k=(j-l)(2n-j+2)/2+I-j+l(I>j時)

11、略

四、簡答題

1、廣義表是線性表的推廣，形式上定義為LS=(ai,a2,國可以是單個元素，也可

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

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

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

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

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è)計題

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(“沒有馬鞍點\n")；

}

該算法由三個并列的嵌套循環(huán)構(gòu)成，其時間復(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)后繼、任意多個(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)可以采用二叉樹的存儲結(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é)點

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對、2對、3對、4錯、5對、6錯、7錯、8對、9錯、10錯、11錯

五、簡答題：1一14略

15、解答:

三個結(jié)點的樹:三個結(jié)點的二叉樹:

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

（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é)點數(shù)為m，度為2的結(jié)點數(shù)為明，總分支數(shù)為B,則有

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

B+l=?12

m+〃]+%=〃

12，解之可得出二根一1

九i+2n2+1=n

二叉鏈衣

123456789101112

ABC0DE00060F

順序存儲

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、解寫也『吸號熠學(xué)符號趣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,主對角線14生成樹

3任意多個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個鏈表中的結(jié)點數(shù)、第i個鏈表中的結(jié)

點數(shù)、i-1

2X深度、廣度

四、簡答題

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

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

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

3、略

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

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

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

j列的元素之和為頂點vj的入度。

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

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

利用十字鏈表容易求得頂點的出度和入度。

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

5、在AOE網(wǎ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é)點，BFS遍歷采用隊列暫存結(jié)點。

要求連通圖的生成樹高度最小時采用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)

頂點vevl

100

234

322

466

567

688

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

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

V

關(guān)鍵活動為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.解答:

頂點vevl

V00

A119

B623

C1725

D318

E2533

F48

G33

H1313

I17

J3131

K2222

W4343

活動e11-e

ai01818

a201717

a301515

044

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

a000

關(guān)鍵活動為：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è)計題

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

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

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

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

(1)鄰接矩陣；

(2)鄰接表。

請寫出相應(yīng)存儲結(jié)構(gòu)上的計算有向圖G出度為0的頂點個數(shù)的算法。

5.試寫一個算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點叫到頂點苗的路徑

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