武汉软件工程职业学院软件技术专业大二数据结构二测.docx
《武汉软件工程职业学院软件技术专业大二数据结构二测.docx》由会员分享，可在线阅读，更多相关《武汉软件工程职业学院软件技术专业大二数据结构二测.docx（22页珍藏版）》请在冰点文库上搜索。
武汉软件工程职业学院软件技术专业大二数据结构二测
武汉软件工程职业学院软件技术专业大二2019数据结构二测
1.树形结构中元素之间存在一个对多个的关系。
[判断题]*
对（正确答案）
错
2.先根遍历树正好等同于按___遍历对应的二叉树[单选题]*
A.先根（正确答案）
B.中根
C.后根
D.层次
3.将一棵树转成二叉树，根结点没有左子树。
[判断题]*
对
错（正确答案）
4.后根遍历树正好等同于按___遍历对应的二叉树。
[单选题]*
A.先根
B.中根（正确答案）
C.后根
D.层次
5.赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
[判断题]*
对（正确答案）
错
6.赫夫曼树的结点个数不能是偶数。
[判断题]*
对（正确答案）
错
答案解析：
n个权值构成的赫夫曼树共有2n-1个节点，为奇数
7.树最适合用来表示（）[单选题]*
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据（正确答案）
D、元素之间无联系的数据
8.下面那个是完全二叉树（）*
A
B
C（正确答案）
D（正确答案）
9.以下关于树和二叉树的描述，正确的是（）[单选题]*
各结点的度均为2的树即为二叉树
任一遍历序列可唯一确定一棵二叉树
任何树都可以转换为唯一的二叉树与之对应（正确答案）
树和二叉树都只能用链式存储实现
10.3个结点构成的二叉树，共有（）种[单选题]*
3
4
5（正确答案）
6
11.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
[单选题]*
24
48
72
53（正确答案）
12.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
[判断题]*
对（正确答案）
错
13.二叉树中每个结点的两棵子树的高度差等于1。
[判断题]*
对
错（正确答案）
14.二叉树中每个结点有两棵非空子树或有两棵空子树。
[判断题]*
对
错（正确答案）
15.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
[判断题]*
对
错（正确答案）
16.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
[判断题]*
对
错（正确答案）
17.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
[判断题]*
对（正确答案）
错
18.具有12个结点的完全二叉树有5个度为2的结点。
[判断题]*
对（正确答案）
错
19.二叉树是非线性数据结构，所以（）。
[单选题]*
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储;
C.顺序存储结构和链式存储结构都能存储;（正确答案）
D.顺序存储结构和链式存储结构都不能使用
20.18.设T是一棵有n个顶点的树，下列说法不正确的是（）。
[单选题]*
A.T有n条边（正确答案）
B.T是连通的
C.T是无环的
D.T有n-1条边
21.14．高度为n的均衡的二叉树是指：
如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。
在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。
[单选题]*
A.10
B.11（正确答案）
C.12
D.13
22.5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。
[单选题]*
A.2n-1（正确答案）
B.2n
C.2n+1
D.2n+1
23.14、一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（）。
[单选题]*
A．2n+1
B．2n-1
C．n-1
D．n+1（正确答案）
24.7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。
[单选题]*
A．10
B．11
C．12（正确答案）
D．13
25.9.已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。
[单选题]*
A.4（正确答案）
B.5
C.6
D.7
26.5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。
[单选题]*
A.N-1
B.N（正确答案）
C.2*N
D.2*N-1
27.⒗一棵具有5层的满二叉树中结点数为（）。
[单选题]*
A.31（正确答案）
B.32
C.33
D.16
28.⒘如果根的高度为1,具有61个结点的完全二叉树的高度为（）。
[单选题]*
A.5
B.6（正确答案）
C.7
D.8
29.19．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。
[单选题]*
A.2k
B.2k+1
C.k/2下取整（正确答案）
D.（k+1）/2下取整
30.20.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）[单选题]*
A.321465
B.321546（正确答案）
C.213546
D.231465
31.20.已知7个结点的二叉树的先根遍历是1245637（数字为结点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（）[单选题]*
A.4652731（正确答案）
B.4652137
C.4231547
D.4653172
32.13.二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（）。
[单选题]*
A.4257631
B.4275631（正确答案）
C.7425631
D.4276531
33.17．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。
[单选题]*
A.2（正确答案）
B.3
C.4
D.5
34.6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
[单选题]*
A．ABC
B．CBA
C．ACB（正确答案）
D．BAC
35.11.二叉树的（）第一个访问的节点是根节点。
[单选题]*
A.先序遍历（正确答案）
B.中序遍历
C.后序遍历
D.以上都是
36.⒗前序遍历序列与中序遍历序列相同的二叉树为（）。
[单选题]*
A.根结点无左子树
B.根结点无右子树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树（正确答案）
37.13、表达式a*（b+c）-d的后缀表达式是：
[单选题]*
A.abcd*+-
B.abc+*d-（正确答案）
C.abc*+d-
D.-+*abcd
38.9．前缀表达式“+3*2+512”的值是（）。
[单选题]*
A.23
B.25
C.37（正确答案）
D.65
39.树最适合用来表示（）[单选题]*
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据（正确答案）
D、元素之间无联系的数据
40.在完全二叉树中，若一个结点是叶结点，则它没（）。
[单选题]*
A、左子结点
B、右子结点
C、左子结点和右子结点（正确答案）
D、以上说法都不对
41.有三个结点的二叉树有（）种形态。
[单选题]*
3
4
5（正确答案）
6
42.下面那个是完全二叉树（）*
A
B
C（正确答案）
D（正确答案）
43.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）[单选题]*
A、9
B、11（正确答案）
C、15
D、不确定
44.在一棵二叉树上第5层的结点数最多是多少（）个？
[单选题]*
14
15
16（正确答案）
17
答案解析：
一棵二叉树，如果每个结点都是是满的，那么会满足2^（k-1）1。
所以第5层至多有2^（5-1）=16个结点！
45.深度为6的二叉树最多有（）个结点。
[单选题]*
64
63（正确答案）
32
31
答案解析：
见二叉树性质
46.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（）个？
[单选题]*
218
216
219（正确答案）
217
答案解析：
假设n表示二叉树的所有结点数，n0表示度为0的结点（叶子结点），n1表示度为1的结点，n2表示度为2的结点：
n=n0+n1+n2,又由二叉树性质：
n2=n0-1，将n2带入得总结点数n=70+80+70-1=219
47.一棵具有5层的满二叉树中结点数为（）。
[单选题]*
A.31（正确答案）
B.32
C.33
D.16
48.如果根的高度为1,具有61个结点的完全二叉树的高度为（）。
[单选题]*
A.5
B.6（正确答案）
C.7
D.8
答案解析：
根据二叉树性质，从所给答案中取值计算。
49.一个具有1025个结点的二叉树的高h为（）？
[单选题]*
二叉树的高度的公式是什么？
11
10
11至1025之间（正确答案）
10至1024之间
答案解析：
若该二叉树为完全二叉树，根据二叉树性质或计算某一深度的满二叉树的结点总数，向下取整log2（1025）+1≈log2（1024）+1=log2（2^10）+1=10+1=11；或深度为10的满二叉树有2^10-1=1024-1=1023,1025>1023,所以至少11层。
该二叉树有至少有11层。
层数最多时：
每层一个结点，有1025层
50.已知一棵完全二叉树含有1001个结点，那么它有（）个度为2的结点。
[单选题]*
250
500（正确答案）
501
505
答案解析：
设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0+n1+n2=1001根据二叉树性质：
n0=n2+1，代入得到，2n2+1+n1=1001由于完全二叉树的n1只能是0或者1，为满足2n2+1+n1=1001，只有n1=0时上式才能成立，因此n2=500，n0=501。
此题有时也考叶子结点数目。
51.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。
[单选题]*
A.acbed
B.decab
C.deabc
D.cedba（正确答案）
52.二叉树的先序遍历和中序遍历如下：
先序遍历：
EFHIGJK；中序遍历:
HFIEJKG。
该二叉树根的右子树的根是：
[单选题]*
A.E
B.F
C.G（正确答案）
D.H
答案解析：
注意审题，要求二叉树根右子树的根结点，由先序序列可知二叉树的根结点为E，所以在中序序列中E的左子树不需考虑。
53.表达式a*（b+c）-d的后缀表达式是：
[单选题]*
A.abcd*+-
B.abc+*d-（正确答案）
C.abc*+d-
D.-+*abcd
54.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。
[单选题]*
A.2k
B.2k+1
C.k/2下取整（正确答案）
D.（k+1）/2下取整
55.以下说法错误的是（）。
[单选题]*
树形结构的特点是一个结点可以有多个直接前趋（正确答案）
线性结构中的一个结点至多只有一个直接后继
树形结构可以表达（组织）更复杂的数据
树（及一切树形结构）是一种"分支层次"结构
56.以下说法正确的是（）。
[单选题]*
A.二叉树不能用顺序存储结构存储
B.二叉树不能用链式存储结构存储;
C.二叉树顺序存储结构和链式存储结构都能存储;（正确答案）
D.二叉树顺序存储结构和链式存储结构都不能使用
57.3个结点构成的二叉树，共有（）种[单选题]*
3
4
5（正确答案）
6
58.二叉树的第i层上最多含有结点数为（）[单选题]*
2的i次方
2的i-1次方减1
2的i-1次方（正确答案）
2的i次方减1
59.下列正确的是（）[单选题]*
如图
先序遍历结果：
ABCDFE
中序遍历结果：
BDCAFE
后序遍历结果：
DCBFEA（正确答案）
60.如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。
[单选题]*
A.2^n-1（正确答案）
B.2^（n-1）
C.2^n
D.2^n+1
答案解析：
根据二叉树性质，或让n取简单的值进行计算，如n=2，n=3等。
61.已知一棵二叉树有10个结点，则其中至多有（）个度为2的结点。
[单选题]*
A.4（正确答案）
B.5
C.6
D.7
答案解析：
设总结点数为n，度为0,1,2的结点数分别为no,n1,n2,则有：
n=n0+n1+n2,根据二叉树性质将n0=n2+1和n=10带入得：
10=2n2+1+n1,要使n2最大，只有取n1=1，此时n2=4。
62.完全二叉树共有2*N-1个结点，则它的叶节点数是（）。
[单选题]*
A.N-1
B.N（正确答案）
C.2*N
D.2*N-1
答案解析：
取N为某一具体值。
63.一棵具有5层的满二叉树中结点数为（）。
[单选题]*
A.31（正确答案）
B.32
C.33
D.16
64.具有1024个结点的二叉树的深度为（）。
[单选题]*
10
11
1024
无法确定（正确答案）
65.线索二叉树中，（）表示当前节点的前驱。
[单选题]*
ltag=0时lchild
ltag=1时lchild（正确答案）
rtag=1时rchild
rtag=0时rchild
66.若二叉树用二叉链表作存储结构，则在n个结点的二叉树链表中只有n—1个空指针域。
[判断题]*
对
错（正确答案）
67.某哈夫曼树中有199个结点，则其叶子结点的个数为（）[单选题]*
99
100（正确答案）
101
102
68.二叉树的深度为6，则二叉树最多有（）个结点。
[单选题]*
A.12
B.63（正确答案）
C.64
D.11
69.用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）。
[单选题]*
A.R[2*i-1]
B.R[2*i+1]（正确答案）
C.R[2*i]
D.R[2/i]
70.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（）。
[单选题]*
A.a在b的右方
B.a在b的左方（正确答案）
C.a是b的祖先
D.a是b的子孙
71.设一棵二叉树的中序遍历序列：
badce，后序遍历序列：
bdeca，则二叉树先序遍历序列为（）。
[单选题]*
A.adbce
B.decab
C.debac
D.abcde（正确答案）
72.在一棵具有5层的完全二叉树中结点总数至少为（）。
[单选题]*
A.31
B.32
C.33
D.16（正确答案）
73.某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（）。
[单选题]*
A.3
B.2
C.4（正确答案）
D.5
74.将一棵有90个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为0，则编号为40的结点的左孩子编号为（）。
[单选题]*
A.81（正确答案）
B.80
C.41
D.79
75.对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（）。
[单选题]*
A.DBFEAC
B.DFEBCA（正确答案）
C.BDFECA
D.BDEFAC
76.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
[单选题]*
A.不发生改变（正确答案）
B.发生改变
C.不能确定
D.以上都不对
77.假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。
[单选题]*
A.15
B.16（正确答案）
C.17
D.47
78.下面说法中正确的是（）。
[单选题]*
A.度为2的树是二叉树
B.度为2的有序树是二叉树
C.子树有严格左右之分的树是二叉树
D.子树有严格左右之分，且度不超过2的树是二叉树（正确答案）
79.按照二叉树的定义，具有3个结点的二叉树有（）种。
[单选题]*
A.3
B.4
C.5（正确答案）
D.6
升级会员 