首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表作树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,题图4-1(a)所示的树
阅读下列说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表作树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,题图4-1(a)所示的树
admin
2018-07-23
64
问题
阅读下列说明、图和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命令在某台交换机的特权模式
阅读以下关于某硬件防火墙相关配置的技术说明,根据要求回答问题1至问题4。【说明】某单位在部署内部局域网时选用了一款硬件防火墙,该防火墙分别带有“WAN”、“LAN”“DMZ”、“FUN”等4个网络接口,支持Web界面、命令行等多种管理模式。该单位
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
阅读以下说明,回答问题1、问题2和问题3,将解答填入对应栏内。[说明]在因特网的发展过程中,WWW(WorldWideWeb)和域名服务系统(DNS)两项技术起了重大的推动作用,在域名服务系统(DNS)出现之前,所有的因特网主机名都存储
阅读以下说明,回答问题1和问题2。【说明】某学校拟组建一个小型校园网,具体设计如下:1.设计要求。(1)终端用户包括:48个校园网普通用户;一个有24个多媒体用户的电子阅览室;一个有48个用户的多媒体教室(性能要求高于电子阅
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?如果ISDN收费是按每分钟计算,假如0.5元/分钟,采用ISDN基本速率接口下载1024k的文件需要付费多少?
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。某商务公司在全国各城市共有15个分支机构,这些机构已经建设了基于大型关系数据库的信息管理系统,每天负责独立地处理本区域内的业务并实时存储业务数据。每个
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
请说出图9-1的拓扑结构名称与特点。请比较交换机的堆叠与级联的区别。
随机试题
配管柱时,应将油管、短节、下井工具,按下井先后顺序在油管桥上依次连接好,并打上明显标记。()
患者老年男性,进行性排尿困难伴尿频、尿急、夜尿增多,饮酒后不能排尿10小时,B超提示前列腺5.2cm×5.0cm×4.8cm大小,膀胱过度充盈,双肾轻度积水,查PSA3.8ng/ml。首先考虑的疾病是
A.严密隔离B.接触隔离C.血液-体液隔离D.肠道隔离E.保护性隔离艾滋病患者应采取
某国家重点水利工程从境外进口一批急需物资,为加速货物通关,收货人向海关申请将该批货物转关运输至工程所在地办理海关手续。但该工:程所在地并未建立海关机构,且货物因超高超长无法封入运输装置。对此,海关将采取何种办法办理?()
下列利息收入中,需要缴纳个人所得税的是()。
按照我国企业会计准则的规定,以下关于合并资产负债表的抵销,表述正确的有()。
会计科目设计的()原则是为了适应国家宏观管理和行业管理的需要。
在下列情况下使用作品,可以不经著作权人许可,不向其支付报酬,但应当指明作者姓名、作品名称,并且不得侵犯著作权人依照本法享有的其他权利:(一)为个人学习、研究或者欣赏,使用他人已经发表的作品;(二)为介绍、评论某一作品或者说明某一问题,在作品中适当引用他
B公司目前全部用权益资本来满足其资金需求,权益资本成本为12%。现在公司打算以8%的利率发行债券,在新的资本结构下,债券市场价值为公司价值的45%,若公司所得税率为25%,计算该公司新的权益资本成本和加权平均资本成本。
货币的效用要大于消费者所购入的商品的效用,则他会()。
最新回复
(
0
)