① 假设图G采用邻接表存储，设计一个算法，判断图G是否连通。若连通则返回1；否则返回0.
bool Connect(AlGraph*G)
{int i;
bool flag=true;
for(i=0;i<G->n;i++)
visited[i]=0;
DFS(G,0);
for(i=0;i<G->n;i++)
if(visited[i]==0)
{flag=false;
break;}
return flag;
}
② 无向图采用邻接表存储结构,编写算法输出图中各连通分量的节点序列
//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.仅适用于邻接表结构
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表结点
LinkQueue Q;//链队列类型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值为未被访问
}
InitQueue(&Q);//初始化辅助队列Q
for (v=0; v<G.vexnum; ++v)//如果是连通图，只v=0就遍历全图
{
if (! visited[v])//v尚未被访问
{
visited[v] = TRUE;//设v为已被访问
Visit(G.vertices[v].data);//访问v
EnQueue(&Q,v);//v入队
while (! QueueEmpty(Q))//队列不空
{
DeQueue(&Q,&u);//队头元素出队并置为u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的邻接顶点
{
if (! visited[p->data.adjvex])//u的邻接顶点尚未被访问
{
visited[p->data.adjvex] = TRUE;//该邻接顶点设为已被访问
Visit(G.vertices[p->data.adjvex].data);//访问该邻接顶点
EnQueue(&Q,p->data.adjvex);//入队该邻接顶点序号
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
③ 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为
答案是o（n+e） 但是邻接表里面不是每个边被储存两次吗，为什么不是n+2e呢？
在大O表示法中O（n+2e)通常应表示为O（n+e）
④ 无向图G.，有n个顶点，m条边，如何采用邻接表存储该图主要是想知道算法~用c语言
无向图就是不分方向的图
连接表的横列有N项，纵列也是N项
形成的N*N项每项都被称为边结点
每项都有纵横两个坐标，例如点（N,N-1），表示的就是从第N点向第N-1点有无路径。
由于有E条边，自然有E条路径，但是由于无向，=双向，所以要乘以二
⑤ 假设图采用邻接表存储，编写一个函数利用深度优先搜索方法求出无向图中通过给定点v的简单回路。
你也是学数据结构的？？？我学的不好，不会。呵呵。
⑥ 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
邻接表储存时，是B。邻接矩阵储存就是C了。
⑦ 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢
这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。
先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
例如，下图所示二叉树的遍历结果是：ABDECF。
(7)假设图采用邻接表存储扩展阅读：
遍历种类：
一、NLR：前序遍历(Preorder Traversal 亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。
二、LNR：中序遍历(Inorder Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。
三、LRN：后序遍历(Postorder Traversal)，访问根结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为 先根遍历、中根遍历和后根遍历。
⑧ 数据结构问题
1、假设图采用邻接表存储，编写一个函数利用深度优先搜索方法求出无向图中通过给定点v的简单回路。
2、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。
（1）已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
（2）已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
（3）已知两棵二叉树的前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树
3、假设二叉树包含的结点数据为1，3，7，2，12。
（1）画出两棵高度最大的二叉树；
（2）画出两棵完全二叉树，要求每个双亲结点的值大于其他孩子结点的值。
4、一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序（同层自左至右）从1开始对全部结点编号，问：
（1）各层的结点数目是多少？
（2）编号为i结点的双亲结点（若存在）的编号是多少？
（3）编号为i的结点的第j个孩子结点（若存在）的编号是多少？
（4）编号为i的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
5、
假设在树中，结点x是结点y的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：{（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c）}
用树形表示法画出此树，并回答下列问题：
（1）哪个是根结点：（2）哪些是叶结点？（3）哪个是g的双亲？
（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？
（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次各是多少？
（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？
（11）树的度数是多少？
6、编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1和ch2均为字符型）：
将串r中所有其值为ch1的字符换成ch2的字符。
将串r中所有字符按照相反的次序仍存放在r中。
从串r中删除其值等于ch的所有字符。
从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。
从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。
7、设二维数组A5*6的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a45的起始地址为多少？按行和按列优先存储时，a25的起始地址分别为多少？
8、假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组表示
⑨ 假设G采用邻接表存储、试设计一个算法、求不带权无向连通图G中距离定点V的最远的
图G由两个集合V和E组成,记为G=(V,E),
其中V是图中顶点的有限集合，V={v1,v2,…,vn}，E是连接V中两个顶点的边的有限集合,边是顶点的有序对或无序对，记作<vi,vj>或（vi, vj）。
如果代表边的顶点对是无序的,则称G为无向图,无向图中代表边的无序顶点对通常用圆括号括起来。
如果表示边的顶点对是有序的,则称G为有向图,在有向图中代表边的顶点对通常用尖括号括起来 。
⑩ 数据结构 ：假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点
(1)每个点关联一个量d，让所有定点的d值都为0
(2)对v进行广度优先搜索
(3)bfs后d值最大的点就是离v最远的点。