2015年陕西省数据理论深入
- 格式：pdf
- 大小：74.48 KB
- 文档页数：1
1、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p
和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,
该算法找到p和q的最近共同祖先结点r。
2、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时
背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选
若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然
s>0但物品数n<1,则无解。
（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true
（2）s,n-1 // Knap←Knap(s,n-1)
3、本题应使用深度优先遍历，从主调函数进入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。
4、设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用
孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
