1. 图的存储结构——所存储的信息有哪些
一、邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。
设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：
（1）如果G是无向图，则：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向图，则：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是带权无向图，则：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是带权有向图，则：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：带权图和不带权图表示的元素类型不同。
带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。
用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
如：
邻接矩阵的特点如下：
（1）图的邻接矩阵表示是唯一的。
（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。
（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。
（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。
（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。
（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
邻接矩阵的数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵表示类型
二、 邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。
其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。
表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息
} ArcNode; //边表节点类型
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //完整的图邻接表类型
邻接表的特点如下：
（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。
（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。
（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。
（1）设计一个将邻接矩阵转换为邻接表的算法；
（2）设计一个将邻接表转换为邻接矩阵的算法；
（3）分析上述两个算法的时间复杂度。
解：
（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。
void MatToList(MGraph g，ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{ int i，j，n=g.n; ArcNode *p; //n为顶点数
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //给所有头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//创建节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//将*p链到链表头
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。
2. 图的存储结构是什么
由于图的结构比较复杂，任意两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。这一点同其他数据结构（如线性表、树）不同。考虑图的定义，图是由顶点和边组成的，所以，分别考虑如何存储顶点和边。图常用的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
3. 数据结构：画出下图的邻接矩阵存储结构
我定义一个int型二维数组 G[5][5].
点a，b,c,d分别定义编号为1,2,3,4
G[u][v]的值为零 则有向边(u,v)不联通
若值为1则有向边(u,v)联通
又因为在c,c ,java中 数组的范围是从0开始的
为了使用方便 我们不使用下标为0的数组元素
因为有四个点 所以我们定义一个5x5的二维数组
矩阵数据如下
00000
00110
00000
00001
01000
其中 G[1][2] G[1][3]G[3][4]G[4][1]的值为一
4. 邻接矩阵的表示法
在图的邻接矩阵表示法中：
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
图的矩阵
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
【例】
下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。
网络矩阵
若G是网络，则邻接矩阵可定义为：
其中：
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。
图的邻接矩阵存储结构形式说明
#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct{
VextexType vexs[MaxVertexNum] //顶点表
EdeType edges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表
int n，e; //图中当前的顶点数和边数
}MGragh;
注意：
① 在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)。
② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
④邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
⑤建立无向网络的算法。
void CreateMGraph(MGraph *G)
{//建立无向网的邻接矩阵表示
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < n;i++) //读入顶点信息，建立顶点表
{
G->vexs=getchar();
}
for(i = 0;i < G->n;i++)
{
for(j = 0;j <G->n;j++)
{
G->edges[i][j] = 0; //邻接矩阵初始化
}
}
for(k = 0;k < G->e;k++)
{//读入e条边，建立邻接矩阵
scanf("%d%d%d"，&i，&j，&w); //输入边(v i ,v j )上的权w
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}//CreateMGraph
该算法的执行时间是0(n+n 2 +e)。由于e
根据图的定义可知，图的逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
Matlab表达N=4;//图中的节点数目
dag=zeros(N,N);//邻接矩阵初始化，值均为0
C=1;S=2;R=3;
W=4;//制定各节点编号
dag(C,[RS])=1;//有两条有向边：C->R,C->S
dag(R,W)=1;//有向边：R->W
dag(S,W)=1;//有向边：S->W
5. 线性的数据结构可以顺序存储也可以链接存储
三、 判断题（每小题1分,共10分,错误打×,正确打√）
1、线性的数据结构可以顺序存储,也可以链接存储.非线性的数据结构只能链接存储.( )
2、单链表从任何一个结点出发,都能访问到所有结点.( )
3、在只有度为0和度为k的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1 ( )
4、将一棵树转换成二叉树后,根结点没有左子树( )
5、邻接表表示无向图,邻接表中的结点个数是无向图中边数的2倍.( )
6、 用邻接矩阵表示图所用的存储空间大小与图的边数成正比.（ ）
7、负载因子（装填因子）是散列表的一个重要参数,它反映散列表的装满程度.( )
8、赫夫曼树一定是满二叉树.（ ）
9、高度为h的k叉树至多有kh-1个结点.（ ）
10、对任意一个图,从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点.（ ）
2、键码序列（26,25,20,33,21,24,42,37）,要用散列法进行存储,规定负载因子α=0.5.
1)\x05（2分）请给出除余法的散列函数.
2)\x05（3分）用链接法解决碰撞,请画出插入所有的关键码后得到的散列表.
3、（6分）已知序列[10,18,4,3,6,12,l,9,15,8],请给出采用希尔排序法（d1＝5、2、1）对该序列做升序排序时的每一趟的结果.
.
7、（6分）下图表示一个地区的通讯网,边表示城市间的通讯线路,边上的权表示架设线路花费的代价,选择能沟通每个城市且总代价最省的n-1条线路,画出选择的过程和最终结果.
6. 邻接表的简介
图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。
在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。
在无向图中，描述每个点所有的边(点a-点b这种情况)
与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。
工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以，尽量用这些库，这样可以大大提高你的效率。
7. 图的邻接矩阵和邻接表的存储结构各有什么特点
图的邻接表数据类型描述如下：
const int N=maxn； // maxn表示图中最大顶点数
const int E=maxe ； // maxe图中最大边数
struct Edge{
int u,v; //边所邻接的两个顶点
int w; //边的权值
int next; //边指针，指向下一条边的内存池地址
}edge[E]; // 静态内存池，用于分配边
int head[N]; // 表头
int num; // 内存池的指针
8. 图的存储结构有哪些
最常见的：
顺序查找：适合顺序结构和链式结构
二分查找：适合顺序结构
其他的二叉查找树、B-树之类有自己的数据结构
9. 图的存储结构
邻接矩阵:
有向图的邻接矩阵
具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。
无向图的邻接矩阵
具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次。
在C 语言中，实现邻接矩阵表示法的类型定义如下所示： #defineMAX_VERTEX_NUM20typedefstructgraph{Elemtypeelem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intn;}Graph;邻接表
边结点的结构为：
adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针
elem是顶点内容，firstedge是指向第一条边或弧结点的指针。
在C语言中，实现邻接表表示法的类型定义如下所示： #defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeLinklist{//边结点intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//顶点结点Elemtypeelem;EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];创建有向图和无向图邻接表的算法实现：
（1） 创建有向图邻接表 voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化顶点数组scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//输入弧while(i){s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//创建新的弧结点s->adgvex=j-1;s->next=adj[i-1].firstedge;//将新的弧结点插入到相应的位置adj[i-1].firstegde=s;scanf(&i,&j);//输入下一条弧}}（2）创建无向图的邻接表 voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化邻接表scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//输入边while(i){s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s1->adgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2;scanf(&i,&j);}}
10. 图的邻接矩阵
为对称矩阵。根据矩阵性质可知原因：邻接矩阵（AdjacencyMatrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2++(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。