首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表作树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,题图4-1(a)所示的树
阅读下列说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表作树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,题图4-1(a)所示的树
admin
2018-07-23
84
问题
阅读下列说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表作树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,题图4-1(a)所示的树的孩子一兄弟表示如题图4-1(b)所示。
函数LevelTraVerse()的功能是对给定树进行层序遍历。例如,对题图4-1所示的树进行层序遍历时,节点的访问次序为:D B A E F P C。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如下表所示。
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 Leve1Traverse(TreeNode root)
{ /*层序遍历树,树采用孩子一兄弟表示法,root是树根节点的指针*/
Queue tempQ;
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->firstchiid->nextbrother;
while(brotherptr){ EnQueue(&tempQ,brotherptr);
____(7);
} /*end-while*/
) /*end-while*/
return OK;
) /*LevelTraverse*/
选项
答案
(1)EnQueue(&tempQ,root)(2)brotherptr=brotherpt->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出队,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->nrstchild。空(6)处和空(7)处所在的语句段的功能是将刚出队节点的子节点及其兄弟节点入队,所以空(6)处应填入EnQueue(&tempQ,ptr->jfirstchild)。空(7)处和空(2)处相同,应填入brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://kaotiyun.com/show/MKDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下关于交换机VTP协议配置的技术说明,根据要求回答问题1至问题4。【说明】利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。利用showvtpstatus命令在某台交换机的特权模式
阅读以下在政务网中基于MPLS的IP-VPN应用服务的技术说明,回答问题1至问题5。【说明】为了保证政务外网各系统的安全,必须要为各系统的网络互联提供安全隔离及网络服务质量保证,使用基于MPLS的IP-VPN是在IP网上解决这种安全隔离的一种较好
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
请说出(1)、(2)、(3)、(4)、(5)对应行的含义。(1)图6-3是Windowsxp的DNS设置窗口,请指出图6-3中配置错误之处。(2)在Windowsxp系统中,根据图6-3中的相关信息,请写出默认路由。(3)图6-
阅读以下说明,回答问题1和问题2。【说明】某学校拟组建一个小型校园网,具体设计如下:1.设计要求。(1)终端用户包括:48个校园网普通用户;一个有24个多媒体用户的电子阅览室;一个有48个用户的多媒体教室(性能要求高于电子阅
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。数据库系统存储了大量的数据,在发生意外的情况下,为了确保数据能够尽可能准确地恢复,数据库系统提供了备份和恢复的功能。通常,数据库管理系统都提供了全部数
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。备份就是对数据文件的备份,备份网络文件就是将所需要的文刊:复制到光盘、磁带或磁盘等存储介质上。这种备份网络文件的思路是否正确?请用200字以内的文字简
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
随机试题
关于低位乳牙,以下不正确的说法是
泄泻之内因,关键在()
对碱呈红色的化合物是
何先生,30岁,2年前因胃溃疡做过胃切除术,近半年来经常头晕、心悸,体力逐渐下降,诊断为缺铁性贫血。其外周血红细胞形态主要为
2017年10月高校教师张某取得一次性技术服务收入4200元,支付交通费300元。已知劳务报酬所得个人所得税税率20%,每次收入不超过4000元的,减除费用800元;每次收入在4000元以上的,减除20%的费用。张某当月该笔收入应缴纳个人所得税税额的
下列有关统计抽样和非统计抽样的说法中,正确的有()。
下列选项中,关于让渡资产使用权收入的说法,不正确的是()。
交通运输具有物质生产的属性和生产资料的属性。()
唐朝是丝绸生产的__________时期,无论产量、质量和种类都达到了前所未有的水平。丝绸的生产组织分为宫廷手工业、农村副业和独立手工业三种,__________较前代大大扩大了。依次填入画横线部分最恰当的一项是()。
许多孕妇都出现了维生素缺乏的症状,但这通常不是由于孕妇的饮食中缺乏维生素,而是由于腹内婴儿的生长使她们比其他人对维生素有更高的需求。为了评价上述结论的确切程度,以下哪项操作最为重要?( )
最新回复
(
0
)