[考研类试卷]计算机专业基础综合数据结构（树和二叉树）历年真题试

卷汇编12

一、综合题

1 已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。【北京工业大学1998五(10分)】

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

2 T树的最大可能深度Kmax=?最小可能深度Kmin=?

3 T树中共有多少非叶结点?

4 若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。【北京邮电大学1992一、3(15／3分)】

5 已知4个字符A，E C，D的哈夫曼编码分别是1，01，000,001。下列01串是由以上4个字母构

成的一段文本的哈夫曼编码：

1001000011011010011010011

请将上述01串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树

的带权路径长度。【电子科技大学2013三、1(5分)】

6 什么是前缀编码?举例说明如何利用二叉树来设计二进制的前缀编码。【中山大学1999三、1(3分)】

二、设计题

6 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：

，其中叶

答案见麦多课文库

结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：

7 给出算法的基本设计思想；

8 使用C或C++语言，给出二叉树结点的数据类型定义；

9 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。【2014年全国试题41(13分)】

10 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。【东北大学2000三、2(10分)】

11 给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。【北京邮电大学2001五、3(10分)】

12 设计一算法分别求出二元树的叶结点，度数为l的结点，度数为2的结点的个数。【哈尔滨工业大学2002八(8分)】

13 已知深度为h的二叉树，以一维数组BT[0．．2h-2]作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。【中南大学2003八(10分)】

14 假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二元树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=O(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[b]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学1999七(14分)】【华南师范大学2000六(17分)】

15 要求二叉树按二叉链表形式存储。 (1)写一个建立二叉树的算法。

(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至Ⅳ的结点一一对应。此题以此定义为准。【西北大学2000六(12分)】【哈尔滨工

答案见麦多课文库

业大学2000十一(14分)】【南开大学1997四 (16分)】【北京邮电大学1994九(20分)】

16 有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。【南京理工大学1998七、1(6分)】【同济大学2005三、2(7分)】

17 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。(注：按层从上到下，由左到右)。【中科院研究生院2005四(15分)】

18 已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1：2h一1】中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由T给出。【北京师范大学2005六、3(15分)】【北京航空航天大学1999七(15分)】

19 二叉树的动态二叉链表结构中的每个结点有三个字段：dam，lchild，rchild。其中指针lchild和rchild的类型为bike。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二又树的静态二叉链表如右图所示。

编写算法由二叉

树的动态二叉链表构造出相应的静态二又链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。【合肥工业大学2000五、3(8分)】

20 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注：已知树中结点数)【清华大学1994七(15分)】

21 设一棵二叉树用二叉链表表示，求该树的高度。【南京航空航天大学2004二、2(12分)】【北京理工大学2000四3(4)】【北京轻工业学院1997一(15分)】

答案见麦多课文库

22 二叉树以链接形式(1eft，data，right)存储，给出求二叉树宽度的算法，所谓宽度是二又树的各层上，具有结点数最多的那一层上的结点总数。 【吉林大学2006四(10分)】【华南理工大学2004三、1(10分)】

23 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学1999五(18分)】【南京航空航天大学2000九】

24 设一棵二叉树的结点结构为(LLINK，INFO，RLINK)，ROOT为指向该二叉树根结点的指针，p和g分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR(RDOT，p，q，r)，该算法找到p和q的最近共同祖先结点r。【吉林大学2000二、3(12分)】【中山大学1994六(15分)】

25 当一棵有n(0<=100)个结点的二叉树按顺序存储方式存储在bf[1..n]中时，试写一个算法，求出二叉树中结点值分别为x和y的两个结点的最近的公共祖先结点的值。【同济大学2003四(10分)】【武汉大学2000五】

26 设一棵完全二叉树使用顺序存储在数组6f[1..n]中，请写出进行非递归的前序遍历算法。【西安电子科技大学1998四(9分)】

27 若二叉树用以下存储结构表示，试给出求前序遍历的算法：TYPE Tree=ARRAY[1．．max] OF RECORD data：char ; parent：integer； END；

【北京邮电大学2002

五、4(15分)】

28 设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。【合肥工业大学1999五、2(8分)】

29 已知一棵高度为k具有n个结点的二叉树，按顺序方式存储： (1)编写用先根遍历树中每个结点的非递归算法；

(2)编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学1997六(20分)】

答案见麦多课文库