2023贵州省java版本高级

1、1、(1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild)25. (1)t-rchild!=null (2)t-rchild!=null (3)N0+ (4)count(t-lchild) (5)count(t-rchild)26. .(1)top+ (2) stacktop=p-rchild (3)top+ (4)stacktop=p-lchild27. (1)*ppos / 根结点2rpos=ipos (3)rposipos (4)ipos (5)ppos+12、连通图的生成树包括图中的全部n个

2、顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩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条边：顶点，权值。

3、 scanf(%d%d%d ,&edgei.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()是测试图是否连通的函数，可用图的遍历实现，3、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形

4、成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束4、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于k

5、ey的记录。设此组记录存放于数组rl.h中。假设查找成功，那么输出该记录在r数组中的位置及其值，否那么显示“not find信息。请编写出算法并简要说明算法思想。5、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右三局部。假设左、右子树均有，那么层次序列根结点的后面应是左右子树的根；假设中序序列中只有左子树或只有右子树，那么在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后

6、，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：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 (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据fo

7、r (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;

8、 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;

9、 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);/算法结束6、此题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，假设退出dfs

10、()前，已访问完有向图的全部顶点设为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)

11、 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 JudgeRoot()/判断有向图是否有根，有根那么输出之。 static int i ;for (i=1;ix，这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否那么，假设下标已超出范围，那么查找失败。void search(datatype A , i

12、nt a,b,c,d, datatype x) /n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. i=a; j=d; flag=0; /flag是成功查到x的标志 while(i=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或向左当x0个人按顺时针方向围坐成一圈，现从第s个人开始按顺时

13、针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype 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为报数的起点*/ w

14、hile (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); /*输出最后一个结点*/ fre

15、e(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(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); /*

16、调用函数*/ 10、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右三局部。假设左、右子树均有，那么层次序列根结点的后面应是左右子树的根；假设中序序列中只有左子树或只有右子树，那么在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef struct int lvl; /层次序列指针，总是指向

17、当前“根结点在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列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(

18、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; /处理无左