首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
admin
2016-05-11
68
问题
阅读以下说明和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中,为将正在编辑的文档以新的文件名保存,可使用______命令。
评价信息系统时需要听取各有关方面的意见。在听取系统操作人员的意见时,主要讨论信息系统的______。
用户设置幻灯片放映时,不能做到的是(56)。
在大型分布式信息系统中,为提高信息处理效率,减少网络拥堵,信息存储的原则是:数据应尽量(66)________________。
在Excel2010中,设单元格A1、B1、C1、A2、B2、C2中的值分别为1、2、3、4、5、6,若在单元格D1中输入公式“=MAX(A1:C2)-MIN(A1:C2)”,按回车键后,则D1单元格中的值为(
以下关于操作系统中回收站的叙述,不正确的是____________。
某家用监控摄像头广告所列的功能中,(15)有错误。
程序员一般用(7)软件编写和修改程序。
由若干条直线段和圆弧等构成的图形,可以用一系列指令来描述。用这种方法描述的图形称为_________。
框架在网页布局中主要起什么作用?主页中定义了几个框架,分别显示哪个文档?假设连接的数据记录集当前指向的记录如下:写出以下ASP代码经过IIS服务器解释后的结果。<tdalign-"center"width="20%"><ahref
随机试题
A.化疗B.放疗C.根治性手术D.化疗和根治性手术骨肉瘤采用的治疗方法是
肺结核最主要的传播途径是
根据有关规范和标准,下列表述中错误的是()。
下列各项不属于物权保护方法的是()。
你认为,父母给的零花钱,孩子们应该()
短时记忆达到巅峰是在个体的()。
哥本哈根气候大会达成了《哥本哈根协议》,但该协议未获全体通过,不具有决议同等约束性执行效力。主要发达国家如美国、英国以及欧盟大部分国家都未明确表示未来碳排放的减排时间表。对于发达国家而言,当下最为紧迫的任务仍然是尽快走出全球金融危机的阴影,因而不愿意为减排
反社会人格犯罪是行为人基于反社会型变态人格而实施的犯罪行为。行为人的特点是:①智力和精神上并无明显缺陷,没有妄想或其他思维障碍;②多数有劣迹前科,有多次、多类型的违纪、违法、犯罪行为;③行为冲动、缺乏深思熟虑和明确的动机;④没有悔过和自责的心理,在
(山西政法2009—99)一片草地(草以均匀速度生长),240只羊可以吃6天,200只羊可以吃10天,则这片草可供190只羊吃的天数是()。
Whenmengrowolder,theirhairoftenbeginstofallout.Whenhairbeginstofallout【C1】______oldage,itisimpossibletomak
最新回复
(
0
)