一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后

admin2019-07-12 38

问题一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则(58)。

选项 A、s→right指向的结点一定是s所指结点的直接后继结点
B、s→left指向的结点一定是s所指结点的直接前驱结点
C、从s所指结点出发的right链可能构成环
D、s所指结点的left和right指针一定指向不同的结点

答案C

解析本题考查数据结构基础知识。具有m个结点的二叉树采用二叉链表存储结构，链表中共有m个结点，-每个结点中两个指针(当前结点的左、右孩子指针)，则共有2m个指针。除了树根之外，其余的每个结点都由一个来自父结点的指针所指向，因此该二叉链表结点中的空指针总数必定为2m-(m-1)＝m+1个，可以充分利用这些空指针域来存放结点的前驱和后继信息。对图(a)所示的二叉树进行中序线索化后如图(b)所示。假设指针s指向中序线索二叉树中的某结点，则s→right指向的结点不一定是s所指结点的直接后继结点。当s结点具有右子树时，s→right指向其右子树而不是后继结点。同理，s→left指向的结点不一定是s所指结点的直接前驱结点。在线索二叉树中，s所指结点的left和right指针可能指向相同的结点，从s所指结点出发的right链可能构成环，如图(c)所示。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]现有5项食物，每项食物的营养价值和价格如下表所示。食物营养价值及价格表　　若要求总价格不超过100的营养

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方

设计一的关系模式Invoice最高满足第几范式?为什么?设计一和设计二哪个更加合理?为什么?根据设计二中关系模式，以下SQL语句是用于“查询从未售出的商品信息”的不完整语句，请填补其中的空缺。SELECTMno,Mname,price

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“每个学生及其选修的课程名和成绩”的不完整语句，请在空缺处填入正确的内容。SELEC(1)FROM(2)WHERE(3)

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)

求供应红色零件北京供应商的编号、名称和状态。求零件颜色不是白色和黑色的供应商状态为1的订单的数量。

宜在空腹情况下进行B超检查的是

需作治疗药物监测的药物是

根据《总会计师条列》的规定，总会计师是()。

心理学是研究人的()及其规律的科学。

2013年9月，为充分表明从严治警的决心和态度，公安部发布“三项纪律”。下列行为，没有违反“三项纪律”相关规定的是()。

公安工作的集中性即统一性，要求在服从国家意志、()等方面高度集中。

认知心理学认为记忆的基本过程有_______、_、_______。

Thefreezingpointisthetemperature_____waterchangesintoice.

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

软考中级

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]现有5项食物，每项食物的营养价值和价格如下表所示。食物营养价值及价格表 若要求总价格不超过100的营养

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(B*C+D)*E)/(F+G))的后缀表示为ABC*D+E*-FG+/为了方

设计一的关系模式Invoice最高满足第几范式?为什么?设计一和设计二哪个更加合理?为什么?根据设计二中关系模式，以下SQL语句是用于“查询从未售出的商品信息”的不完整语句，请填补其中的空缺。SELECTMno,Mname,price

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“每个学生及其选修的课程名和成绩”的不完整语句，请在空缺处填入正确的内容。SELEC(1)FROM(2)WHERE(3)

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)

求供应红色零件北京供应商的编号、名称和状态。求零件颜色不是白色和黑色的供应商状态为1的订单的数量。

宜在空腹情况下进行B超检查的是

需作治疗药物监测的药物是

根据《总会计师条列》的规定，总会计师是()。

心理学是研究人的()及其规律的科学。

2013年9月，为充分表明从严治警的决心和态度，公安部发布“三项纪律”。下列行为，没有违反“三项纪律”相关规定的是()。

公安工作的集中性即统一性，要求在服从国家意志、()等方面高度集中。

认知心理学认为记忆的基本过程有_____________、_____________、_____________。

Thefreezingpointisthetemperature_____waterchangesintoice.

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]现有5项食物，每项食物的营养价值和价格如下表所示。食物营养价值及价格表　　若要求总价格不超过100的营养

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方

认知心理学认为记忆的基本过程有_______、_、_______。