2021年全国数据整理加强

1、2021年全国数据整理加强 2021年全国数据整理加强 1、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。 2、对一般二叉树，仅依据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，依据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void pretopost(elemtype pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最终结点的下标。if(h1=l1)posth2=pre

2、l1; /根结点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) /将右子树先序序列转为后序序列 /pretopost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最终叶子结点的rchild为空。linkedlist head,pre=null;

3、 /全局变量linkedlist inorder(bitree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为headif(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时间简单度

4、为o(n),帮助变量使用head和pre,栈空间简单度o(n)3、题目中要求矩阵两行元素的平均值按递增挨次排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，留意在排序时若有元素移动，则与之相应的行中各元素也必需做相应变动。void translation（float *matrix，int n）/本算法对nn的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。int i,j,k,l；float sum，min； /sum暂存各行元素之和float *p, *pi, *pk;for

5、(i=0; in; i+)sum=0.0; pk=matrix+i*n; /pk指向矩阵各行第1个元素.for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum; /将一行元素之和存入一维数组./for ifor(i=0; in-1; i+) /用选择法对数组p进行排序min=*(p+i); k=i; /初始设第i行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /记新的最小值及行号.if(i!=k) 2021年全国数据整理加强 /若最小行不是当前行,要进行交换(行元素及行元素之和) pk=matr

6、ix+n*k; /pk指向第k行第1个元素.pi=matrix+n*i; /pi指向第i行第1个元素.for(j=0;jn;j+) /交换两行中对应元素.sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和./if/for ifree(p); /释放p数组./ translation算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可削减比较次数,但数据移动会增多.算法时间简单度为o(n2).4、设一棵二叉树的结点结构为 (llink,info,rlin

7、k),root为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ancestor（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。5、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。6、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若

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

9、)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if (n1) 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; in; i+) /在中序序列中查找根结点，然后，左右子女信息入队列if (ini=level

10、0) break;if (i=0) /根结点无左子树，遍历序列的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); 2021年全国数据整理加强 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)

11、;/左子树有关信息入队列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; 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)

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

