首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树,现对该二叉链表所有结点进行如下操作:若结点p的左孩子指针为空,则将该左指针改为指向p在中序(先序、后
一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树,现对该二叉链表所有结点进行如下操作:若结点p的左孩子指针为空,则将该左指针改为指向p在中序(先序、后
admin
2019-07-12
44
问题
一个具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和c++码,将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值,请填空使之完成此功能。floatsum(floatx){floats=0.0;ints
若这三个事务允许并行执行,则请列举出有多少可能的正确结果。各个事务的内部结构如下所示。若事务不施加任何锁,则有多少可能的调度。T1:R1(GetAintot1;t1:=t1+1);U1(UpdateAfromt1);
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
【说明】一个图书馆信息管理系统的分析与建模。下面是某图书馆的有关介绍。图书馆雇有若干管理员,各自具有编码、姓名等属性。管理员可上岗,也可下岗。图书馆中备有若干图书,每本图书有书号、书名、出版社、价格等属性。图书馆不定期地购买并注册新
根据E-R图中给出的词汇,按照“有关模式名(属性1,属性2,…)”的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。假设这个银行有若干个节点,每个节点运行一个数
阅读下列函数说明和C代码,回答下面问题。[说明]冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序
阅读下列程序说明,将在空缺处填入正确的内容。【程序说明】定义一个多边形结构:structpolygon实现以下内容:(1)建立该结构的链表:create函数是创建链表,每输入一个结点的数据,就把该结点加入到链表当中,它返回创建的链表的头指
试分析该关系模式中的函数依赖,并指出关系模式的候地选码。如下的SQL语句是检索“每个学生及其选修的课程名和成绩”的不完整语句,请在空缺处填入正确的内容。SELEC(1)FROM(2)WHERE(3)
随机试题
在异步通信中,标志一个字符数据开始传输的位称为_________位。
A、绞窄性腹痛,X线平片可见肠内液平面B、腹痛,腹部有压痛,反跳痛肌紧张C、腹胀,有移动性浊音D、上腹部疼痛,左侧卧位疼痛减轻,右侧卧位疼痛加剧E、剑突下钻顶样疼痛肠梗阻时
划分法律部门的主要标准是:()。
TQC即全面质量管理,主要特点有()。
心理噪音是指()。
国际收支综合项目差额是指()。
有以下程序:#include<iostream>usingnamespacestd;classBase{public:Base(){x=0;}intx;
What’stheweatherlikewhereyouare?Chancesarethere’sacloudsomewhereonyourhorizon—acollectionofmillionsofmicrosc
WhatisthecurrenttopicofcommoninterestamongtheveryrichinAmerica?WhatmayhappeniftheUnitedStatedplacesobstac
Hiscontinualseverefinancialproblemskepthismotherina______stateofanxiety.
最新回复
(
0
)