2023年河南省数据理论章程

1、假设k1，…，kn是n个关键词，试解答：

试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为k1，k2，…，kn时，用算法建立一棵以llink / rlink 链接表示的二叉查找树。

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-1knap←knap(s,n-1)

3、(1)p->rchild (2)p->lchild (3)p->lchild (4)addq(q,p->lchild) (5)addq(q,p->rchild)

25. (1)t->rchild!=null (2)t->rchild!=null (3)n0++ 4)count(t->lchild) (5)count(t->rchild)

26. .1)top2) stack[top]=p->rchild (3)top++ 4)stack[top]=p->lchild

27. (1)*ppos //根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

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

int similar(bitree p,q) /判断二叉树p和q是否相似。

//沿左分枝向下。

if(bt==p) /不失一般性，假定p在q的左侧，遇结点p时，栈中元素均为p的祖先结点。

for(i=1;i<=top;i++)s1[i]=s[i]; top1=top; }将栈s的元素转入辅助栈s1 保存。

if(bt==q) /找到q 结点。

for(i=top;i>0;i--)将栈中元素的树结点到s1去匹配。

pp=s[i].t;

for (j=top1;j>0;j--)

if(s1[j].t==pp)

while(top!=0 &&s[top].tag==1) top退栈。

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝沿右分枝向下遍历。

//结束while(bt!=null ||top>0)

return(null);/p无公共祖先。

//结束ancestor

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

7、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）

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

下面用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。

//if}//print

void dfs(int v)

//ifelse

visited[v]=2;

//dfsvoid 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