数据结构习题11级用(10)

第六章 树和二叉树

一、选择题

1．树最适合用来表示（ ）。

A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2．深度为5的二叉树至多有（ ）个结点。

A． 16 B． 32 C． 31 D． 10

3．有32个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5

4．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结

点。

A．25 B．15 C．16 D．41

5．在有n个结点的二叉链表中值为非空的链域的个数为（ ）。

A． n-1 B 2n-1 C n+1 D 2n+1

6．有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5

7．对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列

均相同。

A． 3 B． 1 C． 2 D． 不存在

8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。 A． 空或只有一个结点 B． 高度等于其结点数 C． 任一结点无左孩子 D． 任一结点无右孩子

9．前序遍历与中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。

A．一般二叉树 B．只有根结点的二叉树

C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树

10．设n, m为一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（ ）。

A． n在m右方 B． n在m左方 C． n是m祖先 D． n是m子孙

11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。

A． 不发生改变 B． 发生改变

28

C． 不能确定 D． 以上都不对 12．线索二叉树是一种（ ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D． 线性

13. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先

序遍历、中序遍历和后序遍历。如把由树转化得到的二叉树叫做这棵树对应的二叉树，则结论（ ）是正确的。

A． 树的先根遍历序列与对应的二叉树的先序遍历序列相同 B． 树的后根遍历序列与对应的二叉树的后序遍历序列相同 C． 树的先根遍历序列与对应的二叉树的中序遍历序列相同 D． 以上都不对

14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数

至少为（ ）。

A． 2h B． 2h-1 C． 2h+1 D． h+1

15. 设bt是某树的二叉树表示的根结点指针，则bt满足（ ）。

A． bt->lchild==bt->rchild B． bt->rchild==NULL C． bt->lchild==NULL D． bt==NULL

16．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。

A．2n+2 B． 2n+1 C． 2n D． 2n-1

17．设哈夫曼树的叶子结点数为n，则它的结点总数为（ ）。

A． 2n-1 B． 2n C． 2n+1 D． 不确定

18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。

A． 50 B． 60 C. 52 D. 65

19．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根

的右子树的根是（ ）。

A． E B． F C. G D. H 20．下列有关二叉树的叙述中正确的是（ ）。

A． 二叉树的度为2

B． 任何一棵二叉树中至少有一个结点的度为2 C. 度为0的树是一棵二叉树 D. 二叉树中任何一个结点的度为2 21．二叉树上叶结点数等于（ ）。

A． 分支结点数加１ B． 单分支结点数加１ C. 双分支结点数加１ D. 双分支结点数减１ 22．判断线索二叉树中p所指结点由左孩子的条件是（ ）。

29

A． p!=UNLL B． p->lchild!=NULL C. p->ltag==0 D. p->ltag==1

二、填空题

1. 具有n个结点的完全二叉树的深度为 。 2. 二叉树第i层上最多有 个结点。 3. 深度为k的二叉树最多有 个结点。

4．具有n个结点的二叉树的最小深度为 ，最大深度为 ；具有具有n个结点的度为2的树的最小深度为 ，最大深度为 。 5．具有m个叶结点的huffman树共有 个结点。

6．完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。

7．在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 8．三个结点a,b,C．组成二叉树，共有 种不同的结构。

9. 一颗树T中，包括1个度为1的结点，2个度为2的结点，3个度为3的结点，则T的叶子结点数为 。

10．已知某完全二叉树采用顺序存储结构，结点的存放顺序为（A,B,C,D,E,F,G,H,I,J），该完全二叉树的后根遍历序列为 。 11．前序遍历序列是abc且后序遍历序列为cba的二叉树共有 棵。

12. F是由T1, T2, T3三棵树组成的森林，T1, T2, T3 的结点数分别为n1,n2,n3,则F对应的二叉树B(F)的根的左子树中结点数为 ，根的右子树中的结点数为 。

三、基础知识题

1．已知一棵树遍的集合为{,,,,, , ,

,,,,,}, 请画出这棵树，并回答下列问题： (1) 哪个是根结点？ (2) 哪些是叶子结点？ (3) 哪个是结点g的双亲？ (4) 哪些是结点g的祖先？ (5) 哪些是结点g的孩子？ (6) 哪些是结点e的子孙？

(7) 哪些是结点e的兄弟？哪些是结点f的兄弟？ (8) 结点b和n的层次号分别是什么？

30

(9) 树的深度是多少？

(10) 以结点c为根的子树的深度是多少？ (11) 树的度数是多少？

2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k

的结点，问该树中有多少个叶子结点？

4．对题2所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 5．现有按先序遍历二叉树的结点序列为abc，试写出能得到这一遍历结果的各种二

叉树。

6．一棵非空的二叉树其先序序列和后序序列正好相反，说明这棵二叉树的形状。 7．分别画出和下列树对应的二叉树。

A B

8．画出和下列二叉树相应的森林。

A B

9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权

路径长度。

10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出

31

该树并给出其后序序列。

12. 已知某二叉树 …… 此处隐藏：2384字，全部文档内容请下载后查看。喜欢就下载吧 ……