C# · 12月 19, 2021

数据结构作业11—二叉树(选择题)

2-1要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶结点须满足的条件是:(2分)

A.结点的度均为2

B.只有右子树

C.结点的度均为1

D.只有左子树

作者: 考研试卷

单位: 浙江大学

2-2若一棵二叉树的后序遍历序列是{ 1,3,2,6,5,7,4 },中序遍历序列是{ 1,4,7 },则下列哪句是错的?(3分)

A.2是1和3的父结点

B.7是5的父结点

C.这是一棵二叉搜索树

D.这是一棵完全二叉树

作者: 陈越

单位: 浙江大学

2-3在下述结论中,正确的是: (2分)

①只有一个结点的二叉树的度为0;

②二叉树的度为2;

③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③

B.②④

C.②③④

D.①④

作者: DS课程组

单位: 浙江大学

2-4如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最少为:(3分)

A.(k​h−1)/(k−1)−1

B.k(h−1)+1

C. kh

D.(k​h−1 −1)/(k−1)+1

注:不会做就代个数

作者: DS课程组

单位: 浙江大学

2-5如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T有m个非叶子结点,则T中的叶子结点个数为:(3分)

A.m(k−1)−1

B.m(k−1)+1

C.m(k−1)

D. mk

注:仅有根结点的树,此结点既是根结点又是叶子结点

作者: DS课程组

单位: 浙江大学

2-6三叉树中,度为1的结点有5个,度为2的结点3个,度为3的结点2个,问该树含有几个叶结点? (3分)

A.13

B.12

C.10

D.8

作者: DS课程组

单位: 浙江大学

2-7给定二叉树如下图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4,则其遍历方式是: (2分)

A.LRN

B.RLN

C.RNL

D.NRL

作者: DS课程组

单位: 浙江大学

2-8任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 (2分)

A.不发生改变

B.以上都不对

C.不能确定

D.发生改变

作者: DS课程组

单位: 浙江大学

2-9若一棵二叉树的前序遍历序列是{ 4,1,7 },中序遍历序列是{ 1,7 },则下列哪句是错的?(3分)

A.2是5的父结点

B.这是一棵二叉搜索树

C.所有的奇数都在叶子结点上

D.这是一棵完全二叉树

作者: 何钦铭

单位: 浙江大学

2-10设n、m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是 (3分)

A.n在m右方

B.n是m子孙

C.n是m祖先

D.n在m左方

作者: DS课程组

单位: 浙江大学

2-11某二叉树的中序序列和后序序列正好相反,则该二叉树一定是 (2分)

A.任一结点无左孩子

B.高度等于其结点数

C.任一结点无右孩子

D.空或只有一个结点

作者: DS课程组

单位: 浙江大学

2-12某二叉树的前序和后序遍历序列正好相反,则该二叉树一定是 (2分)

A.任一结点无右孩子

B.任一结点无左孩子

C.高度等于其结点数

D.空或只有一个结点

作者: DS课程组

单位: 浙江大学

2-13已知二叉树的先序遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH,则该二叉树形态中,父节点的右子节点为()。 (2分)

A.H

B.F

C.G

D.D

作者: 佚名

单位: 互联网

2-14已知一棵二叉树的树形如下图所示,其后序序列为{ e,a,c,b,d,g,f }。树中与结点a同层的结点是:(3分)

A.f

B.g

C.d

D.c

作者: 考研试卷

单位: 浙江大学

2-15二叉树中第5层(根的层号为1)上的结点个数最多为:(2分)

A.32

B.16

C.15

D.8

作者: DS课程组

单位: 浙江大学

2-16先序遍历图示二叉树的结果为 (2分)

A.H,D,I,B,E,A,F,C,G

B.H,I,D,B,E,F,G,A,C

C.A,B,D,H,I,E,C,F,G

D.A,B,C,D,H,E,I,F,G

作者: DS课程组

单位: 浙江大学

2-17设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点,则此类二叉树的最少结点数和最多结点数分别为: (3分)

A.2h−1,2h−1​​−1

B.2h−1,2h ​​−1

C.2h−1+1,2h ​​−1

D.2h,2h​​ −1

作者: DS课程组

单位: 浙江大学

2-18有一个四叉树,度2的结点数为2,度3的结点数为3,度4的结点数为4。问该树的叶结点个数是多少?(2分)

A.21

B.20

C.12

D.10

作者: 何钦铭

单位: 浙江大学

2-19按照二叉树的定义,具有3个结点的二叉树有几种? (2分)

A.6

B.5

C.4

D.3

作者: DS课程组

单位: 浙江大学

2-20如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最多为:(3分)

A.以上都不是

B.(kh−1 ​​−1)/(k−1)

C.(kh+1 ​​−1)/(k−1)

D.(kh​ −1)/(k−1)

作者: DS课程组

单位: 浙江大学