首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
admin
2017-08-31
35
问题
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。
函数LevelTraVerse()的功能是对给定树进行层序遍历。例如,当对图15.1(a)中的树进行层序遍历时,结点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如表15一1所示。
Bool、Status类型定义如下:
typedef enum{FALSE=0,TRUE=1)Bool;
typedef enum{OVERFLOW=一2,UNDERFLOW=一1,ERROR=0,OK=1}Status;
树的二叉链表结点定义如下:
typedef struct Node{
char data;
struct Node*firstchild,*nextbrother;
}Node,*TreeNode;
【函数代码】
Status LevelTraverse(TreeNode root)
{/*层序遍历树,树采用孩子一兄弟表示法,root是树根结点的指针*/
Queue temQ ;
TreeNode ptr, brOtherptr;
if(!root)
return ERROR;
InitQueue(&tempQ);
(1);
brotherptr=root一>nextbrother;
while( brotherptr ){
EnQueue( &tempQ, brotherptr);
(2),
}/*end-while*/
while( (3) ){
(4),
printf(”%c\t”,ptr一>data);
if( (5) )continue;
(6),
brotherptr=ptr一>firstchild一>nextbrother;
while(brotherptr){
EnQueue(&tempQ,brotherptr);
(7);
}/*end—while*/
}/*end-while*/
return OK;
}/*LevelTraverse*/
选项
答案
(1)EnQueue(&tempQ,root)。 (2)brotherptr=brotherptr->nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(&tempQ,&ptr)。 (5)!ptr->firstchild。 (6)EnQueue(&tempQ,ptr->firstchild)。 (7)brotherptr=brotherptr->nextbrother。
解析
解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的:首先将树根结点入队,然后将其所有兄弟结点入队(当然,由于是根结点,故无兄弟结点);完成这一操作以后,便开始出队、打印;在打印完了之后,需要进行一个判断,判断当前结点有无孩子结点,若有孩子结点,则将孩子结点入队,同时将孩子结点的所有兄弟结点入队;完了以后继续进行出队操作,出队后再次判断当前结点是否有孩子结点,并重复上述过程,直至所有结点输出。
这一描述可能过于理论,难以理解,接下来以本题为例来说明此过程。首先将树根结点D入队,并同时检查是否有兄弟结点,对于兄弟结点应一并入队。这里的D没有兄弟结点,所以队列此时应是:
D
接下来执行出队操作。D出队,出队以后检查D是否有子结点,经检查,D有子结点B,所以将B入队,同时将B的兄弟结点:A和E按顺序入队。得到队列:
B
A
E
接下来再执行出队操作。B出队,同时检查B是否有子结点,B无子结点,所以继续执行出队操作。A出队,同时检查A是否有子结点,A有子结点F,所以将F入队,同时将F的兄弟结点P入队。得到队列:
E
F
P
接下来再次执行出队操作。E出队,E有子结点C,所以C入队。得:
F
P
C
接下来再次执行出队操作。F出队,F无子结点,继续出队操作,P出队,仍无子结点,最后C出队,整个过程结束。
通过对算法的详细分析,现在便可轻松得到答案。(1)应是对根结点root执行入队操作,即.EnQueue(&tempQ,root)。(2)在一个循环当中,循环变量是brotherptr,此变量无语句对其进行更新,所以(2)必定是更新brotherptr。结合前面的算法分析可知(2)应填:brotherptr=brotherptr->nextbrother。(3)、(4)加上后面的语句“printf(“%c\t”,ptr->data);”是控制数据的输出,这些数据应是从队列中得到,所以此处必有出队操作,同时在出队之前应判断队列是否为空,所以(3)、(4)填:!IsEmpty(tempQ)和DeQueue(&tempQ,&ptr)。(5)实际上是问“在什么情况下,要持续进行出队操作?”,前面的算法分析中已指出:若出队结点无子结点,则继续进行出队操作,所以(5)填!ptr->flrstchild。(6)和(7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队,所以(6)填:EnQueue(&tempQ,ptr->firstchild)。(7)和(2)相同,填brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://jikaoti.com/ti/uYi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?请指出图1-12中(3)空缺处的网络名称。在如图1-12所示的网络拓扑结构中,(4)空缺处所使用的设备至少应提供哪几种物理接口?
阅读以下说明,回答问题1~7。【说明】在IMail管理器中,选中MailUser邮件主机,然后在它右边的面板中选中"General"选项卡,出现一个邮件配置窗口,如图2-3所示。
阅读以下有关网络规划的叙述,回答问题1、问题2和问题3。网络工程是一项复杂的系统工程,一般可分为网络规划、网络设计、工程实施、系统测试验收和运行维护等几个阶段。网络规划是在需求分析的基础上,进行系统可行性分析和论证,以确定网络总体方案。网络规划阶段
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
阅读以下说明,回答问题1、问题2和问题3,将解答填入对应栏内。[说明]在因特网的发展过程中,WWW(WorldWideWeb)和域名服务系统(DNS)两项技术起了重大的推动作用,在域名服务系统(DNS)出现之前,所有的因特网主机名都存储
上述配置中是否有问题?请指出并说明理由。解释配置中画线部分内容含义?
阅读以下说明,回答【问题1】~【问题4】,将解答填入空白处。【说明】某小型单位的网络图如图5所示,Cisco路由器有ISDN模块,单位通过ISDN连接Internet。ISDN是指近年来供最终用户使用的一套数字服务,包括电话网络的数字化,以便ISP
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。在最理想和保守的估计中加速开发进度要着重抓的共同环节是哪些?请用50字以内的文字加以说明。
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。请指出图7-15可能存在的关键路径是什么?(请用英文字母序号列出)
随机试题
土的膨胀性试验包括()。
女性,47岁,门脉高压症引起食管、胃底静脉曲张破裂m血致休克。经三腔管压迫后并发吸入性肺炎,已输血,应用抗生素。后病人出现鼻出血、淤斑,查血小板50×109/L,纤维蛋白原1g/L,凝血酶原时间较正常延长4秒,副凝固试验阳性。应考虑病人的情况是
一平面简谐横波的波动表达式为y=0.05cos(20πt+4πx)(SI)。取k=0,±1,±2,…,则t=0.5s时各波峰所在处的位置为()。
企业应在固定资产维护支出发生时,根据固定资产的使用地点和用途,一次性计入()等账户。
定期报告中的特殊披露要求不包括()。
2017年11月,A公司赊销一批商品给B公司,含税价为15万元。由于B公司发生财务困难,无法偿付该应付账款。2018年6月1日,A公司与B公司进行债务重组,A公司同意B公司以其普通股3万股抵偿该项债务,该股票每股面值为1元,每股市价为4元。A公司对该项债权
()被后世誉为“百代画圣”。
()认为学习的基础是学习者内部心理结构的形成和改组,教学就是促进学习者内部心理结构的形成和改组。
自由七艺
设A=,B为3阶非零矩阵,为BX=0的解向量,且AX=α3有解。求常数a,b。
最新回复
(
0
)