文档介绍：:..中级软件设计师下午试题分类模拟4试题一丄、一般的树结构常采用孩子-兄弟表示法表示,即用二义链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩了结点和下一个兄弟结点。例如,如图(a)所示的树的孩了一兄弟表示如图(b)所示。(b)树及其孩子-兄弟表示示意图函数LevelTraVerseO的功能是对给定树进行层序遍历。例如,当对图(G中的树进行层序遍历时,结点的访问次序为DBAEFPCo对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如表所示。实现队列基木操作的函数原型表函数原型说明VoidInitQueue(Queue*Q)初始化队列BoolIsEmpty(QueueQ)判断队列是否为空,若是则返冋TRUE,否则返冋FALSEVoidEnQueue(Queue*Q,TreeNodep)元素入队列VoidDeQueue(Queue**p)元素出队列Bool^Status类型定义如卜":typedefenumfFALSE=0,TRUE=1}Bool;typedefenum{OVERFLOW=-2,UNDERFLOW^-1zERROR=0,0K=1}Status;树的二叉链表结点定义如下:typedefstructNode{chardata;structNode*firstchiid,*nextbrother;}Node,*TreeNode;[函数代码]StatusLevelTraverse(TreeNoderoot){/*层序遍历树,树采用孩子-兄弟表示法,匕。。七是树根结点的指针"QueuetemQ;TreeNodeptr,brotherptr;if(!root)returnERROR;InitQueue(&tempQ);(1);brotherptr=root->nextbrother;while(brotherptr){EnQueue(&tempQ,brotherptr);⑵;}/*end-while*/while((3)){(4);printf("%c\t"zptr->data);if((5))continue;(6);brotherptr=ptr->firstchiId->nextbrother;while(brotherptr){EnQueue(&tempQ,brotherptr);(7);|/*end-while*/}/*end-while*/returnOK;}/*LevelTraverse*/试题二2、函数intToplogical(,并返回关键路径的长度。其屮图G表示一个具有n个顶点的AOE网,图屮顶点从1〜n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:typedefstructGnode{ /*邻接表的表结点类型★/intadjvex; /*邻接顶点编号*/intweight; /*弧上的权值*/structGnode*nextarc; /*扌旨示下一个弧的结点★/}Gnode;typedefstructAdjlist{ /★邻接表的头结点类型*/charvdata; /*顶点的赛据信息*/structGnode*Firstadj; /*指向令N接表的第——个表结点*/}Adjulist;typedefstructLinkedWDigraph{/*图的类型*/intnze; /★图屮顶点个数和边数*/structAdjlist*head; /*指向图中第一个顶点的邻接表的头结点*/}LinkedWDigraph;例如,某AOE网如图1所示,其邻接表存储结构如图2所示。V3丑4=30V5VIheada)=30&2=10V2a3=20a5-50V6a6=30a7=20a8=I0V4VIV21V3V4AV5V6210—43053041()42()A3()5020图2AOE网邻接表存储结构[函数代码]intToplogical(LinkedWDigraphG.{Gnode*p;intjzwztop=0;int*Stack,*ve,*indegree;ve=(int*)malloc((+l)*sizeof(int));indegree=(int*)malloc((+1)*sizeof(int)); /*存彳诸网中齐项点的入度*/stack=(int*)malloc((+1)*sizeof(int)); /*存储入度为0的顶点的编号*/if(!ve||!indegree||!Stack)exit(0);for(j=l;j<=;j++){ve[j]=0;indegree[j]=0