数据结构课后练习题参考答案

数据结构习题参考答案

第一章:

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

B10、A11、D

二、1、线性、树型和图型，非线性2、集合、线性、树型、图形结构

3、有穷性、确定性、可行性、输入和输出4、时间复杂度和空间复杂度

5、一对一、一对多、多对多6、O(n)7、O(m*n)8、逻辑关系

9、数据的逻辑结构、数据的存储结构、对数据施加的操作

10、没有、一个11、一个、一个、后继、任意个12、任意个13、物理

14、数据、数据元素、数据项15、结点、记录、元素、顶点16、顺序存储、链式存储、

索引存储、散列存储17、正确性、可读性、健壮性、高效性18、时间复杂度、空

间复度、计算量、存储量19、问题规模20、1、log2n.n、n\2"、不可行21、设

计、实现22、数据元素23、数学模型

、判断题

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、解答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并

被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数

据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系

的数据元素的集合。数据对象是性质相同的数据元素的集合。

7、解答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存

储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结

构是数据元素及其之间的关系在计算机中的表示。

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、插入和删除首元素时不必进行特殊处理

10、其直接前趋结点的链域

11q->prior=p;

12、前趋结点，后继结点

13、必定，不一定

14、结点、第一个、最后一个、位置、前驱、后继

15、前驱、前驱、后继、后继

16、线性

17、线性、长度

18、p-*next=NULL;

三、判断题

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

四、简答题

1、宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为O(1),两页

序存储结构的为O(n),

2、首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表

的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线性表的数据元素，

其作用是为了对链表进行操作时.，可以对空表、非空表的情况以及对首元结点进行统一

的处理。头指针是指向链表第一个结点(头结点或首元结点)的指针。若链表中附设头

结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。

这三个概念对单链表、双向链表和循环链表均适用。

3、在等概率前提下，平均每插入一个元素需要移动的元素个数为(0+1+2+…+n)/(n+l)=n/2。

若元素插在ai与ai+1之间(0<=i<=n-l)的概率为2(n-i)/(n(n+l)),则平均每插入一个元

素所要移动的元素个数为：(2n+l)/3

4、解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，

但设置尾指针时，若在表尾进行插入或删除操作时可在0(1)时间内完成，同样在表头进

行插入或删除操作时也可在0(1)时间内完成。但若设置的是头指针，表尾进行插入或删

除操作，需要遍历整个链表，时间复杂度为0(n)。

5、解答：能删除。双链表上删除p所指向的结点的时间复杂度为0(1),单循环链表上删除

P所指向的结点的时间复杂度为0(n)。

6、解答：如果长度大于1,则将首元结点删除并插入到表尾。

7、解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不

能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动

态变化表长的线性表。

8、解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为0(1)。

9、解答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个

用来存储指数。

⑶c—

四、设计题

1、

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

{〃采用顺序存储结构实现

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带有一•个头结点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〃找到元素值相同的结点

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

s.data=p.data;r.next=s;r=s;〃把s结点链到c的末尾，r始终指向链表C的最

后一个结点

while(p.data==p.next.data)p=p.next;〃跳过相同的值的结点

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链表的头结点

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、先进后出先进先出2、线性；任何；栈顶；队尾；队首3、srack

4、HS==NULL5、存入元素，移动栈顶指针6、移动栈顶指针，取出元素

7、1和n；1和18、先取出元素，后移动对尾指针9、前一个位置

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

三、简答题

1、利用栈的“后进先出”的特点,共有如下5种情况:

A进A出B进B出C进C出产生输出序列ABC

A进A出B进C进C出B出产生输出序列ACB

A进B进B出A出C进C出产生输出序列BAC

A进B进B出C进C出A出产生输出序列BCA

A进B进C进C出B出A出产生输出序列CBA

2、（1）利用栈s将数组a中的元素逆置。（2）利用栈t将栈s中的数据元素e删除。

3、将si栈的栈底置为0,栈顶由低向高移动；将s2的栈底置为m-1,栈顶由高向低移动。

4、print(4)的输出结果为：

1

22

333

4444

5、算法的功能：利用栈的辅助，将队列中的数据元素进行逆置。

6、当元素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、解答：该递归过程不能简单的改写成一个递推形式的过程，从它的执行过程可见，其输

出的顺序恰好和输入相反，则必须用一个辅助结构保存其输入值，然后逆向取之，所以用栈

最为合适。

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

)

)

四、算法设计

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)非递归函数如下：

intgcd2(intm,intn)

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

⑶略

3、本题实质上就是简答题5。

Queueinverse(QueueQe)

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

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

