2021年.特别行政区C#语言高级.docx

2021年.特别行政区C#语言高级1、本题应使用深度优先遍历，从主调函数进入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)if (visiedp->adjvex=0) dfs (p->adjvex);p=p->next; /whilevisitedv=0; num-; /恢复顶点v/dfsvoid JudgeRoot()/判断有向图是否有根，有根则输出之。static int i ;for (i=1;inum=0; visited1.n=0; dfs(i); / JudgeRoot算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用gi.vertex。2、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。#include typedef char datatype;typedef struct nodedatatype 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;3、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第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为报数的起点*/while (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); /*输出最后一个结点*/free(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 (nelse/*建表*/head=(linklist)malloc(sizeof(listnode); /*建第一个结点*/head->data=n;r=head;for (i=n-1;i>0;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode);p->data=i;p->next=head;head=p;r->next=head; /*生成循环链表*/jose(head,s,m); /*调用函数*/4、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typedef structBiTree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack s,s1;/栈，容量够大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=ROOT;while(bt!=null |top>0)while(bt!=null && bt!=p && bt!=q) /结点入栈s+top.t=bt; stop.tag=0; bt=bt->lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;iif(bt=q) /找到q 结点。for(i=top;i>0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j>0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 && stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.t->rchild; /沿右分枝向下遍历/结束while(bt!=null |top>0)return(null);/、p无公共祖先/结束Ancestor