下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

admin2010-01-23 49

问题下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

选项 A、前序线索二叉树
B、中序线索二叉树
C、后序线索二叉树
D、前、后、中序线索二叉树

答案C

解析易知，前、中、后序遍历二叉树的递归或者非递归算法都用到栈。遍历线索二叉树实际上就是找结点的后继。前序线索二叉树中，除前序遍历最后一个元素无后继外。任一结点的后继便为左孩子(若左子树非空)或者右孩子(若左子树为空)或者是其右线索(若该结点是叶子结点)，只要顺着指针便可以方便地找到后继，显然不需要用到栈。中序线索二叉树中，除中序遍历最后一个元素无后继外，寻找任一结点的后继的过程如下：若该结点有右线索，则该右线索指示的便是后继；否则，该结点右子树最左下的结点便是后继。可以顺着该结点指向右子树的指针向下找到这个最左下的结点，不需要用栈。因此，遍历中序线索二叉树也不需要栈的支持。在后序线索二叉树中求后继要分三种情况来讨论：①若结点W是根结点，则W的后继为空；②若结点W是其双亲结点的右孩子，或者W是其双亲结点的左孩子且W的双亲没有右子树，则W的后继为其双亲结点；③若结点W是其双亲结点的左孩子且其双亲结点有右子树，则W的后继为其双亲结点右子树上按后序遍历的第一个结点。可见，在后序线索化树(以二叉链表存储)上找后继时需要知道结点双亲，这就需要栈的支持。如 13-28所示，从后序遍历第一个结点E开始，顺着E的右线索可以找到E的后继D，当要找D的后继就麻烦了，因为这个时候D的两个指针都指向E，而B只有单向指向D的指针 (不管用)，因此要找到D的后继B就需要栈的支持。

转载请注明原文地址:https://kaotiyun.com/show/xlxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

软件设计师上午基础知识考试

软考中级

Networks　can　be　interconnected　by　different　devices　in　the　physical　layer　networks　can　be　connected　by(1)or　hubs.　Which　just　mov

下列关于传输服务的面向连接服务和无连接服务说法中正确的是(27)。

下述任务中，不属于软件工程需求分析阶段的是(10)。

Atransportlayerprotocolusuallyhasseveralresponsibilties．Oneistocreateaprocess—to—processcommunicationUDPuses(71)n

与算术表达式“(a+(b—c))*d”对应的树是(7)。

阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG

To　round　is　to　delete　or(66)one　or　more　of　the　least　significant　digits　in　a　positional(67)and　to,　or　not　to,　adjust　the　part　re

患者，女性，54岁。出现乏力、双眼异物感、多饮2年，伴大小关节痛，查体见多发龋齿，舌红无苔，关节无畸形、肿大及压痛。下述哪一项化验检查对该患者的诊断最有提示意义

关于处方调配的注意事项A、登记账卡B、批准文号C、有效期D、加贴醒目标签E、签名或盖名章对贵重药品应

个体工商户王某于2005年6月在某百货商场租赁一柜台用于销售新美公司生产的“美美”牌连衣裙，并采取下列促销措施，其中属于不正当竞争行为的是：()

下列属于组织风险的有(　　)。

同一离子方程式可以表示不同物质在不同溶液中的反应。下列各组中两种物质在溶液中的反应，可以用同一离子方程式表示的是()。

以下叙述中正确的是()。

Wewalkedsoquietlythatthenurseatthedeskdidn’tevenlifthereyesfromthebook.Mumpointedtoabigchairbythedoor

Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【C1】______iny

Forthispart,youareallowed30minutestowriteanessaycommentingontheremark"Nopain,nogain."Youcanciteexamplest

A、Seeadoctorordietitian.B、Calculatethefluidamount.C、Followrecommendations.D、Controltheirfluidintake.A主讲人建议，若有人对自己

下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

软件设计师上午基础知识考试

软考中级

Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov

下列关于传输服务的面向连接服务和无连接服务说法中正确的是(27)。

下述任务中，不属于软件工程需求分析阶段的是(10)。

Atransportlayerprotocolusuallyhasseveralresponsibilties．Oneistocreateaprocess—to—processcommunicationUDPuses(71)n

与算术表达式“(a+(b—c))*d”对应的树是(7)。

阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG

To round is to delete or(66)one or more of the least significant digits in a positional(67)and to, or not to, adjust the part re

患者，女性，54岁。出现乏力、双眼异物感、多饮2年，伴大小关节痛，查体见多发龋齿，舌红无苔，关节无畸形、肿大及压痛。下述哪一项化验检查对该患者的诊断最有提示意义

关于处方调配的注意事项A、登记账卡B、批准文号C、有效期D、加贴醒目标签E、签名或盖名章对贵重药品应

个体工商户王某于2005年6月在某百货商场租赁一柜台用于销售新美公司生产的“美美”牌连衣裙，并采取下列促销措施，其中属于不正当竞争行为的是：()

下列属于组织风险的有( )。

同一离子方程式可以表示不同物质在不同溶液中的反应。下列各组中两种物质在溶液中的反应，可以用同一离子方程式表示的是()。

以下叙述中正确的是()。

Wewalkedsoquietlythatthenurseatthedeskdidn’tevenlifthereyesfromthebook.Mumpointedtoabigchairbythedoor

Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【C1】______iny

Forthispart,youareallowed30minutestowriteanessaycommentingontheremark"Nopain,nogain."Youcanciteexamplest

A、Seeadoctorordietitian.B、Calculatethefluidamount.C、Followrecommendations.D、Controltheirfluidintake.A主讲人建议，若有人对自己

Networks　can　be　interconnected　by　different　devices　in　the　physical　layer　networks　can　be　connected　by(1)or　hubs.　Which　just　mov

To　round　is　to　delete　or(66)one　or　more　of　the　least　significant　digits　in　a　positional(67)and　to,　or　not　to,　adjust　the　part　re

下列属于组织风险的有(　　)。