【考研类试卷】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13及答案解析.doc

《【考研类试卷】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13及答案解析.doc（10页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 13及答案解析(总分：66.00，做题时间：90 分钟)一、综合题(总题数：4，分数：12.00)1.已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT 的存储结构的初态和终态。【北京工业大学 1998 五(10 分)】（分数：2.00）_设 T 是一棵二叉树，除叶子结点外，其他结点的度数皆为 2，若 T 中有 6 个叶结点，试问：（分数：6.00）(1).T 树的最大可能深度 Kmax=?最小可能深度 Kmin=?（分数：2.00）_(2).T 树中共有多少非叶结点?（分

2、数：2.00）_(3).若叶结点的权值分别为 1，2，3，4，5，6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度 wp1。【北京邮电大学 1992 一、3(153 分)】（分数：2.00）_2.已知 4 个字符 A，E C，D 的哈夫曼编码分别是 1，01，000,001。下列 01 串是由以上 4 个字母构成的一段文本的哈夫曼编码：1001000011011010011010011 请将上述 01 串还原为编码前的文本。以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。【电子科技大学 2013 三、1(5 分)】（分数：2.00）_3.什么是前缀编码?举例说明如何利用二叉树来

3、设计二进制的前缀编码。【中山大学 1999 三、1(3 分)】（分数：2.00）_二、设计题(总题数：25，分数：54.00)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为： （分数：6.00）(1).给出算法的基本设计思想；（分数：2.00）_(2).使用 C 或 C+语言，给出二叉树结点的数据类型定义；（分数：2.00）_(3).根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。【2014 年全国试题 41(13 分)】（分数：2.00）_4.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 B

4、T 中，写出计算该算术表达式值的算法。【东北大学 2000 三、2(10 分)】（分数：2.00）_5.给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。【北京邮电大学 2001五、3(10 分)】（分数：2.00）_6.设计一算法分别求出二元树的叶结点，度数为 l 的结点，度数为 2 的结点的个数。【哈尔滨工业大学2002 八(8 分)】（分数：2.00）_7.已知深度为 h 的二叉树，以一维数组 BT02 h -2作为其存储结构，试编写一算法，求该二叉树中叶子结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。【中南大学 2003 八

5、(10 分)】（分数：2.00）_8.假定用两个一维数组 LN和 RN作为有 N 个结点 1，2，N 的二元树的存储结构。Li和 Ri分别指示结点 i 的左儿子和右儿子；Li=O(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tb，使 Ti存放结点 i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。【哈尔滨工业大学 1999 七(14 分)】【华南师范大学 2000 六(17 分)】（分数：2.00）_9.要求二叉树按二叉链表形式存储。(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：

6、深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1 至的结点一一对应。此题以此定义为准。【西北大学 2000 六(12 分)】【哈尔滨工业大学 2000 十一(14 分)】【南开大学 1997 四 (16 分)】【北京邮电大学 1994 九(20 分)】（分数：2.00）_10.有 n 个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。【南京理工大学 1998 七、1(6 分)】【同济大学 2005 三、2(7 分)】（分数：2.00）_11.设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中。

7、(注：按层从上到下，由左到右)。【中科院研究生院 2005 四(15 分)】（分数：2.00）_12.已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT1：2 h 一 1】中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1child，data，rchild)，根结点所在链结点的指针由 T 给出。【北京师范大学 2005 六、3(15 分)】【北京航空航天大学 1999 七(15 分)】（分数：2.00）_13.二叉树的动态二叉链表结构中的每个结点有三个字段：dam，lchild，rchild。其中指针 lchild 和rchild 的类型为 bike。静态

8、二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild 和 rdhild 为 integer 型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为 0。例如，下面左图所示的二又树的静态二叉链表如右图所示。 编写算法由二叉树的动态二叉链表构造出相应的静态二又链表 a1n，并写出其调用形式和有关的类型描述。其中 n 为一个确定的整数。【合肥工业大学 2000 五、3(8 分)】 （分数：2.00）_14.假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注：已知树中

9、结点数)【清华大学 1994 七(15 分)】（分数：2.00）_15.设一棵二叉树用二叉链表表示，求该树的高度。【南京航空航天大学 2004 二、2(12 分)】【北京理工大学 2000 四 3(4)】【北京轻工业学院 1997 一(15 分)】（分数：2.00）_16.二叉树以链接形式(1eft，data，right)存储，给出求二叉树宽度的算法，所谓宽度是二又树的各层上，具有结点数最多的那一层上的结点总数。 【吉林大学 2006 四(10 分)】【华南理工大学 2004 三、1(10 分)】（分数：2.00）_17.以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大

