首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
admin
2017-08-31
43
问题
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整在图4-8所示的网络拓扑结构中,无线接入点AP1控制的所有终端组成一个(7)。最适合在图4-8所示的ADSL接入网上实时传输视频数据的MPEG系列标准是
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?图1-12中(2)空缺处是什么设备?该设备在本宽带网络中完成哪些功能?
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1、问题2和问题3。现以一台远程访问服务器(RemoteAccessServer,RAS)Cisco2509、RJ45为例来说明。第1步,准备安装与调试所需的设备,主要包
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]Web服务器是在网络中为实现信息发布、资料查询、数据处理等诸多应用搭建基本平台的服务器。处理Web页面大致可分为3个步骤,原理如图8-2所示,域名是www
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在相应位置。
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
如果在网络设计过程中划分了很多VLAN,则可采用VTP来简化其管理。交换机管理IP地址只能创建在(1)中,而VTP信息只能在(2)端口上传播。共享相同VLAN数据库的交换机构成一个(3)。不同交换机平台、不同的IOS版本支持的VLAN数量不同,从图6-18
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。项目管理就是以项目为对象的系统管理方法,通过一个临时性的专门的柔性组织,对项目进行高效率的计划、组织、指导和控制,以实现项目全过程的动态管理和项目目标的综合协调与优化。除了本题涉及到
在如图1-23所示的网络拓扑结构图中,被路由协议可以使封装后的数据包通过互连网络进行中继传输,它由(1)使用。【供选择的答案】A.PCIB.RouterA和RouterBC.Internet网D.Rcrate
随机试题
Itiswidelybelievedthathighlyeducatedstudentsaremorelikelytogetagoodjob.However,atanon-campusjob【C1】______in
患儿,3岁。平时体弱,经常感冒发热。曾多次因患"肺炎"住院。化验:血IgG、IgM、IgA总量为300mg/L。E-玫瑰花环形成试验、淋巴母细胞转化试验分别为0.60、0.65。为减少反复感染,给患儿下列哪项处理最为需要
宗地图是描述宗地位置、界址点线关系。相邻宗地编号的分宗地籍图,用来作为该宗土地产权证书和地籍档案的附图。宗地图中包括()。
背景资料:某施工双代号网络进度计划如下图所示,其中A、B、D工作使用同一种施工机械,开工前有一台施工机械出现故障,导致可使用的该机械只有一台,根据现场施工条件,工作顺序调整为B、A、D,设备租赁费2000元/天。问题:
宝绘堂记(宋)苏轼君子可以寓意于物,而不可以留意于物。寓意于物,虽微物足以为乐,虽尤物不足以为病。留意于物,虽微物足以为病,虽尤物不足以为乐。老子日:“五色令人目盲,五音令人耳聋,五味令人口爽,驰
党委领导下的群众路线包含的含义包括()。
2004年3月15日,洪海市雅居房地产公司合法取得位于市区的能够进行商品房开发#3地块的土地使用权,2006年3月,该#3地块上开发出“海滨雅居”进行销售,甲花费60万元在“海滨雅居”购得一套住房。入住使用后,甲发现房屋由于设计错误存在严重的结构缺陷。在与
规则:游戏
吉翂,字彦霄,冯翊莲勺人也。世居襄阳。翂幼有孝性。年十一,遭所生母忧,水浆不入口,殆将灭性,亲党异之。天监初,父为吴兴原乡令,为奸吏所诬,逮诣廷尉。翂年十五,号泣衢路,祈请公卿,行人见者,皆为陨涕。天监其父理虽清白,耻为吏讯,乃虚自引咎,罪当大辟。翂乃挝登
有如下Excel2007工作表,在A8单元格中输入函数“=COUNTA(B4:D7)”,按回车键后,则A8单元格中的值为(50);要计算张丹的销售业绩,应在E4单元格中输入函数(51);销售奖金的计算方法是某种商品销售量大于等于70奖励500元,小于70
最新回复
(
0
)