2015年台湾省数据库入门摘要

1、精选文档1、假设K1，Kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。2、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int

2、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

3、 JudgeRoot()/判断有向图是否有根，有根则输出之。 static int i ;for (i=1;i<=n;i+ ) /从每个顶点出发，调用dfs()各一次。 num=0; visited1.n=0; dfs(i); / JudgeRoot算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用gi.vertex。3、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。4、本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0<=i&l

4、t;n）,然后到链表中去查找值为Ai的结点，若查找失败，则插入。LinkedList creat(ElemType A,int n)/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点LinkedList h;h=(LinkedList)malloc(sizeof(LNode);/申请结点h->next=h; /形成空循环链表for(i=0;i<n;i+) pre=h;p=h->next; while(p!=h && p->data<Ai) pre=p; p=p->next; /查找Ai的插入位置 if(p=h | p->d

5、ata!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s->data=Ai; pre->next=s; s->next=p;/将结点s链入链表中/for return(h);算法结束5、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局

6、变量指针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 (n<1

7、) printf(“参数错误n”); exit(0);qnode s,Q; /Q是元素为qnode类型的队列，容量足够大 init(Q); int R=0; /R是层次序列指针，指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode); /生成根结点 p->data=level0; p->lchild=null; p->rchild=null; /填写该结点数据for (i=0; i<n; i+) /在中序序列中查找根结点，然后，左右子女信息入队列 if (ini=level0) break;if (i=0) /根结点无左子树，

8、遍历序列的1n-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) /根结点无右子树，遍历序列的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

9、;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 (ini=levels.lvl) break;p=(bitreptr)malloc(sizeof(binode); /申请结点空间 p->data=levels.lvl; p->lchild=null; p->rchild=null; /填写该结点数据 if (s.lr=1) father-&

10、gt;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=+

11、R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子树有关信息入队列 /结束while (!empty(Q)return(p);/算法结束6、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typed

12、ef struct BiTree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=ROOT; while(bt!=null |top>0)while(bt!=null && bt!=p && bt!=q) /结点入栈s+top.t=bt; stop.tag=0; bt=bt->lchild; /沿左分枝向下if(bt=p) /

13、不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i<=top;i+) s1i=si; top1=top; /将栈s的元素转入辅助栈s1 保存if(bt=q) /找到q 结点。for(i=top;i>0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j>0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 && stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.

14、t->rchild; /沿右分枝向下遍历/结束while(bt!=null |top>0)return(null);/、p无公共祖先/结束Ancestor7、本题应使用深度优先遍历，从主调函数进入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->adjve