数据库系统l试题库及答案 第6章 树和二叉树.docx

第6章树和二叉树
：树和二叉树的基本概念
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
1.
2.
3.
4.
填空题


( )线索二叉树是一种( )结构

在n个结点的线索二叉树中，线索的数目为( )。
-1 B. n +1
三、判断题
( )在先序、中序和后序序列中，叶子结点出现的相对次序是相同的。
( )由一棵二叉树的先序序列和中序序列可以唯一确定这棵二叉树。
( )在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序
遍历，则具有相同的遍历结果。
( )对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。
( )在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向孩子结点，也可能作
为线索，使之指向某一种遍历次序的前驱或后继结点。
( )若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是
该子树中序遍历结果序列的最后一个结点。
( )由一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。
四、简答题
试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：(lchild,data,rchild)。
其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；
假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。
E
C时结点奏型定:夕1加 F = stnie± node
struct node *1 eh i 1 d?
rchild.;};
c算法如-F：
rooi；—;
■traverHa-l (roo"t—>rchi ldJ ; }
若已知一棵二叉树的后序序列是FEGHDCB，中序序列是FEBGCHD，试画出这棵二叉树。
给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
0
阅读下列算法，若有错，改正之。
BiTree InSucc(BiTree q)(
〃已知q是指向中序线索二叉树上某个结点的指针，
//本函数返回指向*q的后继的指针。
r=q->rchild;
if(!r->rtag)
while(!r->rtag)r=r->rchild;
}
五、算法设计题
假定二叉树采用二叉链表存储结构存储，编写递归算法，计算二叉树中叶子结点的数目。
，
假定二叉树采用二叉链表存储结构存储，编写递归算法，求二叉树中以元素值为x的结点为根的子树的 深度。
编写按层次顺序(同一层自左至右)遍历二叉树的算法。
假定二叉树采用二叉链表存储结构存储，
设计一个算法计算一棵给定二叉树的结点总数。
编写算法判别给定二叉树是否为完全二叉树。
：树和森林
一、填空题
树的孩子-兄弟表示法又称为二叉链表表示法，即以 作树的存储结构。
森林是m (mNO)棵 的树的集合。对树的每个结点而言，其子树的集合即为 。
遍历树的方法：一种是先根(次序)遍历树，即先访问树白，然后依 遍历根的每棵 子树；另一种是后根(次序)遍历，即先依 遍历每棵子树，然后访问根结点。
当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可借用二叉树的 和
来实现。
森林的先序遍历与其转换成的二叉树的 相同，森林的中序遍历与其转换成的二叉树的
相同。
设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4,当把森林F转换成一
棵二叉树后，其根结点的左子树中有 个结点，根结点的右子树上有 个结点。
若用孩子兄弟链存储结构来存储具有m个叶子结点、n个分支结点的树，则孩子兄弟链中有
个左指针域为空的结点，有 个右指针域为空的结点。
二、选择题
( )把一棵树转换为二叉树后，这棵二叉树的形态是()。
，，但根结点都没有左孩子
( )下图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林口有( )个叶子结点。

B.
C.