【题目】已知一棵二叉树按顺序方式存储在数组 A[1..n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。

【来源】武汉大学2000年第五（1）题（8’）

【解答】
#inlcude <stdio.h>
parent(int A[],int i,int j)
{int k,m;
m=k=0;
if(i==1||j==1||A[i]==0||A[j]==0||i==j) // A[i]==0或A[j]==0表示不存在该结点
{printf("Error.\n");return;}
while(i!=1&&j!=1){
if(i<j){j=j/2;m=1;} // 结点 j 的最近祖先结点是 ┗ j/2 ┛
else if(j<i){i=i/2;k=1;}
else if(j==i){i=j;break;} // i=j 表示找到共同祖先
}
if(j==1||i==1)i=1; // i 或 j 有一个到了根结点
else if(m==0||k==0)i=i/2; // m、k 中有一个为 0 ，说明在查找过程中 i 或 j 有一个没移动
printf("The nearest common parent is A[%d].\n",i);
}


【分析】本题思路是使 i 和 j 交替追赶，直到相等。

------------------------------------------------------------------------

【题目】试写一个判别给定二叉树是否为二叉排序树的算法。

【来源】长沙铁道学院98年第五（1）题（12’）

【解答】
typedef struct node{
char data;
struct node *left,*right;
}*T;

issorttree(T)
{
initqueue(Q); // 初始化队列
inqueue(Q,T); // 树根结点进队列
while(!empty(Q)){
outqueue(Q,T);
if(T->data>T->left->data&&T->data<T->right->data){
if(T->left)inqueue(Q,T->left);
if(T->right)inqueue(Q,T->right);
}
else if(T->left||T->right)return 1; // 不符合二叉排序树的特征，则终止并返回‘ 1 ’
}
return 0; // 是二叉排序树，则返回 ‘0’
}

【分析】注意队列的运用，其他如图的广度搜索（教材《清华 C 版》）。

------------------------------------------------------------------------------
【题目】设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,
将此链表的记录按照key递增的次序进行就地排序.（不允许使用数组做辅助存储）

【来源】中科院计算机技术研究所1999年第五（1）题 （10’）
华中理工大学2000年第八（2）题 （13’）

【解答】
typedef struct CircleList{ // 定义循环链表
int key;
struct CircleList *next;
}*listnode;

ListSort(listnode head)
{
int k,min,i,j;
listnode p,q,t;
p=head->next;
while(p->next!=head->next){p=p->next;k+=1;} // 统计链表中元素个数，保存在 K 中
p=head;j=1;
for(i=1;i<k;i++){
while(j<=i){p=p->next;j++;} // 找应填入当前最小元素的位置，该位置保存在 q 中
min=p->key;q=p; // 将当前位置元素的值设为初始最小值
while(p->next!=head->next){
if(min>p->key){min=p->key;t=p;} // 找当前最小元素，并保存在 t 所指位置中
p=p->next;
}
t->key=q->key;q->key=min;j=1; // 交换 q 位置元素和最小元素的值
}
}

【分析】本题不需要修改链表中的各个指针。