首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
阅读以下说明、图和C代码。 【说明】 一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
admin
2008-04-04
81
问题
阅读以下说明、图和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
CDMA系统中使用的多路复用技术是(27)。我国自行研制的移动通信3G标准是(28)。
下述关于错误处理流程管理的原则,(49)的说法是不正确的。
以下控制流程图的环路复杂性V(G)等于(54)。
在执行测试和评价的过程中,会产生较多的文档,(43)是对文档内容的正确描述。①评价需求的主要内容是描述评价的目标,特别是描述了产品的质量需求。②评价规格说明的主要内容是确定对软件及其部件实行的所有分析和测量,标识要采用的操作规程、测试方法和工具。③评
内存按字节编址,地址从90000H到CFFFFH,若用存储容量为16KB×8bit的存储器芯片构成该内存,至少需要(3)片。
以下关于软件质量特性测试的叙述,正确的是(44)。①成熟性测试是检验软件系统故障,或违反指定接口的情况下维持规定的性能水平有关的测试工作②功能性测试是检验适合性、准确性、互操作性、安全保密性、功能依从性的测试工作③易学性测试是
J2EE系统架构被各种信息系统普遍采用,______不属于其服务器端应用组件。A.ServletB.JSPC.EJBD.Applet
根据ANSI/IEEE829标准,以下(37)属于《测试程序说明》中程序步骤的内容。 ①启动 ②目的 ③日志 ④设置
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
随机试题
简述国家利益、社会整体利益和个人利益的辩证统一。
背景A公司中标承建一大型电力装备制造厂的全部机电工程,总承包合同约定,A公司除完成关键设备安装外,其余公用工程和辅助工程可自行分包给各专业公司施工,A公司实行总包管理,对全面履行总承包合同负责,为此A公司成立了综合调度机构。在一次例行的全场实地
记账错误观点主要表现为漏记、重记和错记三种。错记又表现为( )。
海上运输的特点包括()。
以下与对应数据相关的说法中,错误的是()。
世界旅游组织的基本特征有()。
简述四班三运转和五班四运转的组织形式。
(2015年真题)简述我国司法机关依法独立行使职权原则的内涵。
某客户机使用DHCP获取IP地址等信息,其获取IP地址过程中捕获的4条报文及对第2条报文分析如下图所示。请分析其中的信息,补全内容。
ThecapitalofNewZealandis______.
最新回复
(
0
)