2015广西壮族自治区数据库考试含答案高级

#include

typedef char datatype;

typedef struct node{

    datatype data;

    struct node * next;

} listnode;

typedef listnode* linklist;

/*--------------------------------------------*/

/*    删除单链表中重复的结点    */

/*--------------------------------------------*/

linklist deletelist(linklist head)

{  listnode *p,*s,*q;

p=head->next;

   while(p)

   {s=p;

q=p->next;

    while(q)  

if(q->data==p->data)

{s->next=q->next;free(q);

q=s->next;}

       else

      {  s=q;      /*找与P结点值相同的结点*/

q=q->next;

      } 

p=p->next;

   }

   return head;

}  

2、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

 int Similar(BiTree p,q) //判断二叉树p和q是否相似

    {if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0);

else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild))

}//结束Similar

3、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：

typedef struct

{ int lvl;         //层次序列指针，总是指向当前“根结点”在层次序列中的位置

int l,h;         //中序序列的下上界

int f;           //层次序列中当前“根结点”的双亲结点的指针

int lr;          // 1—双亲的左子树  2—双亲的右子树

}qnode; 

  BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数

{if (n<1) {printf(“参数错误\\n”); exit(0);}

qnode s,Q[];       //Q是元素为qnode类型的队列，容量足够大

 init(Q); int R=0;  //R是层次序列指针，指向当前待处理的结点

 BiTree p=(BiTree)malloc(sizeof(BiNode));          //生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据

for (i=0; i   if (in[i]==level[0]) break;

if (i==0)  //根结点无左子树，遍历序列的1—n-1是右子树

{p->lchild=null;

s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2;  enqueue(Q,s);

 }

else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树

{p->rchild=null;

    s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

 }

     else   //根结点有左子树和右子树

{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列

s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列

}

while (!empty(Q))  //当队列不空，进行循环，构造二叉树的左右子树

 { s=delqueue(Q); father=s.f;

for (i=s.l; i<=s.h; i++)

 if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode));                    //申请结点空间

p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据

   if (s.lr==1) father->lchild=p;

else father->rchild=p； //让双亲的子女指针指向该结点

   if (i==s.l)

{p->lchild=null; //处理无左子女

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2;  enqueue(Q,s); 

}

   else if (i==s.h)

{p->rchild=null; //处理无右子女

              s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); 

}

        else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列

       s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列

}

   }//结束while (!empty(Q))

return(p);

}//算法结束

4、二部图（bipartite  graph）  G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。

（1）．请各举一个结点个数为5的二部图和非二部图的例子。

（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

5、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

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

}}}}

7、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

29. ① 试找出满足下列条件的二叉树

1）先序序列与后序序列相同  2）中序序列与后序序列相同

3）先序序列与中序序列相同  4）中序序列与层次遍历序列相同    

8、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,}

写出G的拓扑排序的结果。

G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7   

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

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

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

{if(h1>=l1)

{post[h2]=pre[l1];    //根结点

half=(h1-l1)/2;      //左或右子树的结点数

PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)  //将左子树先序序列转为后序序列

PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)  //将右子树先序序列转为后序序列

}  }//PreToPost

32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

LinkedList head,pre=null;  //全局变量

LinkedList InOrder(BiTree bt)

//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head

{if(bt){InOrder(bt->lchild); //中序遍历左子树

       if(bt->lchild==null && bt->rchild==null) //叶子结点

            if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点

else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表

InOrder(bt->rchild); //中序遍历左子树

pre->rchild=null;                //设置链表尾

        }

 return(head);  } //InOrder

时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)

10、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=iLinkedList creat(ElemType A[],int n)

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

{LinkedList h;

h=(LinkedList)malloc(sizeof(LNode));//申请结点

h->next=h; //形成空循环链表

for(i=0;i  {pre=h;

p=h->next;

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);

}算法结束