10、学 1999 五(18 分)】【南京航空航天大学 2000 九】（分数：2.00）_18.设一棵二叉树的结点结构为(LLINK，INFO，RLINK)，ROOT 为指向该二叉树根结点的指针，p 和 g 分别为指向该二叉树中任意两个结点的指针，试编写一算法 ANCESTOR(RDOT，p，q，r)，该算法找到 p 和 q 的最近共同祖先结点 r。【吉林大学 2000 二、3(12 分)】【中山大学 1994 六(15 分)】（分数：2.00）_19.当一棵有 n(0left，iv+1)； 中序遍历左子树 if(bt 一left=null parent：integer； END； 【北京邮电大学

11、2002 五、4(15 分)】 （分数：2.00）_正确答案：(正确答案：另一种双亲表示法存储结构，结点结构是(dam,parent)。对每个结点，直接给出其双亲(的下标)，用正或负表示该结点是双亲的右子女或左子女，0 表示该结点是根，无双亲。该类结构不适于直接进行前序遍历(即若直接前序遍历，算法要很复杂)，较好的办法是将这类结构转为结点及其左右子女的顺序存储结构。转换的核心语句段如下： for(i=1；irchild)p=p 一rchild； 若右子树不空，沿右子树向下 else if(p 一1child)p=p 一lchild； 右子树空，左子树不空，沿左子树向下 else return(

12、p)； p 即为所求)解析：23.已知一棵高度为 k 具有 n 个结点的二叉树，按顺序方式存储：(1)编写用先根遍历树中每个结点的非递归算法；(2)编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学 1997 六(20 分)】（分数：2.00）_正确答案：(正确答案：高度为 K 的二叉树，按顺序方式存储，要占用 2 k 一 1 个存储单元，与实际结点个数 n 关系不大，对不是完全二叉树的二叉树，要增加“虚结点”，使其在形态上成为完全二叉树。二叉树中最大序号的叶子结点是在顺序存储方式下编号最大的结点。核心语句段如下：while(btc=0)c 一一； 初值 c=2 k 一 1，从

13、后向前滤去虚结点找最大序号叶子 f=c2 ； c 的双亲结点 f while(f!=0) 从结点 c 的双亲结点直到根结点，路径上所有结点均为祖先结点 coutcbtf)；f=f2 ； 逆序输出，最老的祖先最后输出)解析：24.在二叉链表表示的二叉树中，增设一个指针域，初值为空，试给出算法在不使用堆栈又不破坏原二叉树的情况下，前序遍历该二叉树。【北京邮电大学 2004 五、2(15 分)】（分数：2.00）_正确答案：(正确答案：将空指针(下面的 pre)域改成指向双亲(或祖先)。核心语句段如下： while(t) t 初值是二叉树根结点的指针 while(t) cohtpre=f； 指向双亲

14、，初值 f=null f=t；t=t 一lchild； 沿左侧向下 t=f； 回退 while(t&t 一rchild=null) t=t 一pre； 回返 if(t&t 一rchild) f=t 一pre； 避免从右侧返回时，再重复访问左侧 t=t 一rchild； 右转 )解析：25.对于二叉树的链接实现，完成非递归的中序遍历过程。【中山大学 1999 五、2(15 分)】（分数：2.00）_正确答案：(正确答案：wh51e(p top0) p 是二叉树指针，top 是栈顶指针，初值为 0 while(p) s+top=p；p=p 一lchild；) 沿左子树向下 if(top)0) p=

15、stop 一；coutrchild；)退栈，访问，转右子树 )解析：26.已知二叉树用下面的顺序存储结构，写出中序遍历该二叉树的算法。 （分数：2.00）_正确答案：(正确答案：二叉树用顺序方式存储，其遍历方法与用二叉链表方式存储类似。0 表示空指针。顺序存储方式下，要告诉根结点的下标。 void InOrder(int i) 对顺序存储的二叉树进行中序遍历，i 是根结点的下标 if(i!=0) InOrder(ariLc)； 中序遍历左子树 cout解析：27.试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 二、2(8 分)】（分数：2.00）_正确答案：(正确答案：设一队列 Q 和栈 S。将根结点入队。当队列不空，做如下操作：Q 出队；出队元素入栈 S；出队结点的非空左、右子女依次入队 Q。队列空后，弹出栈 S 中元素即为所求。)解析：