2014年全国数据库入门要领

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex); p=p->next;} //while

visited[v]=0; num--; //恢复顶点v }//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。 {static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

2、设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 3、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）

有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但

其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。 {for(i=1;i<=n;i++)

if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。 {printf(“%d”,v);

if(i==start) printf(“\\n”); else Print(i,start);break;}//if }//Print void dfs(int v) {visited[v]=1; for(j=1;j<=n;j++ )

if (g[v][j]!=0) //存在边(v,j)

if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2; }//dfs

void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;

for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle

4、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。