首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
admin
2008-04-04
86
问题
阅读以下说明、图和C代码。
【说明】
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
函数LevelTraverse()的功能是对给定树进行层序遍历。例如,对图10-1所示的树进行层序遍历时,结点的访问次序为D B A E F P C。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如下表所示:
Bool、Status类型定义如下:
typedef enum { FALSE=0,TRUE=1 } Bool;
typedef enum { OVERFLOW=-2,UNDERFLOW=-1,ERROR=0,OK=1}Status;
树的二叉链表结点定义如下:
typedef struct Node {
char data;
struct Node *firstchild,*nextbrother;
} Node,*TreeNode;
【函数】
Status LevelTraverse ( TreeNode root )
{ /*层序遍历树,树采用孩子-兄弟表示法,root是树根结点的指针*/
Queue tempQ;
TreeNode ptr,brotherptr;
if (! root)
return ERROR;
InitQueue(&tempQ);
(1);
brotherptr = root -> nextbrother;
while (brotherptr) {
EnQueue(&tempQ,brotherptr);
(2);
}/*end-while*/
while((3)){
(4);
printf("%c\t",ptr->data);
if((5))continue;
(6);
brotherptr = ptr->firstchild->nextbrother;
while (brotherptr) {
EnQueue(&tempQ,brotherptr);
(7);
}/*end-while*/
}/*end-while*/
return OK;
}/*LevelTraverse*/
选项
答案
(1)EnQueue(&tempQ,root) (2)brotherptr=brotherptr->nextbrother (3)!IsEmpty(tempQ),或其等价形式 (4)DeQueue(&tempQ,&ptr) (5)!ptr->firstchild,或其等价形式 (6)EnQueue(&tempQ,ptr->firstchild) (7)brotherptr=brotherptr->nextbrother
解析
本题考查树结构的存储及遍历运算。
借助队列结构对树进行层序遍历时,每个结点都进出队列一次,结点出队列时进行访问。其过程是:首先令树根结点入队,若是森林(树根之间互为兄弟),接着则令其余树的根结点入队,然后在队列非空的情况下,队头结点出队,访问该结点同时令其孩子结点入队。以此类推,直到队列为空。
队列可以保证访问结点时按照层次和自左至右的顺序。
函数中,代码“InitQueue(&tempQ);(1)”初始化队列并令根结点入队列,因此空(1)处应填入“EnQueue(&tempQ,root)”。
采用二叉树存储树结构时,其右分支表示兄弟关系,因此队头结点出队时,应沿右分支将队头结点的所有孩子依次加入队列。以下代码处理第一棵树的兄弟结点,如下:
while (brotherptr){
EnQueue(&tempQ,brotherptr);
(2);
}/*end-while*/
因此,空(2)处应填入“brotherptr=brotherptr -> nextbrother”。这样,就完成了第一层结点的处理。
显然,空(3)处应判断队列是否为空,即填入“!IsEmpty(tempQ)”。队列非空的情况下,令队头元素出队列,即空(4)处应填入“DeQueue(&tempQ,&ptr)”。这是使用队列或栈结构存储元素以实现某种运算的基本特点。
若一个结点不存在孩子,则其firstchild指针域为空,也无需令其孩子结点入队列。
因此,空(5)处应填入“!ptr->firstchild”。反之,若一个结点有孩子,则应首先令其第一个孩子结点入队列,然后通过右分支链使其他孩子结点入队列。因此,空(6)处应填入“EnQueue(&tempQ,ptr->firstchild)”,空(7)处应填入“brotherptr =brotherptr->nextbrother”。
转载请注明原文地址:https://kaotiyun.com/show/wfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
三个可靠度R均为0.8的部件串联构成一个系统,如下图所示:则该系统的可靠度为(7)。
典型的软件测试过程模型有(46)等,在这些模型中,(47)强调了测试计划等工作的先行和对系统需求和系统设计的测试,(48)对软件测试流程予以了说明。
(61)方法根据输出对输入的依赖关系设计测试用例。
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(30)设计模式能够有效达到该目的:该系统中的某子模块需要为其他模块捉供访问不同数据库系统(如 Oracle、SQL Server和DB2 UDB等)的功能,这些数
针对逻辑覆盖(53)叙述是不正确的。
在计算机体系结构中,CPU内部包括程序计数器PC、存储器数据寄存器MDR、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为:MOV R0,#100(即将数值100传送到寄存器R0中),则CPU首先要完成的操作是(1)。
以下关于软件质量特性测试的叙述,正确的是(44)。①成熟性测试是检验软件系统故障,或违反指定接口的情况下维持规定的性能水平有关的测试工作②功能性测试是检验适合性、准确性、互操作性、安全保密性、功能依从性的测试工作③易学性测试是
在ISO/IEC软件质量模型中,功能性是与一组功能及其指定的性质的存在有关的一组属性,其子特性不包括__________。
X软件公司的软件工程师张某兼职于Y科技公司,为完成Y科技公司交给的工作,做出了一项涉及计算机程序的发明。张某认为该发明是利用自己的业余时间完成的,可以以个人名义申请专利。此项专利申请权应归属()。
A、B、C、D四台主机之间哪些可以直接通信?哪些需要通过设置网关(或路由器)才能通信?请完成图2所示的网络连接示意图中需补充的地方。若要使主机A、B、C、D在这个网路上能直接互相通信,可采取什么办法?
随机试题
以下属于公理性原则的是:
某甲是国务院证券管理委员会的_工作人员,违反有关上市申请的审批规定,擅自批准不符合上市资格的公司通过申请,这个疏忽导致使许多股民遭受重大损失,甲没有从中谋取任何个人利益。甲的行为构成:()
我国招投标应当遵循的原则是()。
某企业拟开发一种新产品,有四种设计方案可供选择,见下表。根据以上资料,回答下列问题:根据等概率原则,每种状态的概率为1/3,则该企业应该选择方案()。
()可以引用和编辑文本、图像、声音、动画和视频等多种媒体素材。
观察下面这幅漫画。请你对此谈谈看法。
A、 B、 C、 D、 A原数列可化为:分母为差后等比数列,故下一项为36。分子为三级等差数列,故下一项为8+4+18=30。故空缺项应为。
以下哪部作品属于60年代的“黑色幽默”文学,用夸张、超现实的手法将欢乐与痛苦、可笑与可怖、柔情与残酷、荒唐古怪与一本正经糅合在一起?()
Britainhaslawstomakesurethatwomenhavethesameopportunitiesasmenineducation,jobsandtraining.Butit’sstillunus
KeepOurSeasCleanA)Bytheyear2050itisestimatedthattheworld’spopulationcouldhaveincreasedtoaround12billio
最新回复
(
0
)