数据结构习题3.pdf

数据结构习题3--第1页

数据结构习题3

第6章树

6.1选择题

1．一棵具有n个结点的完全二叉树的树高度（深度）是（）

A）?log2n?+1B）log2n+1C）?log2n?D）log2n-1

2．有关二叉树下列说法正确的是（）

A）二叉树的度为2B）一棵二叉树的度可以小于2

C）二叉树中至少有一个结点的度为2D）二叉树中任何一个结点

的度都为2

3．二叉树的第I层上最多含有结点数为（）

A）2IB）2I-1-1C）2I-1D）2I-1

4．具有10个叶结点的二叉树中有（）个度为2的结点

A）8B）9C）10D）11

5．在下述结论中，正确的是（）

①只有一个结点的二叉树的度为0；

②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二

叉树。

A）①②③B）②③④C）②④D）①④

6．由3个结点可以构造出多少种不同的二叉树？（）

A）2B）3C）4D）5

7．引入二叉线索树的目的是（）

A）加快查找结点的前驱或后继的速度

B）为了能在二叉树中方便的进行插入与删除

C）为了能方便的找到双亲

D）使二叉树的遍历结果惟一

8．有n个叶子的哈夫曼树的结点总数为（）

A）不确定B）2nC）2n+1D）2n-1

数据结构习题3--第1页

数据结构习题3--第2页

9．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，

则该二叉树一定满足（）A）所有的结点均无左孩子B）所有的结点均

无右孩子

C）只有一个叶子结点D）是任意一棵二叉树

10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是

（）

A）250B）500C）505D）以上答案都不对

11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为

DEBAC，则它的先序遍历序列为（）A）ACBEDB）DECABC）

DEABCD）CEDBA

12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，

则度为0的结点个数是（）

A）9B）11C）15D）不确定

13．利用二叉链表存储树时，根结点的右指针是（）

A）指向最左孩子B）指向最右孩子C）空D）非空

14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分

别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结

点个数是（）

A）M1B）M1+M2C）M3D）M2+M3

15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，

则X的前驱为（）

A）X的双亲B）X的右子树中最左的结点

C）X的左子树中最右结点D）X的左子树中最右叶结点

16．n个结点的线索二叉树上含有的线索数为（）

A）2