2014年安徽省数据理论高级

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

2、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=iLinkedList creat(ElemType A[],int n)
//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点
{LinkedList h;
h=(LinkedList)malloc(sizeof(LNode));//申请结点
h->next=h; //形成空循环链表
for(i=0;i{pre=h;
p=h->next;
while(p!=h && p->data{pre=p; p=p->next;} //查找A[i]的插入位置
if(p==h || p->data!=A[i]) //重复数据不再输入
{s=(LinkedList)malloc(sizeof(LNode));
s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中
}
}//for
return(h);
}算法结束

3、 将顶点放在两个集合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{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); }//是二部图
[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

4、设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(iwhile (ix) j=j-1; if (iwhile (i}
r[i]=x;
}