数据结构课后习题答案（修订版）(6)

3.(3)．答：是连通图。因为每一对顶点间都有路径存在，所以该图是连通的。 深度优先搜索遍历：A,B,D,C,F,H,E 广度优先搜索遍历：A,B,D,C,E,F,H

3.(4)．答：①普里姆算法构造过程如下：

B A D B A D B A D C C C E G A B C D E G F E H G A F B C D B F E C D F B A E H G F E H G H G A F E C H G H E C G B A D ②

F H D F H B A D C E G A B C D E G F H F H B A D C E G A B C D E G F H F H B A D C E G A B C D E G F H F H B A D C E G A B C D E G F H F H

3.(5)．答： ①

(1)各结点的最早开始时间 VE(1)=0

VE(2)=VE(1)+dut(<1,2>)=0+8=8 VE(3)=VE(1)+dut(<1,3>)=0+6=6

VE(4)=Max{VE(2)+dut(<2,4>)+VE(3)+dut(<3,4>)}=Max{11,16}=16 VE(5)=VE(1)+dut(<1,5>)=0+7=7

VE(7)=Max{VE(3)+dut(<3,7>),VE(5)+dut(<5,7>)}=Max{15,16}=16 VE(6)=VE(4)+dut(<4,6>)=16+4=20

VE(8)=Max{VE(5)+dut(<5,8>),VE(7)+dut(<7,8>)}=Max{20,18}=20

VE(9)=Max{VE(4)+dut(<4,9>),VE(7)+dut(<7,9>),VE(8)+dut(<8,9>)}=Max{35,24,26}=35 VE(10)=Max{VE(6)+dut(<6,10>),VE(9)+dut(<9,10>)}=Max{34,45}=45 （2）各结点的最迟发生时间 VL(10)=VE(10)=45

VL(9)=VL(10)-dut(<9,10>)=35 VL(8)=VL(9)-dut(<8,9>)=29

VL(7)=Min{VL(8)-dut(<7,8>),VL(9)-dut(<7,9>)}=Min{27,27}=27 VL(6)=VL(10)-dut(<6,10>)=31

VL(5)=Min{VL(7)-dut(<5,7>),VL(8)-dut(<5,8>)}=Min{18,16}=16 VL(4)=Min{VL(6)-dut(<4,6>),VL(9)-dut(<4,9>)}=Min{27,16}=16 VL(3)=Min{VL(4)-dut(<3,4>),VL(7)-dut(<3,7>)}=Min{6,18}=6 VL(2)=VL(4)-dut(<2,4>)=13

VL(1)=Min{VL(2)-dut(<1,2>),VL(3)-dut(<1,3>),VL(5)-dut(<1,5>)}=Min{5,0,9}=0

根据各结点的最早开始时间和最迟发生时间计算出各活动的最早开始时间和最迟开始时间 E()=0 L()=5 E()=0 L()=0 E()=0 L()=9 E()=8 L()=13 E()=6 L()=6 E()=6 L()=16 E()=7 L()=16 E()=7 L()=16 E()=16 L()=27 E()=16 L()=16 E()=16 L()=27 E()=16 L()=27 E()=20 L()=29 E()=20 L()=31 E()=35 L()=35 ②完成整个工程的最短时间是45

③网中的关键活动：，，， 四．(1)答：

#define maxnode 30 #include typedef int elemtype typedef struct arc{ int adjvertex;

struct arc * nextarc; }arctype;

typedef struct{

elemtype vertex; arctype * firstarc; }vertextype;

typedef vertextype adjlisttype[maxnode]; main() {

int I,j,n,e,k; int v1,v2; arctype * q;

adjlisttype graph;

printf(“\\n输入图中顶点的个数n和边数e：\\n”); scanf(“%d%d”,&n,&e);

printf(“\\n输入图中顶点的数据：\\n”); for(k=0;k

scanf(“%d”,&graph[k].vertex); graph[k].firstarc=NULL; }

printf(\\n输入图中的各边，次序为弧尾编号，弧头号编号：\\n”); for(k=0;k

scanf(“%d%d”,&v1,&v2); I=locvertex(graph,v1); j=locvertex(graph,v2);

q=(arctype *)malloc(sizeof(arctype)); q->adjvertex=j;

q->nextarc=graph[I].firstarc; graph[I].firstarc=q; } }

(2)．答：

#define vtxnum 256 struct arctype{ int tailvex; int headvexp;

struct arctype * hlink;

struct arctype * tlink; infotype * info; }arctype;

struct vertextype{ elemtype vertex;

struct arctype * firstin; struct arctype * firstout; }vertextype; struct{

vertextype xlist[vtxnum]; int vexnum; int arcnum; }

typedef vertextype cross[maxnode]; creatgraph() {

int I,j,k,n,e; int v1,v2; arctype * p; cross graph;

printf(“\\n输入顶点数据n和弧数e:\\n”); scanf(“%d%d”,&n,&e); for(k=0;k

scanf(“%d”,&graph[k].vertex); graph[k].firstin=NULL; graph[k].firstout=NULL; }

/*输入弧并将相应弧插入到链表中。*/ for(k=0;k

scanf(“%d%d”,&v1,&v2,&w); I=locvertex(graph,v1); j=locvertex(graph,v2);

p=(arctype *)malloc(sizeof(arctype)); p.tailvex=j; p.headvex=I;

p->tlink=graph[I].firstout; p->hlink=graph[j].firstin; p->info=w;

graph[I].firstout=p; graph[j].firstin=p; }

}

(3)答：

int indegree(adjlist adj,int n,int v) {

int I,j,degree; edgenode *p; for(I=0;I

p=adj[I].link; while(p!=NULL) {

if(p->adjvex==v) degree++; p=p->next; } }

return degree; }

void printin(adjlist adj,int n) {

int I,degree;

printf(“The indegree are:\\n”); for(I=0;I

degree=indegree(adj,n,I);

printf(“(%d,&d)”,I,degree);}}

习题九答案

1. 答案：(1) ╳(2) ╳(3)√(4) √(5) √(6) ╳(7) √(8) ╳ 2. 答案： （1）（A） 1（B） 1（C） 5（D） 3 （2）（A） 2（B） 4（C） 7 （3）（A） 4

3.(1)

#define Max 100

typedef char InfoType; typedef struct{ int key;

InfoType otherinfo; }NodeType;

typedef NodeType SeqList[Max+1]; int SeqSearch(SeqList R,int key)