第六章树和二叉树试题
一、单项选择题
1树中所有结点的度等于所有结点数加（
A0
B1
）。C1
D2
2在一棵树中，（
）没有前驱结点。
A分支结点B叶结点
C根结点
D空结点
3在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（
A2
B1
C0
）。D1
4在一棵具有
个结点的二叉树中，所有结点的空子树个数等于（
A

B
1
C
1
）。D2

5在一棵具有
个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），
最多具有（
）个结点。
A2i
B2i1
C2i1
D2

6在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（
）。
A2h1
B2h1
C2h1
D2h
7在一棵具有35个结点的完全二叉树中，该树的高度为（
A5
B6
C7
）。假定空树的高度为1。D8
8在一棵具有
个结点的完全二叉树中，分支结点的最大编号为（
A
12
B
2
C
2
）。假定树根结点的编号为0。D
21
9在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（
点的编号为0
A2i
B2i1
C2i1
D2i2
）。假定根结
10在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号
为（
）。
Ai12
Bi12
Ci2
Di21
11在一棵树的左子女右兄弟表示法中，一个结点的右孩子是该结点的（
）结点。
A兄弟
B子女
C祖先
D子孙
12在一棵树的静态双亲表示中，每个存储结点包含（
）个域。
A1
B2
C3
D4
13已知一棵二叉树的广义表表示为abcdeghf，则该二叉树的高度为
（
）。假定根结点的高度为0。
1
fA3
B4
C5
D6
14已知一棵树的边集表示为ABACBDCECFCGFH
FI，则该树的高度为（
）。假定根结点的高度为0。
A2
B3
C4
D5
15利用
个值作为叶结点上的权值生成的霍夫曼树中共包含有（
）个结点。
A

B
1
C2

D2
1
16利用36812这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（
）。
A55
B29
C58
D38
17一棵树的广义表表示为abcefgd，当用左子女右兄弟链表表示时，右指针域
非空的结点个数为（
）。
A1
B2
C3
D4
18向具有
个结点的堆中插入一个新元素的时间复杂度为（
）。
AO1
BO

COlog2

DO
log2

参考答案：1C6D11A16A
2C7A12B17C
3A8D13B18C
4C9C14B
5A10B15D
二、填空题
1对于一棵具有
个结点的树，该树中所有结点的r