数据结构以及应用算法教程参考答案（11）第7章图

关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 第7章 图 7.1 解：(1) ID(1)=3 OD(1)=0 ID(2)=2 OD(2)=2 ID(3)=1 OD(3)=2 ID(4)=1 OD(4)=3 ID(5)=2 OD(5)=1 ID(6)=2 OD(6)=3 (2) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 (3)

(4) (5) 有三个连通分量1、5、2346

7.2 解：k=1，说明了各结点之间的相互连通关系；k=2说明了结点之间按路径长度为2的相互连通关系；…。 7.3 解：邻接表：

邻接多重表： 深度优先搜索的顺序为 1 5 6 4 3 2 广度优先搜索的顺序为 1 5 6 3 2 4， 15 16 13 12 24

7.14 解： Status CreateAG(ALGraph &G) { int n,e,k,i,j; cout<<“请输入顶点数：”; cin>>n; cout<<“请输入边数：”; cin>>e; G.vernum=n; G.arcnum=e;

// 建立顶点数组 for(k=0;k<G.vernum;k++){ cout<<"请输入顶点信息："; cin>>G.vertices[k].data; G.vertices[k].firstarc=NULL; } // 建立邻接表 VertexType v1,v2; ArcNode *p,*q; for(k=0;k<G.arcnum;k++){ cout<<"请输入弧的始点和终点信息，中间用空格分开:"; cin>>v1>>v2; i=LocateVex(G,v1); if(i<0 || i>G.vernum-1) return ERROR; j=LocateVex(G,v2); if(j<0 || j>G.vernum-1) return ERROR; if(i==j) return ERROR; p=new ArcNode; if(!p) return ERROR; p->adjvex=j; p->nextarc=NULL; q=G.vertices[i].firstarc; if(!q) G.vertices[i].firstarc=p; else{ while(q->nextarc) q=q->nextarc; // 指针定位于邻接表的尾结点 q->nextarc=p; } } return OK;

} int LocateVex(ALGraph& G,VertexType v) { int i=0; while(G.vertices[i].data!=v&&i<G.vernum) i++; if(G.vertices[i].data==v) return i; else return -1; } 7.15 解 第9章 查找 9.1 解：(1)相同，平均查找长度为 (2)相同，平均查找长度为 (3)对于有序顺序表，平均查找长度为，对于无序顺序表，则为。 9.2 解：查找e的过程如下：

9.3 解：

9.4 解：

9.5 解：

9.7 解：

9.9 解：(1)

(3)