2021年内蒙古自治区数据统计高级

1、2021年内蒙古自治区数据统计高级1、已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=写出G的拓扑排序的结果。G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V72、本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0LinkedList creat(ElemType A,int n)/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点LinkedList h;h=(LinkedList)malloc(sizeof(LNode);/申请结点h-next=h; /形成空循环链表for(i=0;ipre=h;p=h-next;while(

2、p!=h & p-datapre=p; p=p-next; /查找Ai的插入位置if(p=h | p-data!=Ai) /重复数据不再输入s=(LinkedList)malloc(sizeof(LNode);s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/forreturn(h);算法结束3、本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0LinkedList creat(ElemType A,int n)/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点LinkedList h;h=(LinkedList)malloc(siz

3、eof(LNode);/申请结点h-next=h; /形成空循环链表for(i=0;ipre=h;p=h-next;while(p!=h & p-datapre=p; p=p-next; /查找Ai的插入位置if(p=h | p-data!=Ai) /重复数据不再输入s=(LinkedList)malloc(sizeof(LNode);s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/forreturn(h);算法结束4、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）建立有向图G的邻接表存储结构；（

4、2）判断有向图G是否有根，若有，则打印出所有根结点的值。5、本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0LinkedList creat(ElemType A,int n)/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点LinkedList h;h=(LinkedList)malloc(sizeof(LNode);/申请结点h-next=h; /形成空循环链表for(i=0;ipre=h;p=h-next;while(p!=h & p-datapre=p; p=p-next; /查找Ai的插入位置if(p=h | p-data!=Ai) /重复数据不再输入s=(

5、LinkedList)malloc(sizeof(LNode);s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/forreturn(h);算法结束6、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。int Similar(BiTree p,q) /判断二叉树p和q是否相似if(p=null & q=null) return (1);else if(!p & q | p & !q) return (0);else return(Similar(p-lchild,q-lchild) & Similar(p-rchild,

6、q-rchild) /结束Similar7、本题应使用深度优先遍历，从主调函数进入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); /