首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
阅读以下说明和C函数,填补代码中的空缺(1)~(6),将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],cou
admin
2016-05-11
56
问题
阅读以下说明和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编辑状态下,有些英文单词或汉字下面会自动加上红色或绿色的波浪型细下划线。以下叙述中,“波浪型细下划线(44)”是错误的。
数据处理有批处理和联机实时处理两种基本的处理方式。以下各种类型的数据处理中,______宜采用联机实时处理方式。
若有以下表所示的关系R、S、T,则下列等式中正确的是(57)。
Make()copiesofimportantfiles,andstorethemonseparatelocationstoprotectyourinformation.
企业上云就是企业采用云计算模式部署信息系统。企业上云已成为企业发展的潮流,其优势不包括()。
在Excel2007的A1单元格中输入函数“=LEFT(“CHINA”,1)”,按回车键后,则A1单元格中的值为()。
在Excel的A1单元格中输入函数“=6+16+MAX(16,6)”,按回车键后,A1单元格中显示的值为__________。
()是移动互联网的组成部分。
信息处理技术员在编辑文稿时发现的如下几种错误中,最严重的错误是______。
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。说明某公司内部有一个采用TCP/IP作为传输协议的100BASE-TX局域网,包括1台服务器和20台客户机,通过一台16端口的交换机与一台8端口共享集线器级连,其网络结构如图11所
随机试题
影响细胞内外水分布的主要因素是()
术后病人出现血栓性静脉炎,护士应准备给予护理,以防止()
A.腹膜炎B.腹膜纤维化C.腹透管移位D.腹透管周围网膜包绕E.腹透管堵塞某患者尿毒症腹膜透析近3年,过程顺利,1天前发现腹透液完全不能流出,最大可能原因是
尿中蛋白质含量超过多少时称为“蛋白尿”
患儿,男,4岁,因肾病综合征入院,表现有水肿、蛋白尿,目前无感染迹象。患儿入院后,护士为他制订护理计划,下列哪项不妥
下列工程建设项目,经批准可以不进行施工招标的包括()。
由于人机系统中的可靠性的因素众多且随机变化,因此人的可靠性是不稳定的,则人机系统可靠度采用()来提高。
在企业战略咨询时,以下关于资料收集的说法,错误的是()。
把黑桃、红桃、方片、梅花四种花色的扑克牌按黑桃10张、红桃9张、方片7张、梅花5张的顺序循环排列。问:第2015张扑克牌是什么花色?
A、 B、 C、 D、 A
最新回复
(
0
)