首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(
admin
2015-06-03
99
问题
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图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 *firstchiid,*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->firstchild。(6)和(7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队,所以(6)填:EnQueue(&tempQ,ptr->firstchild)。(7)和(2)相同,填brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://kaotiyun.com/show/FdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Windows2003中,(1)不能实现NAT功能。A.终端服务管理器B.Internet连接共享C.路由和远程访问部门B中主机PCI的默认网关地址应配置为(4)才能访问Internet。
该网络采用R1~R7共7台路由器,采用动态路由协议OSPF。由图1-1可见,该网络共划分了3个OSPF区域,其主干区域为(1),主干区域中,(2)为区域边界路由器,(3)为区域内路由器。该单位部门4共有110台PC机,通过交换机连接路由器R5接入网络。
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。在客户端除了可以用p
阅读以下关于在ISDN网中应用点对点协议(PPP)和按需拨号路由(DDR)技术的说明,结合网络拓扑图回答问题1至问题4。【说明】综合数字业务网(ISDN)由数字电话和数据传输服务两部分组成,提供基本速率接口(BRI)和基群速率接口(PRI)两种服
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
解释图10-2中的PVC和SVC。以下是LANE工作过程,其顺序已乱,请排序。①LEC接着便向其他LEC广播这个响应。②在地址表中含有被称为MAC地址的LEC向LEC作出响应。③LES发送多点组播至网络上的其他LEC。④
若采用电话线方式上网,并按要求在计算机连入网络的同时能通电话,连网速率高于500Kbps,可以选用哪种技术方案?其最高通信速率为多少?若采用电视铜缆接入计算机主干网络,用户端需增添什么设备?网络通信速率为多少?
阅读以下说明,回答【问题1】~【问题4】,将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是19
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
随机试题
学习马克思主义哲学的根本方法是()。
A.机体水调节B.电解质平衡C.酸碱平衡D.血钠调节E.血钙调节醛固酮影响的是
杆AB长为l,质量为m,图4-64所示瞬时点A处的速度为v,则杆AB动量的大小为()。
下列有关无效合同的说法中,错误的是()
在试算平衡表中如果试算平衡,则账簿记录一定正确。()
ABC公司正在着手编制2015年的财务计划,公司财务主管请你协助计算其加权资本成本。有关信息如下:(1)公司银行借款利率当前是10%,明年将下降为7%。(2)公司债券目前每张市价980元,面值为1000元,票面利率为8%,尚有5年到期
下列情况中,不允许从增值税销售额中扣除的有()。
需求的构成要素有()。
市场机制的核心是()。
Iremembermeetinghimoneeveningwithhispushcart.Ihadmanagedtosellallmypapersandwascominghomeinthesnow.Itwa
最新回复
(
0
)