数据结构非线性部分1(树与二叉树)自测题及解答

一、概念题（每空1分，共55分）

1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2．由３个结点所构成的二叉树有种形态。

3．一棵深度为6的满二叉树有个分支结点和个叶子。

4．一棵具有２５７个结点的完全二叉树，它的深度为。

5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。

8．设一棵完全二叉树有700个结点，则共有个叶子结点。

9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。

11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。

12.中序遍历的递归算法平均空间复杂度为。

13.二叉树通常有______存储结构和______存储结构两类存储结构。

14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：

（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。

15.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。

17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左

右孩子，其余的________个指针域为NULL。

18.二叉树有不同的链式存储结构，其中最常用的是________与________。

19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。

20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。

21.树的结点数目至少为________，二叉树的结点数目至少为________。

22.下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域data，左、右孩子域lchild、rchild和左、右标志域ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。

inordethread(thr)

{p=thr->lchild;

while (p<>thr) ∥未循环结束

{ while((1) ) p= (2) ;

printf(p->data);

while((3) ) { p=(4) ；printf(p->data);}

p= (5) ;

} }

23.由________转换成二叉树时，其根结点的右子树总是空的。

24.哈夫曼（Huffman）树是带权路径长度________的树，通常权值较大的结点离根________。

25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。

二、选择题（每空1分，共10分）

（）1．不含任何结点的空树。

（Ａ）是一棵树; （Ｂ）是一棵二叉树;

（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树

（）2．二叉树是非线性数据结构，所以。

（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;

（Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构

都不能使用

（）3. 具有n(n>0)个结点的完全二叉树的深度为。

(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n)+1?

（）4．把一棵树转换为二叉树后，这棵二叉树的形态是。

（Ａ）唯一的（Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子

5. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m≥0）个 B

的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为T i的父结点，T i称为T的子结点

（1≤i≤m）。一个结点的子结点个数为该结点的 C 。

供选择的答案

A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上

B: ①互不相交②允许相交③允许叶结点相交④允许树枝结点相交

C：①权②维数③次数④序

答案：A= B= C=

6. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都

能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树

里对应结点的 C 。

供选择的答案

A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树

形结构

B: ①左子结点②右子结点③左子结点或者没有右子结点④兄弟

C：①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄

弟

⑤最左的兄弟⑥最右的兄弟

答案：A= B= C=

三、综合题（1-7每题3分，8-10每题4分,共33分）

1．给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，

试画出二叉树B 。

2. 给定如图所示二叉树T ，请画出与其对应的中序线索二叉树。

3．将算术表达式（（a+b ）+c*(d+e)+f ）*(g+h)转化为二叉树。

4. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

5. 编写递归算法，计算二叉树中叶子结点的数目。

6. 写出求二叉树深度的算法。

7. 编写递归算法，求二叉树中以元素值为x 的结点为根的子树的深度。

8．设度为m 的树采用多重链表存储。每个结点有m+1个域，其中有一个数据域，m 个指向孩

子的指针。则空指针的数目是多少？说明这种存储方式的利弊。

9. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，

0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形

式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

10. 试编写最大堆的向上调整算法函数。要求：写成内联函数的形式，程序头已给出，已通过

数组heap 建堆，建堆区间由遍历器first 、mid 和last 指向，即[mid, last-1）是一个堆，现自底

向上将[mid,last)调整为一个堆。

template

inline void _fixup(Raniter first, Raniter mid, Raniter last, T t)

参考答案

一、概念题（每空1分，共55分）

1、分支层次、根、直接前趋

2、5

3、31 32

4、9

5、2i-1 2 k-1

6、n2+1

7、最大值、完全

8、350 （[n/2]＝350）

9、500 499 1 0

10、n 2

11、L R N F E G H D C B

12、O(n)

13、顺序、链式

14、根、??2/i、左孩子、右孩子、2i、右孩子、2i+1

15、根

16、指向该结点的一个孩子、空指针NULL

17、2n、n-1、n+1

18、二叉链表、三叉链表

19、第一

20、左子树、右子树、左子树、右子树

21、1、0

22、（1）p->ltag=0 (2)p->lchild

(3)p->rtag=1 && p->rchild!=thr (4) p=p->rchild (5)p=p->rchild

22、树

23、最短、较近

24、33

二、选择题（每空1分，共10分）

1. C

2. C

3. C

4. A

5. A=①B=①C=③

6. A=②B=①C=①

三、综合题（1-9每题3分，10-11每题4分,共35分）

1．

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

D

A

C F

E G

B H I

2. 解：要遵循中序遍历的轨迹来画出每个前驱和后继。

中序遍历序列：55 40 25 60 28 08 33 54

33

3．该算术表达式转化的二叉树如图所示。

4．答：DLR ：A B D F J G K C E H I L M

LDR: B F J D G K A C H E L I M

LRD ：J F K G D B H L M I E C A

5

思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

法一：核心部分为：

DLR(BinaryTreeNode *root) /*中序遍历 递归函数*/

{if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; cout<data<lchild);

DLR(root->rchild); }

return(0);

}

法二：

int LeafCount_BiTree(BinaryTree T)//求二叉树中叶子结点的数目

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加

上右子树的叶子数

}//LeafCount_BiTree

6.解答略（参考教材）

7.int Get_Sub_Depth(BinaryTree T,int x)//求二叉树中以值为x的结点为根的子树深度

{

if(T->data==x)

{

cout<

exit 1;

}

}

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找

}

}//Get_Sub_Depth

int Get_Depth(BinaryTree T)//求子树深度的递归算法

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}//Get_Depth

8. n(n>0)个结点的m叉树共有n*m个链域，除根结点外，

每个结点均有一个指针所指，故该树的空链域有n*m-(n-1)=n(m-1)+1个。这种存储结构统一，便于处理，但空链域造成存储效率低。

9.解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：

构造哈夫曼树如下：

（100）Array

（40）（60）

（28）

（）（11）

7 10 6 （）

2 3

方案比较：

方案1的WPL ＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL ＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

结论：哈夫曼编码优于等长二进制编码

10. 解答略（参考教材P319）

■