2023河南省数据库入门深入

1、1、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列即任一遍历序列均可确定一棵二叉树。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) /将左子

2、树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head if(bt)InOrd

3、er(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)2、4、void LinkList_reverse(Linklist &L) /链表的就

4、地逆置;为简化算法,假设表长大于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_reverse3、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedL

5、ist)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。 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-

6、rchild)/结束Similar5、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列即任一遍历序列均可确定一棵二叉树。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,l

7、2,l2+half-1) /将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针

8、为head if(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)6、#define maxsize 栈空间容量 voi

9、d InOutS(int smaxsize)/s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i=n; i+) /n个整数序列作处理。 scanf(“%d,&x); /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1时入栈。 if(top=maxsize-1)printf(“栈满n);exit(0);else s+top=x; /x入栈。 else /读入的整数等于-1时退栈。 if(top=0)printf(“栈空n);exit(0); else printf(“出栈元素是%dn,stop

10、-)； /算法结7、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。8、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，假设存在，那么以顶点序列的方式输出该回路找到一条即可。注：图中不存在顶点到自己的弧有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，假设dfsv结束前出现顶点u到v的回边，那么图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，假设我们找出u的下一邻接点的状态为1，就可以

11、输出回路了。void Print(int v,int start ) /输出从顶点start开始的回路。for(i=1;i=n;i+) if(gvi!=0 & visitedi=1 ) /假设存在边v,i，且顶点i的状态为1。 printf(“%d,v); if(i=start) printf(“n); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j=n;j+ ) if (gvj!=0) /存在边(v,j) if (visitedj!=1) if (!visitedj) dfs(j); /if e

12、lse cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判断是否有回路，有那么输出邻接矩阵。visited数组为全局变量。 for (i=1;i=n;i+) visitedi=0; for (i=1;ij)printf(“序列非法n)；exit(0); i+; /不管Ai是I或O，指针i均后移。 if(j!=k) printf(“序列非法n)；return(false); else printf(“序列合法n)；return(true); /算法结束。10、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是

13、边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 scanf(%d%d%d ,&edgei.

14、i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边假设仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，11、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当a

15、i=-1时，输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。问能否从这n件物品中选择假设干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n)均为正整数，并已顺序存储地在数组W中。请在以下算法的下划线处填空，使其正确求解背包问题。Knap(S，n)假设S=0那么Knaptrue否那么假设S0且n1)个整数存放到一维数组R中。设计一个尽可能高效时间、空间的算法，将R中保存的序列循环左移p0pn个位置，即将R中的数据x0, x1, x2, xn-

16、1，变换为(xp， xp1, , xn-1 ,x0 , x1, xp-1)。12、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置下标。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，假设局部平台长度i-j大于l时，那么修改最长平台的长度kl=i-j和其在b中的起始位置k=j，直到b数组结束，l即为所求。void Platform (int b , int N) /求具有N个元素的整型数组b中最长平台的长度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最长平台i+; j=i; /

17、新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d，l，k)；/ Platform13、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组rl.h中。假设查找成功，那么输出该记录在r数组中的位置及其值，否那么显示“not find信息。请编写出算法并简要说明算法思想。14、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形成空循环链表for(i=0;