13、=p; s.lr=2; enqueue(q,s); /右子树有关信息入队列/结束while (!empty(q)return(p);/算法结束7、设有两个集合a和集合b，要求设计生成集合c=ab的算法，其中集合a、b和c用链式存储结构表示。typedef struct node int data; struct node *next;lklist;void intersection(lklist *ha,lklist *hb,lklist *hc)lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next) for(q=hb;q!=0;q=q-next) if (q

14、-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-next=hc; hc=t;8、数组a和b的元素分别有序，欲将两数组合并到c数组，使c仍有序，应将a和b拷贝到c，只要留意a和b数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到c中即可。void union(int a,b,c,m,n)/整型数组a和b各有m和n个元素，前者递增有序，后者递减有序，本算法将a和b归并为递增有序的数组c。i=0; j=n-1; k=0;/ i，j，k分别是数组a,b和c的下标，因用c描述

15、，下标从0开头while(im j=0)if(aibj) ck+=ai+ else ck+=bj-;while(im) ck+=ai+;while(j=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。bitree creat() /建立二叉树的二叉链表形式的存储结构elemtype x；bitree bt;scanf(“%d”,x); /本题假定结点数据域为整型if(x=0) bt=null;else if(x0)bt=(binode *)malloc(sizeof(binode);bt-d

16、ata=x; bt-lchild=creat(); bt-rchild=creat();else error(“输入错误”)；return(bt);/结束 bitreeint judg 2021年全国数据整理加强 ecomplete(bitree bt) /推断二叉树是否是完全二叉树,如是，返回1，否则，返回0 int tag=0; bitree p=bt, q; / q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);queueinit(q); queuein(q,p); /初始化队列，根结点指针入队while (!queueempty(q)p=queueo

17、ut(q); /出队if (p-lchild !tag) queuein(q,p-lchild); /左子女入队else if (p-lchild) return 0; /前边已有结点为空，本结点不空else tag=1; /首次消失结点为空if (p-rchild !tag) queuein(q,p-rchild); /右子女入队else if (p-rchild) return 0; else tag=1; /whilereturn 1; /judgecomplete9、设有一组初始记录关键字序列（k1，k2，kn），要求设计一个算法能够在o(n)的时间简单度内将线性表划分成两部分，其中左

18、半部分的每个关键字均小于ki，右半部分的每个关键字均大于等于ki。void quickpass(int r, int s, int t)int i=s, j=t, x=rs;while(ij)while (ij rjx) j=j-1; if (ij) ri=rj;i=i+1;while (ij rix) i=i+1; if (ij) rj=ri;j=j-1;ri=x;10、数组a和b的元素分别有序，欲将两数组合并到c数组，使c仍有序，应将a和b拷贝到c，只要留意a和b数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到c中即可。void union(int a,b,c,m,n)

19、/整型数组a和b各有m和n个元素，前者递增有序，后者递减有序，本算法将a和b归并为递增有序的数组c。i=0; j=n-1; k=0;/ i，j，k分别是数组a,b和c的下标，因用c描述，下标从0开头while(im j=0)if(aibj) ck+=ai+ else ck+=bj-;while(im) ck+=ai+;while(j=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。bitree creat() /建立二叉树的二叉链表形式的存储结构elemtype x；bitree bt;sc

20、anf(“%d”,x); /本题假定结点数据域为整型if(x=0) bt=null;else if(x0)bt=(binode *)malloc(sizeof(binode);bt-data=x; bt-lchild=creat(); bt-rchild=creat();else error(“输入错误”)；return(bt);/结束 bitreeint judgecomplete(bitree bt) /推断二叉树是否是完全二叉树,如是，返回1，否则，返回0int tag=0; bitree p=bt, q; / q是队列，元素是二叉树结点指针，容量足够大if(p=null) return

21、 (1);queueinit(q); queuein(q,p); /初始化队列，根结点指针入队while (!queueempty(q)p=queueout(q); /出队 if (p-lchild !tag) queuein(q,p-lchild); /左子女入队else if (p-lchild) return 0; /前边已有结点为空，本结点不空 2021年全国数据整理加强 else tag=1; /首次消失结点为空 if (p-rchild !tag) queuein(q,p-rchild); /右子女入队else if (p-rchild) return 0; else tag=1;

22、 /whilereturn 1; /judgecomplete11、设t是一棵满二叉树，编写一个将t的先序遍历序列转换为后序遍历序列的递归算法。12、设有两个集合a和集合b，要求设计生成集合c=ab的算法，其中集合a、b和c用链式存储结构表示。typedef struct node int data; struct node *next;lklist;void intersection(lklist *ha,lklist *hb,lklist *hc)lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next) for(q=hb;q!=0;q=q-next) if

23、(q-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-next=hc; hc=t;13、设t是一棵满二叉树，编写一个将t的先序遍历序列转换为后序遍历序列的递归算法。14、设有一组初始记录关键字序列（k1，k2，kn），要求设计一个算法能够在o(n)的时间简单度内将线性表划分成两部分，其中左半部分的每个关键字均小于ki，右半部分的每个关键字均大于等于ki。void quickpass(int r, int s, int t)int i=s, j=t, x=rs;while(ij)whil

24、e (ij rjx) j=j-1; if (ij) ri=rj;i=i+1;while (ij rix) i=i+1; if (ij) rj=ri;j=j-1;ri=x;15、矩阵中元素按行和按列都已排序，要求查找时间简单度为o（m+n），因此不能采纳常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种状况：一是ai,jx， 这状况下向j 小的方向连续查找；二是ai,jx，下步应向i大的方向查找；三是ai,j=x，查找胜利。否则，若下标已超出范围，则查找失败。void search(datatype a , int a,b,c,d, datatype x)/n*m矩阵a

25、,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵a中.i=a; j=d; flag=0; /flag是胜利查到x的标志while(i=b 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）或向左（当xai,j）。向下最多是m，向左最多是n。最佳状况是在右上角比较一次胜利，最差是在左下角（ab,c），比较m+n

26、次，故算法最差时间简单度是o(m+n）。16、设一棵二叉树的结点结构为 (llink,info,rlink),root为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ancestor（root，p,q,r）,该算法找到p和q的最近共同祖先结点r。17、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉 2021年全国数据整理加强 树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序

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

28、列inn生成二叉树。 n是二叉树的结点数if (n1) 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; in; i+) /在中序序列中查找根结点，然后，左右子女信息入队列if (ini=level0) break;if (i=0) /根结

29、点无左子树，遍历序列的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;s.h=n-

30、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-lchild=p;else father-rchild=

31、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); /右子树有关信息入队

32、列/结束while (!emp 2021年全国数据整理加强 ty(q) return(p);/算法结束18、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29. 试找出满意下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同19、两棵空二叉树或仅有根结点的二叉树相像；对非空二叉树，可判左右子树是否相像，采纳递归算法。int similar(bitree p,q) /推断二叉树p和q是否相像if(p=null q=null) return (1);else if(!p q | p !q) return (0

33、);else return(similar(p-lchild,q-lchild) similar(p-rchild,q-rchild)/结束similar20、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。21、假设k1，kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为k1，k2，kn时，用算法建立一棵以llink / rlink 链接表示的二叉查找树。22、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列

34、。（15分）（1）a和d是合法序列，b和c 是非法序列。（2）设被判定的操作序列已存入一维数组a中。int judge(char a)/推断字符数组a中的输入输出序列是否是合法序列。如是，返回true，否则返回false。i=0; /i为下标。j=k=0; /j和k分别为i和字母o的的个数。while(ai!=0) /当未到字符数组尾就作。switch(ai)casei: j+; break; /入栈次数增1。caseo: k+; if(kj)printf(“序列非法n”)；exit(0);i+; /不论ai是i或o，指针i均后移。if(j!=k) printf(“序列非法n”)；return

35、(false);else printf(“序列合法n”)；return(true);/算法结束。23、依据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct nodedatatype data; struct node *llink,*rlink; *btree;void judgebst（btree t,int flag）/ 推断二叉树是否是

36、二叉排序树，本算法结束后，在调用程序中由flag得出结论。 if（t!=null flag） judgebst（t-llink,flag）；/ 中序遍历左子树if（pre=null）pre=t；/ 中序遍历的第一个结点不必推断else if（pre-datat-data）pre=t；/前驱指针 2021年全国数据整理加强 指向当前结点 elseflag=flase； /不是完全二叉树judgebst （t-rlink,flag）；/ 中序遍历右子树/judgebst算法结束24、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数n2;只

37、有非空左儿子的个数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(node *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!=n