软件工程

若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中有（）个指针是空指针。

题目

若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中有（）个指针是空指针。

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

编写递归算法,交换二叉链表存储的二叉树中每个结点的左、右子树。


参考答案：

第2题：

二叉树如右图所示,若进行顺序存储（即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为（ ）；若釆用三叉链表存储该二叉树（各个结 点包括结点的数据、父结点指针、左孩子指针、右孩子指针），则该链表的所有结点中空指针的数目为（ ）。

A.6 B.10 C.12 D.15 A.6 B.8 C.12 D.14


正确答案：D,B

第3题：

交换二叉树每个结点的左孩子和右孩子。


参考答案：如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。
　　[算法描述]
　　void ChangeLR(BiTree &T)
　　{
　　BiTree temp;
　　if(T->lchild==NULL&&T->rchild==NULL)
　　return;
　　else
　　{
　　temp = T->lchild;
　　T->lchild = T->rchild;
　　T->rchild = temp;
　　}//交换左右孩子
　　ChangeLR(T->lchild); //递归交换左子树
　　ChangeLR(T->rchild); //递归交换右子树
　　}

第4题：

一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同），若它存在右孩子，则右孩子的编号为（）。
13
略

第5题：

某二叉树如图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为（请作答此空）；若采用三叉链表存储该二叉树（各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针），则该链表的所有结点中空指针的数目为（ ）。

A.6
B.10
C.12
D.15

答案：D
解析：
采用顺序存储结构存储二叉树时，一般的二叉树也必须按照完全二叉树的形式存储，需要填上一些不存在的"虚结点"。题中二叉树的高度为4，需要的存储空间为24-1=15，如下：

可见，空指针的数目为8。

第6题：

在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点的下标为k(起始下标为1)，那么(39)时采用顺序存储更节省空间。

A．

B．

C．

D．


正确答案：A
解析：采用三叉链表存储二叉树时，每个结点需要占用d+4*3个字节，n个结点则需要　n(d+12)。若顺序存储最后一个结点的下标为k，则共需kd个字节。显然，kdn(d+12)时采用顺序存储更节省空间，即要求(作图)。

第7题：

在一棵完全二叉树的顺序存储方式中，若编号为t的结点有右孩子，则此结点右孩子的编号为( )

A．2t

B．2t-1

C．2t+1

D．t/2


正确答案：C

第8题：

一棵完全二叉树的顺序存储中，若编号为i的结点有左孩子，则该左孩子的编号为 ______。


正确答案：2i
2i 解析：根据完全二叉树的性质，对一棵有n个结点的完全二叉树，若2i＞n则结点i无左孩子，否则其左孩子结点是2i。

第9题：

某二叉树如图所示，若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1)，则该数组的大小至少为（58）；若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针)，则该链表的所有结点中空指针的数目为（59）。

A.6
B.8
C.12
D.14

答案：B
解析：
采用顺序存储结构存储二叉树时，一般的二叉树也必须按照完全二叉树的形式存储，需要填上一些不存在的“虚结点”。题中二叉树的高度为4，需要的存储空间为24-1=15，如下：可见，空指针的数目为8。

第10题：

在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。


正确答案:2i+1

更多相关问题
相关内容