2021年青海省数据分析深入

1、2021年青海省数据分析深入1、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点int i，top=0,tag,longest=0;while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分

2、枝向下if(tagtop=1) /当前结点的右分枝已遍历if(!stop-Lc & !stop-Rc) /只有到叶子结点时，才查看路径长度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下/while(p!=null|top0)/结束LongestPath2、#define maxsize 栈空间容量 void InOutS(int smaxsize)/s是元素为整数的栈，本算法进行入栈和退栈操作。int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i0) p=stacktop; top-;prin

3、tf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;5、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct nodeint data; struct node *lchild,*rchild;node;int N2,NL,NR,N0;void count(nod

4、e *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 *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)

5、_;if (p-lchild!=null)(3)_; (4)_;6、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。7、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。8、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进

6、行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）9、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。10、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，Sm,后序序列是P1,P2,，Pm。因后序序列最后一个元素Pm是根，则

7、在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1im)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，Si-1是左子树的中序序列，而Si+1,Si+2,Sm是右子树的中序序列。若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则S2，S3，Sm和P1，P2，Pm-1可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则S1，S2，Sm-1和P1，P2，Pm-1唯一确定左子树，从而也确定了二叉树。最后，当1next;q=p-next;s=q-next;p-next=NULL; whil

8、e(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse12、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。13、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#defin

9、e true 1#define false 0typedef struct nodedatatype data; struct node *llink,*rlink; *BTree;void JudgeBST（BTree t,int flag）/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 if（t!=null & flag） Judgebst（t-llink,flag）；/ 中序遍历左子树if（pre=null）pre=t；/ 中序遍历的第一个结点不必判断else if（pre-datadata）pre=t；/前驱指针指向当前结点elseflag=flase；

10、 /不是完全二叉树 Judgebst （t-rlink,flag）；/ 中序遍历右子树/JudgeBST算法结束14、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。15、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序

11、列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef struct int lvl; /层次序列指针，总是指向当前“根结点”在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序

12、列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

13、=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； /让双亲的子女指

14、针指向该结点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

15、 (!empty(Q)return(p);/算法结束16、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-wn）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s0但物品数nj)printf(“序列非法n”)；exit(0);i+; /不论Ai是I或O，指针i均后移。if(j!=k) printf(“序列非法n”)；return(false);else printf(“序列合法n”)；return(true);/算法结束。20、证明由二叉树的中序序列和后序序

16、列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，Sm,后序序列是P1,P2,，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1im)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，Si-1是左子树的中序序列，而Si+1,Si+2,Sm是右子树的中序序列。若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则S2，S3，Sm和P1，P2，Pm-1可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则S1，S2，Sm-1和P1，P2，Pm-1唯一确定左子树，从而也确定了二叉树。最后，当1x， 这情况下向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 pri