首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。 【说明】 一般的树结构常采用孩子一兄弟表示法表示,即用二叉链表代表树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点,例如,如图
admin
2009-02-15
41
问题
请认真阅读以下函数说明、图及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://jikaoti.com/ti/TkW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
信息处理组长感到日常的信息处理工作效率不高,而且容易出错。为解决这个问题,一般来说,应重点采取的技术措施是()。
“位”(bit)是计算机的最小信息单位,一般把连续的(30)称为一个字节(Byte)。
在Word2007中,字符样式应用于__________。
以下关于数据处理的叙述中,不正确的是(1)________________。
目前最常见的用户界面是________________。
某企业甲乙两个部门招聘职工中,男女应聘人数和录用人数情况如下表:从上表看出,各部门女性录用率都大于男性录用率。从该企业合计来看,()。
下面关于幻灯片打印的叙述中,正确的是______。
在网页中创建一个如下图所示的表单控件的HTML代码是(26)。
在选择多媒体数据压缩算法时需要综合考虑(24)。
随机试题
警跻人
寄生虫病自然疫源地所具备的条件,哪项是错误的
增殖型肠结核患者不经常出现的临床表现是
贸易术语的国际贸易惯例主要有()。
下列关于预收款的特点说法不正确的有()。
公共支出,也称财政支出或政府支出,是政府为履行其职能而购买相应商品和劳务从而支出的一切费用的总和。政府进行货币资金支出的活动,其行为依据是()。
某超市出售四种水果礼盒,其中礼盒一有3颗苹果4颗梨,售价20元;礼盒二有4颗苹果3颗梨,售价22元;礼盒三有5颗苹果6颗梨,售价32元;礼盒四有6颗苹果2颗梨,售价28元。小张从中选购得到11颗苹果8颗梨,请问小张结账时要支付多少钱?
A:CanIseeyourdrivinglicence?B:______
数据库管理系统中用来定义模式、内模式和外模式的语言为
A、Mostnicknamesarequiteinteresting.B、Somestatenicknameshavesurprisingorigins.C、GeorgeWashingtonhasmanynicknames.
最新回复
(
0
)