首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
admin
2016-05-11
57
问题
阅读以下说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
某年级两个班举行了一次数学统考,一班(共30人)的平均成绩为70分,二班(共 20人)的平均成绩为75分,则该年级的平均成绩为(65)分。
下列事件中,确定事件是______。①掷一枚硬币正面朝上。②打开电视机,正在播电视剧③随意翻丌一本书,正好翻到第100页④天下雨,地面湿⑤你身高不能长到4米⑥买奖券中特等大奖⑦掷一枚骰子的点数小于8
计算机病毒是一段程序,一般隐藏在______中。
以下关于操作系统中回收站的叙述,不正确的是____________。
在WindowsXP中,删除某个应用程序在桌面上的快捷方式,则(42)。
下列选项中,不能收发电子邮件的软件是______。
在Windows 2000操作系统的客户端可以通过(14)命令查看DHCP服务器分配给本机的IP地址。
在Excel2010中,一个宗箱的函数计算包括()。
防火墙包过滤规则的默认策略为拒绝,下表给出防火墙的包过滤规则配置界面。若要求内部所有主机能使用IE浏览器访问外部IP地址为202.117.118.23的Web服务器,为图中(1)~(4)空缺处选择正确答案。(1)A.允许B.拒绝(2)A.192
[说明]请根据网页显示的效果图,将HtML文本(n)处的解答填写在相应的解答栏内。[上图网页中的元素说明][HTML文档代码]<!DOCTYPEHTMLPUBLIC“-//W3C//DTDHTML
随机试题
感染
A______changeinpolicyisneededifrelationsareevertoimprove.
用于哌替啶中毒的解救药物是
含漱剂按给药途径和方法属于
案情:陈某因没有收入来源,以虚假身份证明骗领了一张信用卡,使用该卡从商场购物10余次,金额达3万余元,从未还款。(事实一)陈某为求职,要求制作假证的李某为其定制一份本科文凭。双方因价格发生争执,陈某恼羞成怒,长时间勒住李某脖子,致其窒息身亡。(事
简述账务处理模块与固定资产模块之间的联系。
甲公司根据合同约定向乙公司销售价值270万元建筑材料,乙公司向甲交付一张经丙公司承兑的商业汇票,该汇票距到期日尚有3个月。甲公司持有票据一个月后,因资金紧张,将其贴现给丁银行。丁银行在汇票到期日向丙公司提示付款时,遭拒付。丙公司拒付的理由是:乙公司来函告知
企业培训体系的子体系包括()。
根据下面材料回答下列问题。699万,这是教育部统计的2013年全国普通高校毕业生的人数,比2012年增加了19万,是2000年的6.5倍多,当时的毕业生总数为107万,由于就业形势严峻,这个夏天被称为“史上最难就业季”。今年就业形势可用“一增两减”概括
Globalizationisaphenomenonthathasbeenaffectingcountriesandsocietiesforseveraldecades,buttheoutlineoftheglobal
最新回复
(
0
)