首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
admin
2008-04-04
50
问题
阅读以下说明、图和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
人眼看到的任一彩色光都是亮度、色调和饱和度3个特性的综合效果,其中(13)反映颜色的种类。
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
软件开发人员可以用(18)软件编写和修改程序。
如果在程序中的多个地方需要使用同一个常数,那么最好将其定义为一个符号常量,这样______。
在数据库逻辑设计阶段,若实体中存在多值属性,那么将E-R图转换为关系模式时,___________,得到的关系模式属于4NF。
在结构化分析中,用数据流图描述(42)。当采用数据流图对银行客户关系管理进行分析时,(43)是一个加工。(42)
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
银行系统数据流图中,某个加工根据客户的多个不同属性的值来执行不同的操作,则对该加工最适宜采用()描述。
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
随机试题
Anotherreasonacompanymightnothaveahumanresourcesdepartmentisthattheychoosetooutsourceittoacompanythatprovi
1956年,在中共八大上提出“三个主体,三个补充”思想的是()
A.新月体肾小球肾炎B.毛细血管内增生性肾炎C.系膜增生性肾小球肾炎D.微小病变型肾病E.局灶性节段性肾小球肾炎哪种是隐匿性肾小球肾炎的病理类型
A.开窍醒神、活血散结B.开窍醒神、化湿和胃C.开窍醒神、清热止痛D.开窍醒神、清心化痰E.开窍辟秽、温通止痛
面瘫的贝尔征是指
下列关于栓剂的错误表述是
关于《雅典宪章》,哪种说法是不适宜的?
以下出口商品,检验检疫机构不受理免验申请的是()
投资者在申购或赎回ETF份额时,申购赎回代理券商可按照( )的标准收取佣金。
Itmaycomeasasurprisetomanyanexhaustedmotherorfather—butthinkingaboutyourchildrencouldimproveyourmemory,ast
最新回复
(
0
)