2011海南省数据分析基础

1、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

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、4、 void LinkList_reverse(Linklist &L)

//链表的就地逆置;为简化算法,假设表长大于2

{

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

{

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头

}

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

3、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。

4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似

{if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0);

else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar

5、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）

（1）下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

6、 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。

int BPGraph (AdjMatrix g)

//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合

Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1

while(f<r)

{v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号

if (!visited[v])

{visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++)

if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列

else if (s[j]==s[v]) return(0);} //非二部图

}//if (!visited[v])

}//while

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

7、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>} 写出G的拓扑排序的结果。

G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7

8、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。

void union(int A[],B[],C[],m,n)

//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。

{i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始 while(i<m && j>=0)

if(a[i]<b[j]) c[k++]=a[i++] else c[k++]=b[j--];

while(i<m) c[k++]=a[i++];

while(j>=0) c[k++]=b[j--];

}算法结束

4、要求二叉树按二叉链表形式存储。15分

（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构

{ElemType x；BiTree bt;

scanf(“%d”,&x); //本题假定结点数据域为整型

if(x==0) bt=null;

else if(x>0)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt->data=x; bt->lchild=creat(); bt->rchild=creat();

}

else error(“输入错误”)；

return(bt);

}//结束 BiTree

int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0

{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1);

QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队

while (!QueueEmpty(Q))

{p=QueueOut(Q); //出队

if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队

else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空

if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队

else if (p->rchild) return 0; else tag=1;

} //while

return 1; } //JudgeComplete

9、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点

int i，top=0,tag[],longest=0;

while(p || top>0)

{ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下

if(tag[top]==1) //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度

if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈，记住最高栈顶指针，退栈

}

else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下

}//while(p!=null||top>0)

}//结束LongestPath

10、#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针，定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}

else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\n”);exit(0);}

else printf(“出栈元素是%d\n”,s[top--])；}

}

}//算法结

11、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：

（1）．建立有向图G的邻接表存储结构；

（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

12、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。

void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数

node edge[];

scanf( "%d%d",&e,&n) ; //输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。

{edge[0]=edge[i]; j=i-1;

while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];

edge[j+1]=edge[0]; }//for

k=1; eg=e;

while (eg>=n) //破圈，直到边数e=n-1.

{if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边

}//while

}//算法结束。

connect()是测试图是否连通的函数，可用图的遍历实现，

13、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）

（1）A和D是合法序列，B和C 是非法序列。

（2）设被判定的操作序列已存入一维数组A中。

int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。

while(A[i]!=‘\0’) //当未到字符数组尾就作。

{switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);} }

i++; //不论A[i]是‘I’或‘O’，指针i均后移。}

if(j!=k) {printf(“序列非法\n”)；return(false);}

else {printf(“序列合法\n”)；return(true);}

}//算法结束。

14、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。

15、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。

void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];

scanf( "%d%d",&e,&n) ; //输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。

{edge[0]=edge[i]; j=i-1;

while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];

edge[j+1]=edge[0]; }//for

k=1; eg=e;

while (eg>=n) //破圈，直到边数e=n-1.

{if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边

}//while

}//算法结束。

connect()是测试图是否连通的函数，可用图的遍历实现，

本文来源：https://www.bwwdw.com/article/ttt1.html