首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
admin
2009-02-15
50
问题
请认真阅读以下函数说明、图及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
程序员下午应用技术考试
软考初级
相关试题推荐
在Word2007的编辑状态下,可以同时显示水平标尺和垂直标尺的视图模式是(37)________________。
计算机硬件唯一能够直接识别和处理的语言是(30)________________。
在PowcrPoint2010中,将一张幻灯片中的图片及文本框设置成一致的动画显示效果后,________________。
某商场购进了一批洗衣机,加价25%销售了60%后,在此基础上再打8折销完,则这批洗衣机的总销售收入相对于进价总额的利润率为________________。
下面关于幻灯片打印的叙述中,正确的是______。
在浏览网页时,当鼠标指针移至某些文字或某些图片时,会出现手形状,通常是由于网页在这个地方做了(17)。
在统计学中,用来衡量一个样本中各个数据波动大小的量是______。
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
(1)是固化在主板ROM内的程序,为计算机提供最底层、最直接的硬件访问和控制。
在Windows7运行时,为强行终止某个正在持续运行且没有互动反应的应用程序,可按组合键Ctrl+Alt十Del启动(24)________________,选择指定的进程和应用程序,结束其任务。
随机试题
试列举出外圆柱表面三种常用的加工方法。
十二指肠球部后壁溃疡并发大出血,血管多来自
关于工作分解结构的说法,正确的有()。
【背景资料】某办公大楼由主楼和裙楼两部分组成。平面呈不规则四方形,主楼29层,裙楼4层,地下2层,总建筑面积81650m2。该工程5月份完成主体施工,屋面防水施工安排在8月份。屋面防水层由一层聚氨酯防水涂料和一层自粘SBS高分子防水卷材构成。裙楼
如果“长期待摊费用”项目不能在以后会计期间受益的,应当将尚未摊销的该项目的摊余价值全部转入当期损益。()
某旅游团计划乘16:00的航班离开北京飞往香港,地陪小唐应在()之前将该团送到机场。
仲裁是指纠纷当事人在自愿基础上达成协议,将纠纷提交司法机构的第三者审理,由第三者作出对争议各方均有约束力的裁决的一种解决纠纷的制度和方式。()
甲、乙两校图书馆的存书量之比为7:5,如果甲校给乙校10本书,那么两校的存书量之比就变为4:3。但实际上乙校给了甲校一些书,导致两校的存书量之比变为2:1。那么,乙校给了甲校多少本书?
Ishalltellhimthetruth,______.
以下关于VBA运算符优先级比较,正确的是()。
最新回复
(
0
)