吉林省专升本考试数据结构分章习题及参考答案———选择题
（第五章）
1、一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
A、250
B、500
C、254
D、501
2、将一棵树t转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h的
A、前序遍历
B、中序遍历
C、后序遍历
D、层序遍历
3、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。
A、中序遍历
B、先序遍历
C、后序遍历
D、按层次遍历
4、二叉树的第5层上最多含有结点数为（）
A、31
B、16
C、15
D、32
5、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：
A、E,G,F,A,C,D,B
B、E,A,C,B,D,G,F
C、E,A,G,C,F,B,D
D、上面的都不对
6、若森林F有15条边、25个结点，则F包含树的个数是( )。
A、8
B、9
C、10
D、11
7、有权值分别为2,3,5,8,7,4的叶子结点生成一棵哈夫曼树，其带权路径长度为（）
A、36
B、72
C、96
D、120
8、任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序(）
A、肯定不发生改变
B、肯定发生改变
C、不能确定
D、有时发生变化
9、为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是( ).
A、 111,110,10,01,00
B、000,001,010,011,1
C、100,11,10,1,0
D、001,000,01,11,10
10、给定二叉树1(2(4,5(6,7)),3)。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4则其遍历方式是( )
A、LRN
B、NRL
C、RLN
D、RNL
11、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（）。
A、67
B、68
C、69
D、70
12、深度为k的完全二又树至少有( )个结点。
A、2k-2+1
B、2k-1
C、2k-1
D、2k-1-1
13、一个具有1025个结点的二叉树的高h为（）
A、11
B、10
C、11至1025之间
D、10至1024之间
14、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有( )个。
A、n-l
B、n
C、n+1
D、n+2
15、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A、空或只有一个结点
B、任一结点无左子树
C、高度等于其结点数
D、任一结点无右子树
16、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。
A、acbed
B、decab
C、deabc
D、cedba
17、 前序遍历序列与后序遍历序列相同的二叉树为()。
A、 非叶子结点只有左子树的二叉树
B、 根结点无右子树的二叉树
C、 只有根结点的二叉树
D、 非叶子结点只有右子树的二叉树
18、 按照二叉树的定义，具有3个结点的二叉树有()种。
A、 3
B、 4
C、 5
D、 6
19、设森林中有4棵树，树中结点的个数依次为n1、n2、n3和n4，则把森林转换成一棵二叉树后，其根结点的左子树上有( )个结点。
A、n1-1
B、n1
C、n1+n2+n3
D、n2+n3+n4
20、 二叉树中结点的儿子的顺序是()
A、 确定的
B、 可变的
C、 任意的
D、 未知
21、在一 棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10 个度为1的结点，则树T的叶子结点个数是( )
A、4
B、82
C、113
D、122
22、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：
A、E
B、F
C、G
D、H
23、一棵二叉树中有10个度为2的结点，8个度为1的结点，则叶子结点有（）个。
A、10
B、11
C、12
D、13
24、 有n(n>0)个结点的完全二叉树的深度是()。
A、┕ log2n┘
B、┕ log2n+1┘
C、┕ log2n+1┘
D、 log2(n)+1
25、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。
A、先序
B、中序
C、后序
D、从根开始按层次遍历
26、下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A、二叉排序树
B、哈夫曼树
C、AVL树
D、堆
27、 在一棵三叉树中，度为3的结点个数为3个，度为2的结点个数为1个，度为1的结点个数为2个，则度为0的结点个数为()个。
A、8
B、 5
C、 6
D、 7
28、树是结点的集合，一棵非空的树有()个根结点。
A、 1且只有1
B、 1或多于1
C、 0或1
D、 至少2
29、在一棵高度为k的满二叉树中，结点总数为（）
A、2k-1
B、2k
C、2k-1
D、log2k+1
30、一棵完全二叉树上有1001个结点，则叶子结点的个数是（）
A、250
B、500
C、254
D、501
先序中序后序遍历二叉树31、先序序列为a、b、c、d的不同二又树的个数是( )
A、13
B、14
C、15
D、16
32、树形结构是数据元素之间存在的一种()。
A、一对一关系
B、多对多关系
C、多对一关系
D、一对多关系
33、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A、9
B、11
C、15
D、不确定
34、一棵具有n个结点的完全二叉树的树高度（深度）是（）
A、⌊ log2n+1 ⌋
B、log2n+1
C、⌊ log2n ⌋
D、⌊ log2n-1 ⌋
35、若一棵完全二叉树有 768个结点，则该二叉树中叶子结点的个数是( )
A、257
B、258
C、384
D、385
36、 当一棵二叉树的前序序列和中序序列分别是HGEDBFCA和EGBDHFAC时，其后序序列必是().
A、 BDEAGFHC

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。