首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
admin
2016-05-11
70
问题
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。
【说明】
二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],counter
存放第i层上的结点数,并按照层次顺序来遍历二叉树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。
按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BTNode{
TElemType data;
struct BTNode *left,*right;
)BTNode,*BiTree;
队列元素的类型定义如下:
typedef struct {
BTNode*ptr;
int LevelNumbe r;
)QElemType;
GetWidth()函数中用到的函数原型如下所述,队列的类型名为QUEUE:
【C函数】
int GetWidth(BiTree root)
{
QUEUE Q;
QElemType a,b;
int width,height=GetHeight(root);
int i,*counter=(int*)calloc(height+l,sizeof(int)};
if( (1) ) return一1; /*申请空间失败*/
if(!root) return 0; /*空树的宽度为0*/
if( (2) ) return一1; /*初始化队列失败时返回*/
a.ptr=root; a.LeveiNumber=1;
if(!EnQueue(&Q,a))return一1 ; /*元素入队列操作失败时返回*/
while(!isEmpty(Q)){
if( (3) )return一1; /*出队列操作失败时返回*/
counter[b.LevelNumber]++;/*对层号为b.LevelNumber的结点计数*/
if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/
a.ptr=b.ptr一>left;
a.LevelNumber= (4) ;
if(!EnQueue(&Q,a))return一1;
}
i f(b.ptr一←right){/*若右子树存在,则右子树根结点及其层次号入队*/
a.ptr=b.ptr一←right;
a.LevelNumber= (5) ;
if(!EnQueue(&Q,a))return一1;
}
}
width:counter[1];
for(i=1;i<height+1;i++) /*求counter[]中的最大值*/
if( (6) ) width=counter
;
free(counter);
return width;
}
选项
答案
(1)!counter或0=counter或NULL=counter或等价表示 (2)!InitQueue(&Q) 或0=InitQueue(&Q) 或等价表示 (3)!DeQueue(&Q,&b)或0=DeQueue(&Q,&b) 或等价表示 (4)b.LevelNumber+1 或等价表示 (5)b.LevelNumber+1 或等价表示 (6)counter[i]>width 或等价表示
解析
本题考查数据结构实现和C语言基本应用。
考生需要认真阅读题目中的说明,以确定代码部分的处理逻辑,从而完成代码。
根据注释,空(1)处应填入“!counter”或其等价形式。
由于初始化队列的函数原型为“InitQueue(QUEUE*Q)”且返回值为0表示操作失败,因此调用该函数时实参应取地址,即空(2)处应填入“!InitQueue(&Q)”或其等价形式。
空(3)处需进行出队列操作,同时通过参数得到队头元素,根据说明,该空应填入“!DeQueue(&Q,&b)”或其等价形式。
出队操作后,得到的队头元素用b表示,根据队列元素的类型定义,其对应结点在二叉树中的层次号表示为b.LevelNumber,显然,其孩子结点的层次号应加1,因此空(4)和(5)处应填入“b.LevelNumber+1”。
从代码中可知变量width的作用是表示最大的层次编号,并通过顺序地扫描数组counter中的每一个元素来确定width的值,显然,空(6)处应填入“counter
>width”或其等价形式。
转载请注明原文地址:https://kaotiyun.com/show/t9jZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在Word中采用(47)可实现下图显示的排版格式。
数据录入工作有两个指标:录入速度和错误率。一般而言,数据录入员在录入大批数据时,录入速度会(65),错误率会(66)。66
删除Windows中某个应用程序的快捷方式,意味着(39)。
在Excel的A1单元格中输入函数“=6+16+MAX(16,6)”,按回车键后,A1单元格中显示的值为__________。
在Excel2010中,一个宗箱的函数计算包括()。
下列关于Word绘图功能的叙述中,不正确的是__________。
以下定性的分类变量中,(9)属于有序变量(能排序)。
数据处理过程中经常会发生数据出错,因此,数据校验工作非常重要。实际工作中一般都需要采取某些有效的数据校验措施,但有些做法是很少采用的。例如,在每个处理阶段结束后,要求(26)。
请根据网页显示的效果图(见图6-3)和网页中的元素说明回答问题。
网页留言效果如下图所示,网页文档如下,请参照表格给出的说明在下划线处填写正确的答案到答题纸对应的栏内。[上图网页中的元素说明] [HTML文本]<!DOCrYPEHTMLPUBLIC“-//W3C//DTDHTML
随机试题
修约后要求小数点后保留一位A、23.2B、23.3C、23.5D、23.8E、23.9修约前数字为23.2501
A.化学药品价格B.中药价格C.中成药价格D.处方药价格E.非处方药价格国务院价格主管部门负责制定国家基本医疗保障用药中的
液压和润滑管道冲洗在酸洗合格后进行,冲洗液应采用()。
债务人或者管理人应当自人民法院裁定债务人重整之日起6个月内,同时向人民法院和债权人会议提交重整计划草案。下列各项中,属于重整计划草案内容的有()。
党对公安工作绝对领导的必要性包括()。
Thefollowingquestionspresentasentence,partofwhichorallofwhichisunderlined.Beneaththesentence,youwillfindfiv
Lookatthefollowingopinionsordeedsandthelistofpeoplebelow.Matcheachopinionordeedwiththecorrectperson,A,
Imadeapledgetomyselfonthewaydowntothevacationbeachcottage.FortwoweeksIwouldtrytobealovinghusbandandfa
Afterdecadesofdecline,theshareofmotherswhostayhomewiththeirchildrenhas【C1】______risenoverthelastseveralyears
A、Becauseallroomsaretaken.B、Becausemanyspareroomsareavailable.C、Becausethereareonlydoublerooms.D、Becausethere
最新回复
(
0
)