第四章树真题
2 .假设某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为(A.acbed B.becab C.deabc D.cedba )
3 .用二叉树的链表表示包含n个节点的二叉树时，空指针字段的数量为(A.n-1 B.n C.n 1 D.n 2 12 )。 关于树的描述是正确的) ) )。
a .每个内部节点至少有一个兄弟b。 每个叶节点都有父节点
c .有没有部分树的树d .每棵树至少有一个根节点和一个叶节点。 24 .对于一棵二叉树，如果有m个叶，则树中的节点数为____________。
30 .已知一二叉树的尖根扫描序列为ABCDEGHF，中根扫描序列为CBEDAGFH，并描绘该二叉树。 34 .二叉树以二叉树的链表形式存储，建立判别给定二叉树是否为完全二叉树的算法。
用5.9、2、5、7四个叶的节点构造霍夫曼树，该树的权路径长为(A.23 B.37 C.44 D.46 12 ) n个值构造两股排序树，其最大高度为) a.n/2b.NC
22 .在具有n个节点的完全二叉树中，从树根开始从上到下、从左到右对所有节点进行编号。 如果编号I的节点具有父节点，则该父节点的编号为_____。 23 .深度为k的二叉树的节点数最多为________个。
24 .如果某二叉树的后根扫描为ABKCBPM，则该二叉树的根为______。
29 .某通信电文由a、b、c、d、e、f六个字符码组成，各字符码在电文中出现的次数分别为6。
5、9、10、20、1，让我们画一个用于这六个字符代码的霍夫曼树。
30 .已知一个二叉树的顺序记忆结构如问题30图所示，其中表示虚拟节点，尝试构造该二叉树。
A B G C D H E F题30图
34 .如果两个二叉树B1和B2都为空，或都不是空，B1的左、右部分树和B2的左、右部分树分别相似，则称为二叉树B1和B2相似。 试着写算法，判别给定的两根二叉树是否相似。
8 .具有n个节点二叉树，指向孩子节点的分枝数为(A.n-1 B.n C.n 1 D.2n )
对具有9.100个节点的完全二叉树按层序进行编号，编号为49个节点，其左边孩子的编号为(A.99 B.98 C.97 D.50 10具有10个叶节点的霍夫曼树，该节点总数为) )。
a.2m-1b.2mc.2m1d.2(m1 ) 22 .深度为k的二叉树最多有________个节点，最低有_ _ _ _ _个节点。
29 .已知一棵二叉树的前序序列为ABCDEFG，中序序列为CBDAEGF。 请将此二叉树结构化，并给出此二叉树的后序列。
30 .问题30把图中所示的三棵树组成的森林变成一棵二叉树。
13
8 .如果使用二叉树链表存储包括n个节点的二叉树，则空指针字段的数目为(A.n-1 B.n C.n 1 D.n 2)
9 .在深度为h的完全二叉树中，包含的节点数不小于(A.2H-1-1 B.2H-1 C.2H-1 D.2H
19 .深度为10的二叉树逐层编号，编号为51个节点，其父母节点编号为_______。 21 .有n个叶子节点的霍夫曼树。 该节点的总数为________。
22 .在具有n个节点的树中，所有非终端节点的度为k的情况下，该树的叶的节点数为________。 25 .如果某二叉树的后根遍历序列为abd，中根遍历序列为adb，则该前根遍历序列为________。 30 .出题30图所示画二叉树二叉树的二叉树链表存储结构。
35 .二叉树的节点类型定义如下。 类型结构节点{数据类型数据；
结构节点*液晶屏，*液晶屏； (} Bi树； Bitree*t；
试着创建计算二叉树深度的递归算法((intdepth ) bitree*t ) )。
8 .如果某二叉树的先根扫描序列和后根扫描序列正好相反，则该二叉树具有的特征是() ) ) ) ) ) ) ) ) ) ) 65 )
a .高度等于其节点数b。 其中一个节点上没有左子项c。 其中一个节点没有右边的子节点d。 天空或只有一个节点9。 在完全二叉树中，如果一个节点是叶节点，则没有(
a .构建具有左儿童节点b .右儿童节点c .左儿童节点和右儿童节点d .左儿童节点、右儿童节点和兄弟节点12.n个节点的双叉排序树，最坏情况下其深度为(a.n/2 b.n c.n 1
21.100个节点的完全二叉树按层次进行编号，编号为49个节点，其左边孩子的编号为________。 30 .已知一个二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，我们来描绘这个二叉树。
8 .除根节点外，树的每个节点() )。
a .孩子可以是任何人，
一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( )14
A.2 B.3 C.5 D.8
20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。
21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。
29.分别写出题29图中二叉树的先根、中根、后根遍历序列。
10．高度为h的完全二叉树中，结点数最多为( )A．2h-1 B.2h+1 C.2h-1 D.2h 11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是( )A．mn B.mn-1 C.n(m-1) D.m(n-1) 21．有4个结点且深度为4的二叉树的形态共有_______种。
22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。
30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。
8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为( ) A.3 B.4 C.5 D.6
9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为( ) A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。
22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。
29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、G、F、A，试画出这棵二叉树，并给出其先根序列。 7.关于二叉树性质的描述，正确的是( )
A.二叉树结点的个数可以为0 B.二叉树至少含有一个根结点 C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子
15
D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 8.具有4个结点的二叉树可有( )
A.4种形态 B.7种形态 C.10种形态 D.11种形态 22.深度为k的满二叉树其叶子结点个数共有________________个。 23.二叉树通常采用________________两种存储结构表示。 29.试采用类C语言，给出二叉树的二叉链表结构描述。
35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述 7.树是n个结点的有穷集合，( )
A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子C.2k-1个叶子 D.2k-1-1个叶子 22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。
23.落寞的鼠标二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。 29．对于如题29图所示二叉树，分别写出其先根遍历，中根遍历，后根遍历的结点访问序列。
35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数(可采用递归算法描述)。 7．深度为k的二叉树最多有()个结点
22.落寞的鼠标二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为______。 23.具有n个结点的完全二叉树，其深度为___________。 29．已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
35.二叉树是由所有度数不大于2的结点构成的一种特定树，落寞的鼠标结点度为2，则该结点有左 右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。 7.根据定义，树的叶子结点其度数( )
A.必大于 0 B.必等于0 C.必等于1 D.必等于2
8.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有( ) A.2n个指针域其中n个指针为NULL B.2n个指针域其中n+1个指针为NULL C.2n-1个指针域其中n个指针为NULL D.2n-1个指针域其中n+1个指针为NULL 22.树的遍历主要有先根遍历、后根遍历和___________三种。 23.深度为k的完全二叉树至少有___________个结点。
29.已知某二叉树如下图所示，试给出其二叉链表及顺序存储结构表示。
16