2015年四川省学习数据库基础
1、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
2、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n<1) printf("n<0");
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}
3、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。
4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，现证明当n=m时结论成立。
设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则S
m是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1
{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树 。