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
{num=0; visited[1..n]=0; dfs(i); }
}// JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
2、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d 可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。
3、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ① 试找出满足下列条件的二叉树
1）先序序列与后序序列相同 2）中序序列与后序序列相同
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
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
{num=0; visited[1..n]=0; dfs(i); }
}// JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
2、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d 可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。
3、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ① 试找出满足下列条件的二叉树
1）先序序列与后序序列相同 2）中序序列与后序序列相同
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同