第七章习题_原创文档.pdf

第七章树

一、判断题（T表示正确，F表示错误）

1．二叉树是树的特殊形式

2．由树转换成二叉树，其根节点的右子数总是空的。

3．先根遍历一棵树和先序遍历与该树对应的二叉树，其结果相同。

4．后根遍历树和中序遍历与该树对应的二叉树，其结果不同。

5．先序遍历森林和先序遍历与该森林对应的二叉树，其结果不同。

6．后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。

7．若一个节点是某二叉树子树的中序遍历序列中的最后一个节点，则他必是该子树的先序遍历序

列中的最后一个节点

8．若一个节点是某二叉树子树的中序遍历序列中的第一个节点，则他必是该子树的先序遍历序列

中的第一个节点

9．不使用递归也可以实现二叉树的先序，中序和后序遍历。

10.先序遍历二叉树的序列中，任何节点的子树的所有节点不一定跟在该节点之后。

11．由先序序列和后续序列能唯一确定一棵二叉树。

12.由先序序列和中续序列能唯一确定一棵二叉树。

13.由中序序列和后续序列不能唯一确定一棵二叉树。

14.完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能

15.满二叉树一定是完全二叉树。

二、单选题

1．对树而言，不适合的遍历（）

A)先序B）中序C）后序D)层次

2．以二叉链表作为二叉树的存储结构在具有n个结点的二叉链表中（n0）空链域的个数为（）

A)2n-1B）n-1C）n+1D)2n+1

3．线索化二叉树中某结点*p没有孩子的充要条件是（）

A)p-lchild=NULLB）p-ltag=1且p-rtag=1

C）p-ltag=0D)p-lchild=NULL且p-ltag=1

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是（）

A)3B）4C）5D)1

5．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，…n。且

有如下的性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的节点中，其

最小编号等于v左子树上结点的最大编号加1，这是按（）编号的。

A)中序遍历序列B）先序遍历序列C）后序遍历序列D)层次顺序

6．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端节点，B中右指针域为空的节

点有（）个

A)n-1B）nC）n+1D)n+2

7．先序遍历的顺序是（）

A)根结点，左子树，右子树B）左子树，根结点，右子树

C）右子树，根结点，左子树D)左子树，右子树，根结点

8．中序遍历的顺序是（）

A)根结点，左子树，右子树B）左子树，根结点，右子树

C）右子树，根结点，左子树D)左子树，右子树，根结点

9任何一棵二叉树的叶子结点在先序，中序，后序遍历序列中的点对次序是（）

A)不发生改变B）发生改变C）不能确定D)以上都不对

10．后序遍历的顺序是（）

A)根结点，左子树，右子树B）左子树，根结点，右子树

C）右子树，根结点，左子树D)左子树，右子树，根结点

11．后序遍历序列为dabec,中序遍历序列为debac,则先序遍历序列为（）

A)cbedB）decabC）deabcD)cedba

12．先序遍历序列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍历的结果为（）

A)gcefhabdB）gdbecfhaC）bdgaechfD)gdbehfca

13．先序遍历序列为stuwv,中序遍历序列为uwtvs,则后序遍历序列为（）

A)uwvtsB）vwutsC）wuvtsD)wutsv

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