return(Qe);}

4、定义单链表结点类型如下：

typedefstructLnode{

ElemTypedata;

StructLnode*next;

}Lnode,*LinkNode;

根据单链表的特点，实现队列的5种运算的函数如下：

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、两个串的长度相

等且对应位置字符相同5、顺序存储方式和链接存储方式

6、有一个或多个空格组成的串、串中空格字符的个数

7、匹配

8、交换律、结合律

四、简答题

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

五、设计题

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、最大整数的递归定义为：f(k)=a|O](k=O时)llf(k)=max(f(k-l),a[k])(k>0时)

最小整数的递归定义为：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)

[怨当E

H卜”+l)+i,当『<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)数组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、四维数组A的按行优先顺序在内存中的存储次序为：A0000,AOOOKA0010,A001K

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

AHU；按列优先存储顺序为: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,国可以是单个元素，也可

以是广义表，并分别称为广义表的原子和子表。

主要区别是：线性表中元素只能是单个元素，而广义表中元素可以是单个元素，

也可以是广义表；线性表中各元素是独立的，而广义表中元素可以为其他表或子表共享，特

别地，广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。

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)),())

五、设计题

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")；

}

该算法由三个并列的嵌套循环构成，其时间复杂度为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)可以采用二叉树的存储结构并利用二叉树的已有算法解决树的问题。(17)空树，

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

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

补充填空题：

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.顺序、链式

11.根

12.根

13.2n>n-1>n+l

14.99

15.二叉链表、三叉链表

16.虚结点

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.前驱、唯一路径

32.n+l、2"

33.21、21'-1

四、附加判断题：1对、2对、3对、4错、5对、6错、7错、8对、9错、10错、11错

五、简答题：1一14略

15、解答:

三个结点的树:三个结点的二叉树:

（1）a是根结点

（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、证明：设度为1的结点数为m，度为2的结点数为明，总分支数为B,则有

\'2其中总分支数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网+*«双*/-

QA

25、解写也『吸号熠学符号趣m不为前缀。所以｛00,01,10,11｝,｛0,10,110,111｝是前缀码,

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

26、解答：树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无环，前驮，所有以它为尾的弧

22e,主对角线14生成树

3任意多个15关键路径

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出度数，度数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个链表中的结点数、第i个链表中的结

点数、i-1

2X深度、广度

四、简答题

1、(1)n条边(2)n-1条边

2、根据邻接表中表向量的大小确定邻接矩阵的行列数；由第I个顶点指向的单链表中结点j来确定邻

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

3、略

4、图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。

借助于邻接矩阵容易判断任意两个顶点是否有边/弧相连，并容易求出顶点的度。对无向图，顶点

vi的度是邻接矩阵中第I行或第j列的元素之和；对有向图，第I行的元素之和为顶点vi的出度，第

j列的元素之和为顶点vj的入度。

在无向图的邻接表中，第I个链表中表结点个数恰好为顶点vi的度；而在有向图中，第I个链表

中表结点个数只是顶点vi的出度。

利用十字链表容易求得顶点的出度和入度。

邻接多重表适合于对边进行操作，如在遍历时对边作记号或在拓扑排序中对边进行删除。

5、在AOE网中完成工程的最短时间是从开始点到完成点的最长路径的长度，这条路径长度最长的路

径叫关键路径。

其它题答案略。

五、补充应用题

1.解答：邻接矩阵为邻接表为

-01010'

10011

00011

11100

01100

2.解答：邻接矩阵为:

"01110-

00000

00010

01000

01100

逆邻接表为：

3.解答：深度优先搜索序列为：V5v4v3v2v,,广度优先搜索序列为：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遍历采用栈暂存结点，BFS遍历采用队列暂存结点。

要求连通图的生成树高度最小时采用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.解答：拓扑序列为v5v6v1v0v2v3v4

14.解答：(1)

顶点vevl

100

234

322

466

567

688

(2)最少需要的单位时间为8。

(3)关键路径为(1,3,4,6)

V

关键活动为e2、e5>e7

15.解答：?

13

G

深度优先遍历序列为:12345；广度优先遍历序列为：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

关键路径为：VGHKJW

a000

关键活动为：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

六、算法设计题

1.写出将一个无向图的邻接表转换成邻接矩阵的算法。

2.写出根据有向图的邻接表建立有向图的逆邻接表的算法。

3.试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。

4.G为一n个顶点的有向图，其存储结构分别为：

(1)邻接矩阵；

(2)邻接表。

请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。

5.试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点叫到顶点苗的路径

假设分别基于下述策略：图的深度优先搜索；图的广度优