){?inti;?i=H(R.key);?if(H[i]==NULL) H[i]=R;else?{ while(H[i]!=NULL) { i=(i+1)%(m+1); } H[i]=R;?}}第七章一、基本知识题1.图的逻辑结构特点是什么?什么是无向图和有向图?什么是子图?什么是网络?答:图是比树更为复杂的一种非线性数据结构,在图结构中,每个结点都可以和其它任何结点相连接。无向图:对于一个图G,若边集合E(G)为无向边的集合,则称该图为无向图。有向图:对于一个图G,若边集合E(G)为有向边的集合,则称该图为有向图。子图:设有两个图G=(V,E)和G’=(V’,E’),若V(G’)是V(G)的子集,且E(G’)是E(G)的子集,则称G’是G的子图(Subgraph)。网络:有些图,对应每条边有一相应的数值,这个数值叫做该边的权。边上带权的图称为带权图,也称为网络。2.什么是顶点的度?什么是路径?什么是连通图和非连通图?什么是非连通图的连通分量?答:顶点的度:图中与每个顶点相连的边数,叫该顶点的度。在一个图中,若从某顶点Vp出发,沿一些边经过顶点V1,V2,…,Vm到达,Vq,则称顶点序列(Vp,V1,V2,…,Vm,Vq)为从Vp到Vq的路径。在无向图中,如果从顶点Vi到顶点Vj之间有路径,则称这两个顶点是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的连通分量:非连通图的每一个连通的部分叫连通分量。3.给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。答:图G所对应的邻接矩阵如下:图G所对应的邻接表如下:图254.假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。答:(a)所对应的无向图如下图(a)所示,(b)所对应的有向图如下图(b)所示:5.5.分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。
全文预览
