首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
admin
2009-02-15
52
问题
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。
【说明】
一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图5-9(a)所示的树和如图5-9(b)所示的树的孩子一兄弟表示。
函数LevelTraverse()的功能是对给定树进行层序遍历。例如,对如图5-9所示的树进行层序遍历时,节点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如表5-12所示。
Bool、Status类型定义如下:
typedef enum{FALSE=0, TRUE=1}Bool;
typedef enum{OVERFLOW=-2, UNDERFLOW=-1, ERROR=0, OK=1)Status;
树的二叉链表节点定义如下:
typedef struct N6de{
char data;
struct Node *firstchild, *nextbrother;
}Node, *TreeNode;
【C函数程序】
Status LevelTraverse(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=brotherptr->nextbrother (3)!IsEmpty(tempQ),或其等价形式 (4)DeQueue(&tempQ,&ptr) (5)!ptr->firstchild,或其等价形式 (6)EnQueue(&tempQ,ptr->firstchild) (7)brotherptr=brotherptr->nextbrother
解析
这是一道要求读者掌握树结构的存储及遍历运算的程序分析题。本试题的解答思路如下。
队列可以保证访问节点时按照层次和自左至右的顺序。借助队列结构对树进行层序遍历时,每个节点都进出队列一次,节点出队列时进行访问。其过程是,首先令树根节点入队,若是森林(树根之间互为兄弟),接着则令其余树的根节点入队,然后在队列非空的情况下,队头节点出队,访问该节点同时令其孩子节点入队。依此类推,直到队列为空。
在试题所给出的【C函数程序】中,代码“InitQueue(&tempQ); (1) ;”完成初始化队列并令根节点入队列的功能,因此(1)空缺处所填写的内容是“EnQueue(&tempQ,root)”。
采用二叉树存储树结构时,其右分支表示兄弟关系,因此队头节点出队时,应沿右分支将队头节点的所有孩子依次加入队列。(2)空缺处所在的while循环完成处理第一棵树的兄弟节点的功能,因此,(2)空缺处所填写的内容是“brotherptr=brotherptr->nextbrother”。至此,就完成了第一层节点的处理。
(3)空缺处用于判断队列是否为空,即应填入“!IsEmpty(tempQ)”或其他等价形式。
使用队列或栈结构存储元素以实现某种运算的基本特点是,当队列非空时,应令队头元素出队列。因此(4)空缺处所填写的内容是“DeQueue(&tempQ,&ptr)”。
若一个节点不存在孩子,则其firstchild指针域为空,也无须令其孩子节点入队列。因此,(5)空缺处所填写的内容是“!ptr->firstchild”或其他等价形式。反之,若一个节点有孩子,则应首先令其第一个孩子节点入队列,然后通过右分支链使其他孩子节点入队列。因此,(6)空缺处所填写的内容是“EnQueue(&tempQ,ptr->firstchild)”,(7)空缺处所填写的内容是“brotherptr=brotherptr->nextbrother”。
转载请注明原文地址:https://kaotiyun.com/show/oIjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
某一个PPT文档共有8张幻灯片,现选中第4张幻灯片,改变幻灯片背景设置后,单击“应用”按钮,则______。
在Word2007文档编辑时,使用(39)________________选项卡中的“分隔符”命令,可以在文档中指定位置强行分页。
《数据中心设计规范》GB50174-2017属于()。
在Excel2010中,设单元格A1、B1、C1、A2、B2、C2中的值分别为1、2、3、4、5、6,若在单元格D1中输入函数“=MAX(A1:A2,B1:C2)”,按回车键后,则D1单元格中的值为(
企业建立生产和库存管理系统的目的不包括()。
某企业去年四次核查的钢材库存量情况如下表:用加权平均法计算出该企业去年钢材平均库存量为()吨(中间各次核查数据的权都取1,首次与末次核查数据的权都取0.5)。
上级要求信息处理技术员做a、b、c、d、e五件工作。先做什么,后做什么,如何安排呢?根据工作性质以及紧急程度,他列出了如下几条规则:a应在b前 c应在a前 d应在a前 a应在e前d应在b前 b应在e前 c应在d前 c应在
在浏览网页时,当鼠标指针移至某些文字或某些图片时,会出现手形状,通常是由于网页在这个地方做了(17)。
打开DOC文档48.doc,有如下表格,欲在空白单元格中计算出整行其他四个单元格的数值之和,应在空白单元格中插入公式(48)。
阅读下列说明,回答问题1至问题6。【说明】特洛伊木马是一种基于客户端朋艮务器模式的远程控制程序,黑客可以利用木马程序入侵用户的计算机系统。木马的工作模式如图4-8所示。
随机试题
我国进行卫生立法活动的基础和依据是
属于反治的是()
气雾剂中的抛射剂压片时的润滑剂
胃镜检查病人的护理下列哪一项是错误的()
应在婴儿饮食中添加米汤及稠粥的婴儿月龄是
患者,男性,50岁。右上腹胀痛3个月伴黄疸3周。体检肝肋下3cm,剑突下4cm,质硬,移动性浊音(+)。B超:肝内有一占位性病变。最可能的诊断为
既有结构的安全性评定包括()评定项目。
根据《中华人民共和国合同法》相关规定,因不可抗力不能履行合同的,根据不可抗力的影响,部分或者全部免除责任,但法律另有规定的除外。下列选项中,可以完全免除法律责任的是( )。
秦腔俗名“______”、“桄桄子”,在漫长的历史过程中积累了______多个剧目。
RIP是距离矢量协议,它利用跳数作为其计量标准,是一种外部网关协议。()
最新回复
(
0
)