《2021年.特别行政区数据总结入门》由会员分享，可在线阅读，更多相关《2021年.特别行政区数据总结入门（23页珍藏版）》请在金锄头文库上搜索。
1、2021年.特别行政区数据总结入门1、设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(node *t)if (t-lchild!=NULL) if (1)_ N2+; else NL+;else if (2)_
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)_;if (p-lchild!=null)(3)_; (4)_;2、给定n个村庄之间的交通图，若村庄i和j之间有道路，
3、则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）3、矩阵中元素按行和按列都已排序，要求查找时间复杂度为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(
4、“A%d%d=%d”,i,j,x); /假定x为整型.else printf(“矩阵A中无%d 元素”，x)；算法search结束。算法讨论算法中查找x的路线从右上角开始，向下（当xAi,j）或向左（当x4、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数if(bt=null | klchild & !p-rchild) leaf+; /叶子结点if(p-lchild) Q+rear=p-lchild; /左子女入队if(p-rchild) Q+rear=p-rchi
5、ld; /右子女入队if(front=last) level+; /二叉树同层最右结点已处理,层数增1last=rear; /last移到指向下层最右一元素if(levelk) return (leaf); /层数大于k 后退出运行/while /结束LeafKLevel5、#define maxsize 栈空间容量 void InOutS(int smaxsize)/s是元素为整数的栈，本算法进行入栈和退栈操作。int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; itypedef char datatype;typedef struct nodedataty
6、pe data;struct node * next; listnode;typedef listnode* linklist;/*-*/* 删除单链表中重复的结点 */*-*/linklist deletelist(linklist head) listnode *p,*s,*q;p=head-next;while(p)s=p;q=p-next;while(q) if(q-data=p-data)s-next=q-next;free(q);q=s-next;else s=q; /*找与P结点值相同的结点*/q=q-next; p=p-next;return head; 9、在有向图G中，如果
7、r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）建立有向图G的邻接表存储结构；（2）判断有向图G是否有根，若有，则打印出所有根结点的值。10、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。11、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新
8、开始报数，数到第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为报数的起点*/while (count!=s) /*找初始报数起点*/pre=
9、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;pr
10、intf(n=);scanf(%d,&n);printf(s=);scanf(%d,&s);printf(m=,&m);scanf(%d,&m);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); /*调用函数*/12、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点
11、的两个指针域分别为llink和rlink）。13、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量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）/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出
12、结论。 if（t!=null & flag） Judgebst（t-llink,flag）；/ 中序遍历左子树if（pre=null）pre=t；/ 中序遍历的第一个结点不必判断else if（pre-datadata）pre=t；/前驱指针指向当前结点elseflag=flase； /不是完全二叉树 Judgebst （t-rlink,flag）；/ 中序遍历右子树/JudgeBST算法结束14、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄
13、到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）15、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当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是根
14、，这时二叉树的左子树为空，右子树的结点数是m-1,则S2，S3，Sm和P1，P2，Pm-1可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则S1，S2，Sm-1和P1，P2，Pm-1唯一确定左子树，从而也确定了二叉树。最后，当1l) l=i-j+1;k=j; /局部最长平台i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；/ Platform17、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部（注:向量d可视为循环表），其原则为，先
15、将rl赋给d1，再从r2 记录开始分二路插入。编写实现二路插入排序算法。18、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为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+; /访问的顶点数1if (num=n) printf(“%d是有向图的根。n”,v); num=0;/ifp=gv.firstarc;while (p)
