内容发布更新时间 : 2024/6/3 21:19:27星期一 下面是文章的全部内容请认真阅读。

C)756 D)不确定

C【解析】叶子结点有45个，根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，则度为2的结点数为44个，因此度为1的结点数为845-45-44=756个。

65.某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为 A)32 B)46 C)48 D)49

C【解析】根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，得度为0的结点数为16+1=17个，故总的结点数=17+15+16=48个。

66.某二叉树共有730个结点，其中度为1的结点有30个，则叶子结点个数为 A)1 B)351 C)350

D)不存在这样的二叉树

D【解析】设叶子结点数为n，根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，则度为2的结点数为n-1,n+n-1+30=730，得n=350.5。由于结点数只能为整数，所以不存在这样的二叉树。

67.某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为 A)不可能有这样的二叉树 B)150 C)199 D)149

A【解析】叶子结点数为200，根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，则度为2的结点数为199，199+200>350，故不存在这样的二叉树。

68.某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为 A)0 B)1 C)2 D)63

A【解析】叶子结点有64个，根据在二叉树中度为0的结点（叶子结点）总比度为2的结点多一个，则度为2的结点数为63个；又深度为m的二叉树最多有2-1个结点，则该二叉树最多有2-1=127个结点。64+63=127，因此该树不存在度为1的结点。

m

7

69.深度为7的二叉树共有127个结点，则下列说法中错误的是

A)该二叉树是满二叉树 B)该二叉树有一个度为1的结点 C)该二叉树是完全二叉树 D)该二叉树有64个叶子结点

B【解析】满二叉树满足深度为m的二叉树最多有2-1个结点，本题中二叉树深度为7且有127个结点，满足2-1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第k层上有2结点，则该二叉树的叶子结点数为2=64个。满二叉树不存在度为1的结点。

7-1

7

k-1

m

70.深度为5的完全二叉树的结点数不可能是 A)15 B)16 C)17 D)18

A【解析】设完全二叉树的结点数为n，根据深度为k的二叉树至多有2-1个结点，再根据完全二叉树的定义可知，2-1

k-1

k-1。本题中完全二叉树的深度为5，则25-1-1

k

71.某完全二叉树共有256个结点，则该完全二叉树的深度为 A)7 B)8 C)9 D)10

C【解析】根据完全二叉树的性质：具有n个结点的完全二叉树的深度为[log2n]+1。本题中完全二叉树共有256个结点，则深度为[log2256]+1=8+1=9。

72.深度为７的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为 A)62 B)63 C)64 D)65

B【解析】在满二叉树的第k层上有2个结点、且深度为m的满二叉树有2-1个结点，则深度为6的满二叉树共有2-1=63个结点，第6层上有2=32个结点。本题是深度为7的完全二叉树，则前6层共有63个结点，第7层的结点数为125-63=62个且全为叶子结点。由于第6层上有32个结点，第7层上有62个结点，则第6层上有1个结点无左右子树（该结点为叶子结点）。因此，该完全二叉树中共有叶子结点62+1=63个。

6

6-1k-1

m

73.在具有2n个结点的完全二叉树中，叶子结点个数为 A)n B)n+1 C)n-1 D)n/2

A【解析】由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点（即叶子结点）总比度为2的结点多一个，得度为2的结点有a-1个。再根据完全二叉树的定义，度为1的结点有0个或1个，假设度1结点为0个，a+0+a-1=2n，得2a=2n-1，由于结点个数必须为整数，假设不成立；当度为1的结点为1个时，a+1+a-1=2n，得a=n，即叶子结点个数为n。

74.下列数据结构中为非线性结构的是 A)二叉链表 B)循环队列 C)循环链表 D)双向链表

A【解析】二叉树的链式存储结构也称为二叉链表，二叉树是树的一种，属于非线性结构。

75.下列叙述中正确的是

