2015年四川省数据要领摘要
- 格式：rtf
- 大小：56.19 KB
- 文档页数：3
1、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,
右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子
结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node;
int N2,NL,NR,N0;
void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++;
else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;
}
26.树的先序非递归算法。
void example(b)
btree *b;
{ btree *stack[20], *p；
int top;
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; (2)___;
}
if (p->lchild!=null)
(3)___; (4)__;
}}}}
2、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下
沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，
请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）
3、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下
沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，
请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）
4、约瑟夫环问题（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); /*调用函数*/
}
}
5、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出
构造过程。
