程序二叉树及树

一. 选择题

1. 树最适合用来表示（ ）。 A.有序数据元素 B.无序数据元素

2. 二叉树的第k层的结点数最多为（ ）. A.2k-1 B.2K+1

共有（ ）个空指针域。 (A) 2m-1 (B) 2m

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

C.2K-1

D.2k-1

3. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总

(C) 2m+1

(D) 4m

4. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA

5. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 (A) 9 (B) 10 (C) 11

6. 设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1

(D) 12

(D) 2k-1

7. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l

8. 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）。 (A) Nl+N2+……+Nm (C) N2+2N3+3N4+……+(m-1)Nm (B) l+N2+2N3+3N4+……+(m-1)Nm

(D) 2Nl+3N2+……+(m+1)Nm

9. 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。 (A) 20 (B) 30 (C) 40 (D) 45

10. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 (A) 空或只有一个结点 (C) 任一结点无左孩子 (B) 高度等于其结点数 (D) 任一结点无右孩子

11. 设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。 (A) 3 (B) 4 (C) 5

12. 深度为k的完全二叉树中最少有（ ）个结点。 (A) 2k-1-1 (B) 2k-1 (C) 2k-1+1

(D) 6

(D) 2k-1

13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102

14. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1

15. 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 (A) 20 (B) 256 (C) 512 (D) 1024

16. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 (A) 8 (B) 7 (C) 6 (D) 5

17. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。 (A) 5 (B) 6 (C) 7 (D) 8

18. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3

19. 设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。 (A) 4 (B) 5 (C) 6 (D) 7

20. 设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（ ）个叶子结点。 (A) (i1)Ni

i1m(B) Ni

i1m(C) Ni

i2m(D) 1(i1)Ni

i2m

21. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。 (A) 129 (B) 219 (C) 189 (D) 229

22. 设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l

二. 填空题

1. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

2. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

3. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

4. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

5. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。

6. 深度为k的完全二叉树中最少有____________个结点。

7. 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。

8. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。

9. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

10. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

11. 设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。

12. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。

13. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。

14. 高度为h的完全二叉树中最少有________个结点，最多有________个结点。

15. 设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。

16. 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。

17. 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

18. 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。

19. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。

20. 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。

21. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。

22. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node {int data;

struct node *lchild; ________________; }bitree;

void createbitree(bitree *&bt) {

scanf(“%c”,&ch); if(ch=='#')

___________; else

{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;

createbitree(bt->rchild);} }

三. 判断题

1. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）

2. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ） 3. 设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ） 4. 完全二叉树中的叶子结点只可能在最后两层中出现。（ ） 5. 哈夫曼树中没有度数为1的结点。（ ）

6. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ） 7. 由树转化成二叉树，该二叉树的右子树不一定为空。（ ） 8. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )

四. 应用题

1. void ABC(BTNode * BT) {

if BT {

ABC (BT->left); ABC (BT->right); cout<data<<' ';} }

该算法的功能是：

2. 二叉搜索树的查找——递归算法:

bool Find(BTreeNode* BST,ElemType& item) {

if (BST==NULL) return false; //查找失败 else {

if (item==BST->data){

item=BST->data;//查找成功 return___________;} else if(itemdata)

return Find(______________,item);

else return Find(_______________,item); }//if }

3. 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

4. 已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

5. 右图所示的森林：

⑴求树（a）的先根序列和后根序列；

⑵求森林先序序列和中序序列；

⑶将此森林转换为相应的二叉树；

6. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。

五. 算法设计

1. 设计一个求结点x在二叉树中的双亲结点算法。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

3. 在链式存储结构上建立一棵二叉排序树。

4. 设计判断两个二叉树是否相同的算法。

5. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

6. 设计计算二叉树中所有结点值之和的算法。