河北省分析数据库的考试题目基础.pdf

1、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图 中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回 路（找到一条即可）。（注：图中不存在顶点到自己的弧） 有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三 类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问 完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前 出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v 的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为 1，就可以输出回路了。 void Print(int v,int start ) /输出从顶点start开始的回路。 for(i=1;i=l1) posth2=prel1; /根结点 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 pre=bt; /处理第一个叶子 结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入 链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n) 4、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下 面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成 一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺 的语句。 #define MAX 100 typedef struct Node char info; struct Node *llink, *rlink; TNODE; char predMAX,inodMAX; main(int argc,int *argv) TNODE *root; if(argcinfo=(1)_; for(2)_ ; rposllink=restore(ppos+1, (4)_,k ); ptr-rlink=restore (5)_+k,rpos+1,n-1-k); return ptr; postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(ptr-rlink); printf(“%c”,ptr-info); 5、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左 右子树是否相似，采用递归算法。 int Similar(BiTree p,q) /判断二叉树p和q是否相似 if(p=null else if(!p else return(Similar(p-lchild,q-lchild) struct Node *llink, *rlink; TNODE; char predMAX,inodMAX; main(int argc,int *argv) TNODE *root; if(argcinfo=(1)_; for(2)_ ; rposllink=restore(ppos+1, (4)_,k ); ptr-rlink=restore (5)_+k,rpos+1,n-1-k); return ptr; postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(ptr-rlink); printf(“%c”,ptr-info); 7、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下 面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成 一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺 的语句。 #define MAX 100 typedef struct Node char info; struct Node *llink, *rlink; TNODE; char predMAX,inodMAX; main(int argc,int *argv) TNODE *root; if(argcinfo=(1)_; for(2)_ ; rposllink=restore(ppos+1, (4)_,k ); ptr-rlink=restore (5)_+k,rpos+1,n-1-k); return ptr; postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(ptr-rlink); printf(“%c”,ptr-info); 8、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二 叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针， 试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖 先结点r。 9、4、 void LinkList_reverse(Linklist 为简化算法,假设表长大于2 p=L-next;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把L的元素逐个插入新表表头 q-next=p;s-next=q;L-next=s; /LinkList_reverse 10、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的 n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方 向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数 到第m的人又出列，如此重复直到所有的人全部出列为止。现要求 采用循环链表结构设计一个算法，模拟此过程。 #include typedef int datatype; typedef struct node datatype data; struct node *next; listnode; typedef listnode *linklist; void jose(linklist head,int s,int m) linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*当循环链表中的结点个数大于1时*/ p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ pre=p; p=p-next; count+; pre-next=p-next; /*输出该结点，并删除该结点*/ printf(“%4d“,p-data); free(p); k1=pre-next; /*新的报数起点*/ printf(“%4d“,k1-data); /*输出最后一个结点*/ free(k1); main() linklist head,p,r; int n,s,m,i; printf(“n=“); scanf(“%d“, printf(“s=“); scanf(“%d“, printf(“m=“, scanf(“%d“, if (ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ 11、矩阵中元素按行和按列都已排序，要求查找时间复杂度为 O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角 （i=a,j=d）元素与x比较，只有三种情况：一是Ai,jx， 这情况下 向j 小的方向继续查找；二是Ai,j=c) if(Aij=x) flag=1;break; else if (Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x为整 型. else printf(“矩阵A中无%d 元素”，x)； 算法search结束。 算法讨论算法中查找x的路线从右上角开始，向下（当xAi,j）或 向左（当xs) s=wij; if (s0但物 品数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); /算法结束 15、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一 个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的 结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历 序列均可确定一棵二叉树）。 void PreToPost(ElemType pre ,post,int l1,h1,l2,h2) /将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最 后结点的下标。 if(h1=l1) posth2=prel1; /根结点 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; /全局变量 LinkedL