首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
admin
2009-02-15
38
问题
请认真阅读以下函数说明、图及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
程序员下午应用技术考试
软考初级
相关试题推荐
假设“EXAM.DOC”文件夹存储在“EXAM1”文件夹中,“EXAM1”文件夹存储在“EXAM2”文件夹中,“EXAM2”文件夹存储在F盘的根文件夹中,当前文件夹为“EXAM1”。那么,正确描述“EXAM.DOC”文件的绝对路径表示为(37)。
《信息处理系统一开放系统互连一基本参考模型》(ISO7498-2:1989)属于(63)________________。
下列关于索引的叙述中,正确的是________________。
操作系统的资源管理功能不包括________________。
在Word2010文档中,某个段落最后一行只有一个字符,()不能把该字符合并到上一行。
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。33.
在Excel中,B2单元格的内容为123,A1单元格中的内容为“=B2”,当用Delete键删除B2单元格的内容后,则A1单元格显示(55)。
由国家机关下达任务开发的软件,若在项目任务书或者合同中对软件著作权未作明确规定的,其软件著作权由(21)享有。
请认真阅读下列有关代理服务器的说明信息,然后根据要求回答问题1至问题6。【说明】某单位通过电信部门提供的ADSL与Internet相连,并通过代理服务器使内部各计算机终端访问Internet,连接方式如图1-1所示。电信部门分配的公网IP地址为2
请根据图2-13网页的显示效果,解释该ASP程序中用下画线标出的语句的含义,即填写(1)、(3)、(4)、(6)、(10)空缺处的解释内容。在index.asp文档中使用了<styletype="text/css">语句。其中,CSS是指(10),
随机试题
获得光滑表面的加工方法是()。
A.普萘洛尔B.去甲肾上腺素C.异丙肾上腺素D.多巴胺E.酚妥拉明
患者,男性,32岁。皮肤反复出现紫癜1个月,加重并出现恶心、腹痛2天。查体:四肢皮肤散在紫癜,心肺未见异常,腹平软,脐周轻压痛,无反跳痛和肌紧张,肝脾肋下未触及,肠鸣音活跃。该患者目前不需要的治疗药物是
某消化性溃疡病人,原有疼痛节律消失,变为持续上腹疼痛,伴频繁呕吐,呕吐物含发酵性宿食。最可能的并发症是
转让旧房产,计算其土地增值税增值额时准予扣除的项目有()。
斯坎伦计划属于的管理方式是()。
练习企业合并及不丧失控制权情况下处置部分对子公司投资的处理甲股份有限公司(本题下称“甲公司”)为上市公司,2009年至2011年企业合并、长期股权投资有关资料如下:(1)2009年1月20日,甲公司与乙公司签订购买乙公司持有的丙公司(非
《物业管理条例》确立的基本法律关系有社区居委会与业主、业主大会及物业服务企业的关系,物业管理各方主体与政府之间的关系()。
根据《最高人民法院、最高人民检察院、公安部、司法部关于开展社区矫正试点工作的通知》,社区矫正的适用范围包括()
设则下列矩阵中与A合同但不相似的是[img][/img]
最新回复
(
0
)