首页 > 2014年山东省数据总结入门

2014年山东省数据总结入门

发布时间：来源：文档文库

小中大

字号：

手机查看

1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树
1）先序序列与后序序列相同2）中序序列与后序序列相同
3）先序序列与中序序列相同4）中序序列与层次遍历序列相同
2、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
3、本题应使用深度优先遍历，从主调函数进入dfs(v时，开始记数，若退出dfs(前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs(过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
intnum=0，visited[]=0//num记访问顶点个数,访问数组visited初始化。constn=用户定义的顶点数;
AdjListg;//用邻接表作存储结构的有向图g。voiddfs(v
{visited[v]=1;num++;//访问的顶点数＋1
if(num==n{printf(“%d是有向图的根。\n”,v;num=0;}//ifp=g[v].firstarc;while(p
{if(visied[p->adjvex]==0dfs(p->adjvex;p=p->next;}//while
visited[v]=0;num--;//恢复顶点v}//dfs
voidJudgeRoot(
//判断有向图是否有根，有根则输出之。{staticinti;
for(i=1;i<=n;i++//从每个顶点出发，调用dfs(各一次。{num=0;visited[1..n]=0;dfs(i;}}//JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

本文来源：https://www.2haoxitong.net/k/doc/791d17eea5e9856a561260ee.html