2010年计算机专业统考试题数据结构

第七章图基本内容图的定义、概念、术语及基本操作图的存储结构，特别是邻接矩阵和邻接表图的深度优先和广度优先遍历图的应用（连通分量、最小生成树、拓扑排序、关键路径、最短路径）基本内容图的遍历：深度优先和广度优先遍历在连通图中，主函数一次调用深度（广度）优先遍历过程，可遍历全部顶点，可以用此方法求连通分量的个数，能够画出遍历中形成的深度（广度）优先生成树或生成森林。深度优先遍历intvisited[max];for(i=1;i=max;i++)visited[i]=0;voiddfs(AdjlistG,inv){inti;structedgenode*p;visited[v]=1;printf(“%d”,G[v].data);p=G[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)dfs(G,p-adjvex);p=p-nextarc;}}广度优先遍历intvisited[max],queue[max];voidbfs(AdjlistG,intv){intfront=0,rear=0,v1;structedgenode*p;for(i=1;i=max;i++)visited[i]=0;visited[v]=1;printf(“%d”,G[v].data);queue[rear]=v;rear++;while(front!=rear){v1=queue[front];p=G[v1].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){vistited[p-adjvex]=1;printf();queue[rear]=p-adjvex;rear++;}p=p-nextarc;}}}深度优先遍历非递归voiddfs(AdjlistG,intv){structArcnode*stack[],*p;intvisited[max],top=0;for(i=1;i=max;i++)visited[i]=0;visited[v]=1;printf(“%d’’,v);p=G[v].firstarc;while(top0||p!=NULL){while(p!=NULL)if(visited[p-adjvex]!=0)p=p-nextarc;else{visited[p-adjvex]=1;printf(“%d”,p-adjvex);top++;stack[top]=p;p=G[p-adjvex].firstarc;}if(top0）{top--;p=stack[top];p=p-nextarc;}}}最小生成树最小代价生成树连通图的最小生成树通常不是唯一的，但最小生成树边上的权值之和是唯一的，掌握Prim算法和Kruskal算法，能够手工分步模拟生成树的过程。拓扑排序拓扑排序是在有向图上对入度（先、后）为零的顶点的一种排序，通常结果不唯一。用拓扑排序和深度优先遍历都可以判断图是否存在回路。掌握手工模拟算法关键路径关键路径是在拓扑有序的前提下求出的从源点到汇点的最长路径。减少关键活动时间可以缩短工期，是指该活动为所有关键路径所共有，且减少到尚未改变关键路径的前提下才有效。手工模拟算法过程。最短路径从单源点到其他顶点，以及各个顶点间的最短路径问题，掌握Dijkstra和Floyd算法，并能手工模拟，掌握用求最短路径来解决的应用问题。1、输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表StatusBuild_AdjList(ALGraph&G){InitALGraph(G);scanf(“%d”,&v);if(v0)returnERROR;G.vexnum=v;scanf(%d,&a);if(a0)returnERROR;G.arcnum=a;for(m=0;mv;m++)G.vertices[m].data=getchar();for(m=1;m=a;m++){t=getchar();h=getchar();if((i=LocateVex(G,t))0)returnERROR;if((j=LocateVex(G,h))0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q-nextarc;q=q-nextarc);q-nextarc=p;}p-adjvex=j;p-nextarc=NULL;}returnOK;}2、在邻接表表示的有向图G上插入边(v,w)statusInsert_Arc(ALGraph&G,charv,charw){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q-nextarc;q=q-nextarc);if(q-adjvex==j)returnERROR;/*边已经存在q-nextarc=p;}G.arcnum++;returnOK;}3、深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0intvisited[MAXSIZE];intexist_path_DFS(ALGraphG,inti,intj){if(i==j)return1;else{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;if(!visited[k]&&exist_path_DFS(k,j))return1;}}}4、判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk){if(i==j&&k==0)return1;elseif(k0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){l=p-adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;}visited[i]=0;/*本题允许曾经被访问过的结点出现在另一条路径中}return0;}5、求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度intpath[MAXSIZE],visited[MAXSIZE];/*暂存遍历过程中的路径intFind_All_Path(ALGraphG,intu,intv,intk){path[k]=u;visited[u]=1;if(u==v){printf(Foundonepath!\n);for(i=0;path[i];i++)printf(%d,path[i]);}elsefor(p=G.vertices[u].firstarc;p;p=p-nextarc){l=p-adjvex;if(!visited[l])Find_All_Path(G,l,v,k+1);}visited[u]=0;path[k]=0;}6、求一个有向无环图中最长的路径intmaxlen,path[MAXSIZE];/*数组path用于存储当前路径intmlp[MAXSIZE];/*数组mlp用于存储已发现的最长路径voidGet_Longest_Path(ALGraphG){maxlen=0;FindIndegree(G,indegree);for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++)visited[j]=0;if(!indegree[i])DFS(G,i,0);/*从每一个零入度结点开始深度优先遍历}printf(LongestPath:);for(i=0;mlp[i];i++)printf(%d,mlp[i]);/*输出最长路径}voidDFS(ALGraphG,inti,intlen){visited[i]=1;path[len]=i;if(lenmaxlen&&!G.vertices[i].firstarc)/*新的最长路径{for(j=0;j=len;j++)mlp[j]=path[j];/*保存下来maxlen=len;}else{for(p=G.vertices[i].firstarc;p;p=p-nextarc){j=p-adjvex;if(!visited[j])DFS(G,j,len+1);}}path[i]=0;visited[i]=0;}6、设无向图G已用邻接表结构存储，试用广度优先算法求图的各连通分量。voidbfscom(AdjlistG){intcount=0;for(i=1;i=n;i++)visited[i]=0;for(i=1;i=n;i++)if(visited[i]==0){printf(“第%d个连通分量”,++count);bfs(G,i);}}7、输出有向无环图形式表示的表达式的逆波兰式voidNiBoLan_DAG(ALGraphG){FindIndegree(G,indegree);for(i=0;iG.vexnum;i++)if(!indegree[i])r=i;PrintNiBoLan_DAG(G,r);}voidPrintNiBoLan_DAG(ALGraphG,inti){c=G.vertices[i].data;if(!G.vertices[i].firstarc)printf(“%c”,c);/*原子else/*子表达式{p=G.vertices[i].firstarc;PrintNiBoLan_DAG(G,p-adjvex);PrintNiBoLan_DAG(G,p-nextarc-adjvex);printf(%c,c);}}8、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法。分析：每个顶点到其余各顶点的最短路径中最长的有n条，这n条中最短的一条。9、设顶点a,b,c,d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离；①求每个村庄到其它村庄的最短距离；②乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。分析：每个顶点到其余各顶点最短路径之和最短的一个。10、欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）试用一种数据结构表示地图上各国相邻的关系。（2）描述涂色过程的算法。（不要求证明）。分析：地图涂色问题可以用“四染色”定理.将地图上的国家编号（1~n）从编号1开始逐一涂色，对每个区域用1色、2色、3色、4色依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色入栈；否则，用下一颜色。若1~4色都与相邻某区域重色，则需出栈回溯，修改栈顶区域颜色。用邻接矩阵描述地图上国家间的关系，n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，矩阵相应位置为1，否则为0。用栈记录染色结果，栈的下标值为区域号，元素值为色数。voidmapcolor(AdjMatrixC){ints[];s[1]=1;i=2;j=1;