2010福建省分析数据库的考试题目深入(2)

if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝

while(top!=0 && s[top].tag==1) top--; //退栈

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor

12、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {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

13、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.

14、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i

//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 {LinkedList h;

h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;inext;

while(p!=h && p->data

{pre=p; p=p->next;} //查找A[i]的插入位置

if(p==h || p->data!=A[i]) //重复数据不再输入 {s=(LinkedList)malloc(sizeof(LNode));

s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中

}

}//for

return(h); }算法结束

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