第六章考研习题()

1．高度为 K的二叉树最大的结点数为（ ）。【山东大学 2001 二、3 (1分)】

kk-1kk-1

A．2 B．2 C．2 -1 D．2-1 2. 利用二叉链表存储树，则根结点的右指针是（ ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空 3．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次 4、高度为h的满二叉树对应的森林由（）棵树构成。

h

A．1 B．log2 C．h/2 D．h

5某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：( ),二叉树对应的森林包括多少棵树（ ）。

6一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树

7在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）

A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同

8某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 9在完全二叉树中，若一个结点是叶结点，则它没（ ）。

A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点

10在下列情况中，可称为二叉树的是（ ）

A．每个结点至多有两棵子树的树 B. 哈夫曼树 C．每个结点至多有两棵子树的有序树

D. 每个结点只有一棵右子树 E．以上答案都不对

11 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A． n-1 B．n C． n+1 D． n+2 12由3 个结点可以构造出多少种不同的有向树？（ ）

A．2 B．3 C．4 D．5 13由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 14下述编码中哪一个不是前缀码（ ）。【中科院计算所 2000 一、2 （2分）】

A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 应用题：

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

2已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 【西安电子科技大学2000计应用 一、4 （5分）】

3 已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？

4．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。

5、设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：

（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？

6．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。

7、已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。

【东北大学 1999 六、3 （12分）】

8．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称 为huffman 树。（1）给出构造huffman 树 的算法。

（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。 （3）用c语言编写构造huffman 树的程序.

序号 1 2 向 A B 15 6 3 C 7 4 D 12 5 E 25 6 F 4 7 G 6 8 H 1 9 I 15

本文来源：https://www.bwwdw.com/article/0w18.html