数据结构-作业6

参考教材：数据结构教程（Java语言描述)        作者：李春葆

1 . 容易 （3分）现有一"遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。表示该遗传关系最适合的数据结构为______。

A. 数组

B. 树

C. 图

D. 线性表

2 . 容易 （3分）一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是______。

A. nh

B. n+h

C. n-1

D. h-1

3 . 容易 （3分）若一棵3次树中有2个度为3的结点，1个度为2的结点，2个度为1的结点，该树一共有______ 个结点。

A. 5

B. 8

C. 10

D. 11

4 . 容易 （3分）一棵度为5、结点个数为n的树采用孩子链存储结构时，其中空指针的个数是______。

A. 5n

B. 4n+1

C. 4n

D. 4n-1

5 . 容易 （3分）以下关于二叉树的说法中正确的是______。

A. 二叉树中每个结点的度均为2

B. 二叉树中至少有一个结点的度为2

C. 二叉树中每个结点的度可以小于2

D. 二叉树中至少有一个结点

6 . 容易 （3分）若一棵有n个结点的二叉树，其中所有分支结点的度均为k，该树中的叶子结点个数是______。

A. n(k-1)/k

B. n-k

C. (n+1)/k

D. (nk-n+1)/k

7 . 容易 （3分）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为______。

A. 9

B. 11

C. 15

D. 不确定

8 . 容易 （3分）具有10个叶子结点的二叉树中有______ 个度为2的结点。

A. 8

B. 9

C. 10

D. 11

9 . 容易 （3分）一棵二叉树中有7个叶子结点和5个单分支结点，其总共有______ 个结点。

A. 16

B. 18

C. 12

D. 31

10 . 容易 （3分）一棵二叉树中有35个结点，其中所有结点的度之和是______。

A. 35

B. 16

C. 33

D. 34

11 . 容易 （3分）高度为5的二叉树至多有______ 个结点。

A. 16

B. 32

C. 31

D. 10

12 . 容易 （3分）高度为5的二叉树至少有______ 个结点。

A. 5

B. 6

C. 7

D. 31

13 . 容易 （3分）二叉树第i层上至多有______ 个结点。

A. 2i

B. 2i-1

C. 2i-1-1

D. 2i-1

14 . 容易 （4分）一个具有1025个结点的二叉树的高h为______。

A. 11

B. 10

C. 11～1025

D. 12～1024

15 . 容易 （4分）一棵完全二叉树中有501个叶子结点，则至少有______ 个结点。

A. 501

B. 502

C. 1001

D. 1002

16 . 容易 （4分）一棵完全二叉树中有501个叶子结点，则至多有______ 个结点。

A. 501

B. 502

C. 1001

D. 1002

17 . 容易 （4分）一棵高度为8的完全二叉树至少有______ 叶子结点。

A. 63

B. 64

C. 127

D. 128

18 . 容易 （4分）棵高度为8的完全二叉树至多有______ 叶子结点。

A. 63

B. 64

C. 127

D. 128

19 . 容易 （4分）一棵满二叉树中127个结点，其中叶子结点的个数是______。

A. 63

B. 64

C. 65

D. 不确定

20 . 容易 （4分）一棵满二叉树共有64个叶子结点，则其结点个数为______。

A. 64

B. 65

C. 127

D. 128

21 . 容易 （4分）设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是______。

A. 16

B. 15

C. 7

D. 17

22 . 容易 （4分）如果一棵二叉树B是由一棵树T转换而来的二叉树，那么T中结点的先根序列对应B的______ 序列。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

23 . 容易 （4分）设一棵二叉树B是由森林T转换而来的，若T中有n个非叶子结点，则二叉树B中无右孩子的结点个数为______。

A. n-1

B. n

C. n+1

D. n+2

24 . 容易 （3分）某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是______。

A. 空或只有一个结点

B. 完全二叉树

C. 二叉排序树

D. 高度等于其结点数

25 . 容易 （3分）一棵二叉树的先序序列为ABCDEFG，它的中序序列可能是______。

A. CABDEFG

B. ABCDEFG

C. DACEFBG

D. ADCFEGB

26 . 容易 （3分）一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为______。

A. CBEFDA

B. FEDCBA

C. CBEDFA

D. 不确定 

27 . 容易 （3分）由含n个结点的二叉树线索化后有______ 个线索（不计头结点）。

A. 2n

B. n+1

C. n-1

D. 2n-1

28 . 容易 （3分）若x是中序线索二叉树中一个有左孩子的结点，且不是根结点，则x的前驱结点为______。

A. x的双亲结点

B. x的右子树中最左下结点

C. x的左子树中最右下结点

D. x的左子树中最右下结点

29 . 容易 （3分）一棵哈夫曼树中共有199个结点，它用于多少个字符的编码______。

A. 99

B. 100

C. 101

D. 199

30 . 容易 （3分）根据使用频率为5个字符设计的哈夫曼编码不可能是______。

A. 000，001，010，011，1

B. 0000，0001，001，01，1

C. 000，001，01，10，11

D. 00，100，101，110，111