2015年西藏自治区数据要领大纲

1、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。

2、(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)top++ (2) 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

3、设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)__;

}}}}

4、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)

//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。