2014年广西壮族自治区数据分析高级

2014年广西壮族自治区数据分析高级

1、(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

2、设有一个数组中存放了一个无序的关键序列K1、K2、 、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。

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、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数

2014年广西壮族自治区数据分析高级

{if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大

int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数 int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数

while(front<=rear)

{p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点

if(p->lchild) Q[++rear]=p->lchild; //左子女入队

if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1

last=rear; } //last移到指向下层最右一元素

if(level>k) return (leaf); //层数大于k 后退出运行

}//while }//结束LeafKLevel

本文来源：https://www.bwwdw.com/article/6621.html