2014山东省数据库期末考试高级.doc

1、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数while(frontlchild & !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(levelk) return (leaf); /层数大于k 后退出运行 /while /结束LeafKLevel2、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int num=0， visited=0 /num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数; AdjList g ; /用邻接表作存储结构的有向图g。 void dfs(v) visited v=1; num+; /访问的顶点数1 if (num=n) printf(“%d是有向图的根。n”,v); num=0;/if p=gv.firstarc; while (p) if (visiedp-adjvex=0) dfs (p-adjvex);p=p-next; /while visitedv=0; num-; /恢复顶点v/dfsvoid JudgeRoot()/判断有向图是否有根，有根则输出之。 static int i ;for (i=1;i1) 层上叶子结点个数if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数while(frontlchild & !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(levelk) return (leaf); /层数大于k 后退出运行 /while /结束LeafKLevel5、给出折半查找的递归算法，并给出算法时间复杂度性分析。6、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。7、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）建立有向图G的邻接表存储结构；（2）判断有向图G是否有根，若有，则打印出所有根结点的值。8、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。9、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef struct int lvl; /层次序列指针，总是指向当前“根结点”在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; ilchild=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) /根结点无右子树，遍历序列的1n-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; idata=levels.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); elses.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);/算法结束10、二部图（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为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【11、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。#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; 12、给出折半查找的递归算法，并给出算法时间复杂度性分析。13、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数while(frontlchild & !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(levelk) return (leaf); /层数大于k 后退出运行 /while /结束LeafKLevel14、设计一个尽可能的高效算法输出单链表的倒数第K个元素。15、二部图（bip