首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(
admin
2015-06-03
93
问题
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。
。
函数LevelTraverse()的功能是对给定树进行层序遍历。例如,当对图15-1(a)中的树进行层序遍历时,结点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如表15-1所示。
。
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 *firstchiid,*nextbrother;
}Node,*TreeNode;
【函数代码】
Status LevelTraverse(TreeNode root)
{/*层序遍历树,树采用孩子一兄弟表示法,root是树根结点的指针*/
Queue temQ;
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。
解析
解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的:首先将树根结点入队,然后将其所有兄弟结点入队(当然,由于是根结点,故无兄弟结点);完成这一操作以后,便开始出队、打印;在打印完了之后,需要进行一个判断,判断当前结点有无孩子结点,若有孩子结点,则将孩子结点入队,同时将孩子结点的所有兄弟结点入队;完了以后继续进行出队操作;出队后再次判断当前结点是否有孩子结点,并重复上述过程,直至所有结点输出。
这一描述可能过于理论,难以理解,接下来以本题为例来说明此过程。首先将树根结点D入队,并同时检查是否有兄弟结点,对于兄弟结点应一并入队。这里的D没有兄弟结点,所以队列此时应是:
D
接下来执行出队操作。D出队,出队以后检查D是否有子结点,经检查,D有子结点B,所以将B入队,同时将B的兄弟结点:A和E按顺序入队。得到队列:
B
A
E
接下来再执行出队操作。B出队,同时检查B是否有子结点,B无子结点,所以继续执行出队操作。A出队,同时检查A是否有子结点,A有子结点F,所以将F入队,同时将F的兄弟结点P入队。得到队列:
E
F
P
接下来再次执行出队操作。E出队,E有子结点C,所以C入队。得:
F
P
C
接下来再次执行出队操作。F出队,F无子结点,继续出队操作,P出队,仍无子结点,最后C出队,整个过程结束。
通过对算法的详细分析,现在便可轻松得到答案。(1)应是对根结点root执行入队操作,即EnQueue(&tempQ,root)。(2)在一个循环当中,循环变量是brotherptr,此变量无语句对其进行更新,所以(2)必定是更新brotherptr。结合前面的算法分析可知(2)应填:brotherptr=brotherptr->nextbrother。(3)、(4)加上后面的语句“printf(“%c\t”, ptr->data);”是控制数据的输出,这些数据应是从队列中得到,所以此处必有出队操作,同时在出队之前应判断队列是否为空,所以(3)、(4)填:!IsEmpty(tempQ)和DeQueue(&tempQ,&ptr)。(5)实际上是问“在什么情况下,要持续进行出队操作?”,前面的算法分析中已指出:若出队结点无子结点,则继续进行出队操作,所以(5)填!ptr->firstchild。(6)和(7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队,所以(6)填:EnQueue(&tempQ,ptr->firstchild)。(7)和(2)相同,填brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://kaotiyun.com/show/FdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
假定提供Web服务的两台Linux服务器IP地址分别为192.168.1.10和192.168.1.20。为了使用DNS循环机制,由主机名www.test.com对外提供一致的服务,需要在DNS服务器的test.com区域文件中增加下列内容:www
阅读以下关于在Linux系统中配置Apache服务器的说明,回答问题1至问题3,将解答填入解答栏内。【说明】在Linux系统中采用Apache配置Web服务器。Apache服务器提供了丰富的功能,包括:目录索引、目录别名、虚拟主机、HTTP日志报
阅读以下说明,回答问题1和问题2,将解答填入对应的解答栏内。【说明】某单位内部网络拓扑结构如下图所示,在该网络中采用RIP路由协议。
IPSec工作在TCP/IP协议栈的(1),为TCP/IP通信提供访问控制、(2)、数据源验证、抗重放、(3)等多种安全服务。IPSec的两种工作模式分别是(4)和(5)。(1)~(5)备选答案:A.应用层B.网络层C.数据链
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。【说明】某公司内部服务器S1部署了重要的应用,该应用只允许特权终端PC1访问,如下图所示。为保证通信安全,需要在S1上配置相应的IPSec策略。综合考虑后,确定该IPSec策略如下。
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。DNS系统中反向查询
请在(1)~(4)空白处填写恰当的内容。DHCP的工作过程是:1)IP租用请求。DHCP客户机启动后,发出一个DHCPDISCOVER消息,其封包的源地址为(1),目标地址为(2)。2)IP租用提供。当DHCP服务器收到DHCPDI
阅读以下关于网络地址转换(NAT)的技术说明,结合网络拓扑图回答问题1至问题3。【说明】网络地址转换(NAT)技术可用来缓解IP地址短缺问题和实现TCP负载均衡功能。动态地址翻译技术在子网外部使用少量的全局地址,通过路由器进行内部和外部地址的转换
阅读以下电子商务公司应用无线局域网的技术说明,根据要求回答问题1至问题5。【说明】由于市场的不断扩大,A电子商务公司客户数量日益增多。现有的网络已不能满足信息发展的需求,考虑到既要同时满足网络扩容顺利进行及公司日常工作的正常开展,又要保证目前土建
随机试题
Humanityusesalittlelessthanhalfthewateravailableworldwide.Yetoccurrencesofshortagesanddroughtsarecausingfami
在进程调度算法中,_______调度算法比较适合于分时操作系统。
下列疾病可出现周围性发绀的是
肠道中正常菌群,对维持微生物平衡作用很大的厌氧菌为
A.茯苓B.附子C.白术D.甘草E.人参四逆散与四逆汤的组成中均含有的药物是()
左心衰竭首先引起的病变是
药品批发和零售连锁企业对特殊管理的药品应实行
三相异步电动机产生最大电磁转矩时对应的转差率称为()。
SoC芯片中的CPU绝大多数是以IP核的方式集成在芯片中的,很少再自行设计开发。目前32位嵌入式处理器主要采用的是由【41】国一家专门从事RISC处理器内核设计公司设计的【42】内核。
Gettingagoodnight’ssleephaslongbeenknowntoconsolidatetheday’smemories,movingthemfromshort-termstorageintolon
最新回复
(
0
)