历年真题分类整理

26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。

前序序列： 后序序列：

21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为 {,,,,,}，该树的度是 。

7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）

A. 0 B. 1 C. 48 D. 49

28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：

(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)； (2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。 (1) (2)

21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有_________棵。 7.高度为5的完全二叉树中含有的结点数至少为( )

A.16 B.17 C.31 D.32 8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A.5 B.8 C.11 D.18

9.下列所示各图中是中序线索化二叉树的是( )

27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼

编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

9

21．任意一棵完全二叉树中，度为1的结点数最多为________。

9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ ） A．FEDCBA B．ABCDEF C．FDECBA D．FBDCEA

10．已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，l，

2，则与F对应的二叉树的右子树中的结点个数为（ ） A．2 B．3 C．8 D．11 29．已知一棵二叉排序树如图所示。 请回答下列问题：

(1)画出插入元素23后的树结构；

(2)请画出在原图中删除元素57后的树结构。

26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作：

(1)遍历右子树； (2)访问根节点； (3)遍历左子树。

已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。

21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长

度为_________。

10．下列数据结构中，不属于二叉树的是（ ）

A．B树 B．AVL树 C．二叉排序树 D．哈夫曼树 28.已知二叉树如下：

10

请画出该二叉树对应的森林。

19.3个结点可以组成___________种不同树型的二叉树。

20.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( )

7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n C.

+1

B. D.n/2

26.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG， 请回答下列问题： (1)画出此二叉排序树；

(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。

24.在一棵深度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是______________。 21.一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是________________。

7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ ） A.结点均无左孩子的二叉树 C.高度为n的二叉树

B.结点均无右孩子的二叉树 D.存在度为2的结点的二叉树

8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ ）

11

A.4 B.5 C.7 D.8

27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。 （1）画出该森林；

（2）画出该森林所对应的二叉树。 (1) (2)

21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为__________。

9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ） A.12 B.16 C.18 D.20

28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。

6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ ） A.9 B.11 C.15 D.不确定 13.下述编码中不是前缀码的是（ ）

A.(00，01，10，11) B.(0，1，00，11) C.(0，10，110，111) D.(1，01，000，001)

七、图

返回

22.n个顶点且含有环路的无向连通图中，至少含有 条边。

8.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ） A. Dout B. Dout-1 C. Dout+1 D. n

9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ） A. 3 B. 4 C. 5 D. 6

10.如图所示的带权无向图的最小生成树的权为（ ）

A. 51 B. 52 C. 54 D. 56

22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。

10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( )

12