首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
admin
2016-05-11
26
问题
阅读以下说明和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://jikaoti.com/ti/zHW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
E-mail一般的格式是______。
LCD显示器的响应时间为(2)时,显示的效果更好。
某机构准备发布中国互联网发展年度报告。报告分四个方面:全网概况、访问特征、渠道分析和行业视角。用户24小时上网时间分布应属于()方面的内容。
某企业的大数据工程项目包括如下四个阶段的工作:①数据获取,②数据清洗与整理,③数据分析,④数据展现。一般来说,工作量较大、花费时间较长的阶段是______(1),技术含量最高的阶段是______(2),准备向有关部门递交成果的阶段是______(3)。
在Excel中,若单元格C5=1000、D5=50、C6=6000、D6=40,在单元格E5中输入公式“=C5*$D$5”,再将此公式复制到F6单元格中,则F6单元格的值为(54)。
在文档中插入形状“圆”后,在圆心位置输入了字符C却看不到,为将字符C显示出来,可以右击该形状,选择将其__________。
在Excel中,设单元格A1中的值为80,B1中的值为35,若在C1单元格中输入函数“=IF(AND(A1>=60,B1>=60),“不及格”,“补考”)”,按回车键后,C1单元格中的值为()。
Word中“编辑”菜单下的“定位”命令的功能不能够定位(47)。
在Excel中,A1,A2,B1,B2,C1,C2单元格的值分别为1、2、3、4、3、5,在D1单元格中输入函数“=SUM(A1:B2,B1:C2)”,按回车键后,D1单元格中显示的值为______。
网页留言效果如下图所示,网页文档如下,请参照表格给出的说明在下划线处填写正确的答案到答题纸对应的栏内。[上图网页中的元素说明] [HTML文本]<!DOCrYPEHTMLPUBLIC“-//W3C//DTDHTML
随机试题
有以下程序:#include<stdio.h>main(){intsum=10,n=1;while(n<3){sum=sum—n;n++;}printf("%d,%d",n,sum);}
防民之口,甚于防川。川壅而溃,伤人必多。
A.分泌性腹泻B.渗透性腹泻C.渗出性腹泻D.动力性腹泻E.吸收不良性腹泻胃泌素瘤所致腹泻属于
有关肾区疼痛.下列哪项不正确?
“氨基糖苷类联用呋塞米导致肾、耳毒性增加”显示药源性疾病的原因是()。
根据《中国执业药师职业道德准则适用指导》,执业药师应当
关于承运人权利和义务的说法正确的是:
双亲杂交后,从母本植物上得到的种子以及由该种子长成的植株称杂种一代。()
将19分解成3个不重复数字(1至9)之和(不计顺序)的方法共有______种。
A、HewillgotoCanadaforvacation.B、Hewilljuststayathome.C、Hewilldosometemporaryjobtoearnsomemoney.D、Hewill
最新回复
(
0
)