A)非完全二叉树可以采用顺序存储结构 B)有两个指针域的链表就是二叉链表 C)有的二叉树也能用顺序存储结构表示 D)顺序存储结构一定是线性结构

C【解析】在计算机中，二叉树通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此A项错误，C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此D项错误。双向链表也有两个指针域，因此B项错误。

76.有二叉树如下图所示：

则前序序列为 A)ABDEGCFH B)DBGEAFHC C)DGEBHFCA D)ABCDEFGH

A【解析】前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。

中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是DBGEAFHC。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是DGEBHFCA。

77.设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为 A)JIHGFEDCBA B)DGHEBIJFCA C)GHIJDEFBCA

D)ABCDEFGHIJ

B【解析】二叉树的前序序列为ABDEGHCFIJ，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是A。再由中序序列为DBGEHACIFJ，可以得到结点D、B、G、E、H位于根结点的左子树上，结点C、I、F、J位于根结点的右子树上。由于中序遍历和后序遍历都是先遍历左子树，故本题后序遍历首先访问D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点A。采用排除法可知，后续序列为DGHEBIJFCA。

78.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBEDA，则前序遍历序列为 A)CBADE B)CBEDA C)ABCDE D)EDCBA

C【解析】二叉树的后序遍历序列为CBEDA，由于后序遍历最后访问根结点，可以确定该二叉树的根结点是A。再由中序遍历序列为CBADE，可以得到子序列（CB）一定在左子树中，子序列（DE）一定在右子树中。结点C、B在中序序列和后序序列中顺序未变，说明结点B是结点C的父结点；结点D、E在中序序列和后序序列中顺序相反，说明结点D是结点E的父结点。因此该二叉树的前序遍历序列为ABCDE。

79.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的深度（根结点在第1层）为 A)2 B)3 C)4 D)5

C【解析】二叉树的前序序列为ABCDEFG，则A为根结点；中序序列为DCBAEFG，可知结点D、C、B位于根结点的左子树上，结点E、F、G位于根结点的右子树上。另外，结点B、C、D在前序序列和中序序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。故二叉树深度为4。

80.设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为 A)ABCDHGFE B)DCBAHGFE C)EFGHABCD D)HGFEDCBA

D【解析】二叉树的前序序列与中序序列均为ABCDEFGH，可知二叉树根结点为A，且根结点A只有右子树，没有左子树。同理，可以推出结点B只有右子树无左子树。依此类推，该二叉树除叶子结点外，每个结点只有右子树无左子树。因此该二叉树的后序序列为HGFEDCBA。

81.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为 A)CBAFED B)FEDCBA

C)DEFCBA D)ABCDEF

B【解析】该二叉树的后序遍历序列与中序遍历序列均为ABCDEF，则根结点为F；根结点F只有左子树，右子树为空。即ABCDE是根结点F的左子树集合。这样问题就转化为就后序遍历序列与中序遍历序列均为ABCDE的子树，同理可得左子树集合的根结点为E，且根结点E只有左子树无右子树。依次类推，该二叉树除叶子结点外，每个结点只有左子树无右子树，结构如下：

按层次输出（同一层从左到右）的序列为FEDCBA。

82.某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出（同一层从左到右）的序列为 A)HGFEDCBA B)HFDBGECA C)ABCDEFGH D)ACEGBDFH

C【解析】二叉树的前序序列为ABDFHCEG，可以确定这个二叉树的根结点是A；再由中序序列HFDBACEG，可以得到HFDB为根结点A的左子树，CEG为根结点A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到该二叉树的结构如下：

该二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。

83.某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为 A)ABCDEFGH B)ABDHECFG C)HDBEAFCG D)HDEBFGCA

B【解析】完全二叉树的特点是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为ABCDEFGH，可以得到该二叉树的结构如下：

故此完全二叉树的前序序列为ABDHECFG。

84.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是 A)前序序列 B)中序序列 C)后序序列 D)前序序列或后序序列