《计算机专业基础综合数据结构历年真题试卷汇编8》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构历年真题试卷汇编8（4页珍藏版）》请在金锄头文库上搜索。
1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编8（总分：66.00，做题时间：90分钟）一、填空题（总题数：22，分数：44.00）1. 设一棵完全二叉树叶子结点数为k，最后一层结点数2，则该二叉树的高度为。【北京科技 大学1998 一、3】正确答案：（正确答案：dog 2 k+1）2. 巳知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是。【东南大学 2005数据结构部分二、7（1分）】 正确答案：（正确答案：235。参见上面一、2的分析。）3. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编 号为0，则编号为50的结点的
2、右孩子编号为。【中南大学2005二、l（2分）】正确答案：（正确答案：102。假定编号为i的结点的左右孩子存在，左孩子的编号是2*i+1，右孩子的编 号是 2*i+2。）4. 高度为i（iN1）的完全二叉树最多有 个结点；最少有 个结点；若按自上而下，从左到右的次序给结点编号（从1开始），则编号最小的叶子结点的编号为。【大连理工大学 2005 一、2（3分）】【江苏大学2006二、3（2分）】 正确答案：（正确答案：（1）2 t -1 （2）2 i-1 （3）n/2+1（设n是完全二叉树的结点数）5. 对于一个具有n个结点的二叉树，当它为一棵（1）二叉树时具有最小高度，当它为一棵（2）时，具有
3、最大 高度。【哈尔滨工业大学2001 一、3（2分）】 正确答案：（正确答案：（1）完全（2）只有一个叶子结点的二叉树）6. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是（1）。它共有（2）个叶子结点和（39）个非叶 子结点，其中深度最大的那棵树的深度是（4），它共有（5）个叶子结点和（6）个非叶子结点。【山东大学 2001三、7（2分）】 正确答案：（正确答案：（1）2 （2）n 1 （3）1 （4）n （5）1 （6）n 一 1）7. 在树的孩子兄弟表示法中，二叉链表的左指针指向，右指针指向。【北京理工大 学2006十、3（1分）】 正确答案：（正确答案：（1）结点的第一个孩
4、子（2）结点的右兄弟）8. 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，巳知T1、T2、T3的结点数分别为 n1、n2和，n3，则二叉树B的左子树中有（1）个结点，右子树中有（2）个结点。【南京理工大学2000 二、9（3分）】 正确答案：（正确答案：（1）n1 1 （2）n2+n3）9. 先序遍历森林时，首先访问森林中第一棵树的。【中山大学2005】正确答案：（正确答案：根结点）10. 设森林F对应的二元树为B，它有m个结点，B的根为P，P的右子树结点个数为n，则森林，中第一 棵树的结点个数是。【哈尔滨工业大学2005 一、8（1分）】正确答案：（正确答案：m 一 n）1
5、1. 一个深度为七的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编 号，则编号最小的叶子的序号是（1）；编号是f的结点所在的层次号是（2）（根所在的层次号规定为1层）。【南京理工大学2001二、2（2分）】 正确答案：（正确答案：（1）2 I +1（第k层1个结点，总结点个数是2 k-1，其双亲是2 k-1 / 2=2 k-2 ）（2）log 2 i/+1本题（1）也可以这样分析：深度为k且具有最少结点数的完全二叉树，第k层只有一 个结点，第k-1层是满的，最左边的结点度为1，其右兄弟就是编号最小的叶子结点。而第k-2层最右边结点的编号是2 k-2 1。所以，最小叶
6、子结点的编号是（2 k-2 1）12. 将一棵结点编号（从上到下，从左至右）为1到7的满二叉树转变成森林，则中序遍历该森林得到的序 列为。【北京工业大学2005二、5（3分）】 正确答案：（正确答案：4, 2, 5，1，6, 3, 7。说明：题中“中序遍历该森林”多数教材使用“后序遍历 该森林”。）13. 每一棵树都能唯一地转换为它所对应的二叉树。若巳知一棵二叉树的前序序列是BEFCGDH，对称序列 是FEBGCHD，则它的后序序列是（1）。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是（2）。【山东工业大学1997 二 （6分）】 正确答案：（正确答案：（1）FEGHDCB （2）B
7、EF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF）14. 前序遍历树林正好等同于按（1）遍历对应的二叉树，后序遍历树林正好等同于按（2）遍历对应的二又 树。【山东工业大学1999二、1（4分）】 正确答案：（正确答案：（1）前序（2）中序）15. 二叉树的先序序列和中序序列相同的条件是。【合肥工业大学2000三、7（2分）】正确答案：（正确答案：任何结点至多只有右子女的二叉树）16. 已知一棵二叉树的前序序列为abdecfhg，中序序列为dbeahfcg，则该二叉树的根为（1），左子树中有（2），右子树中有（3）。【南京理工大学1996二、1（6分）】 正确答案：（正确答案：
8、（1）a （2）dbe （3）hfcg）17. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用“”表示，现前序 遍历二叉树，访问的结点的序列为ABDGCE. H. F.，则中序遍历二叉树时，访问的结点序列为（1）；后 序遍历二叉树时，访问的结点序列为（2）。【南京理工大学1999二、3（4分）】 正确答案：（正确答案：（1）.D.G.B.A.E.H.C.F （2）-GD.B-HE.FCA）18. 设某二叉树的先序遍历序列为abcdefgh，中序遍历序列为dgbaechf,，则其后序遍历序列为。【北京交通大学2006二、5（2分）】正确答案：（正确答案：gdbehfca）
9、19. 某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是。【中科院研 究生院2005二、6（1分）】【东南大学2005数据结构部分二、6（1分）】 正确答案：（正确答案：cedba）20. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女， 则这个结点在后序遍历中的后继结点是。【中国人民大学2001 一、4（2分）】 正确答案：（正确答案：双亲的右子树中最左下的叶子结点）21. 一棵左子树为空的二又树在先序线索化后，其中的空链域的个数为。【厦门大学2002六、 1（4分）】 正确答案：（正确答案：2）22. 设一棵后序线索树的高
10、是50，结点x是树中的一个结点，其双亲是结点y，y的右子树高度是3l，x 是y的左孩子。则确定x的后继最多需经过 中间结点（不含后继及x本身）。【南京理工大学2000 二、8（1. 5 分）】 正确答案：（正确答案：31（x的后继是经x的双亲y的右子树中最左下的叶结点）二、综合题（总题数：8,分数：22.00）23. 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什 么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件二、1（5分）】 正确答案：（正确答案：树的孩子兄弟链表表示法和二叉树二叉链表表示法本质上是一样的，只是解释不 同，也就是说，树（
11、树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二 叉树的一些算法去解决树和森林的问题。树和二又树均属于树形结构，其区别有三：一是二叉树的度至多 为2,树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树 还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（一些教材上考虑到与二叉树的转 换，允许树为空）。二叉树不是树的特例。）24. 请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。【大连海事大学2001三（10 分）】 正确答案：（正确答案：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，
12、也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有 唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无 双亲），从这个意义上说，存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子 表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非 线性结构。但在以下意义上，又蜕变为线性结构：度为1的树，以及广义表中的元素都是原子时。另外， 广义表中同层（最高层是用逗号分隔的）元素之间的关系可看成前驱和后继，也符合线性表中元素间的逻辑 关系，但这时元素有原子，也有子
13、表，即元素并不属于同一数据对象。）25. 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？【中国人民大学2001二、3（4 分）】 正确答案：（正确答案：方法有二。一是对该算术表达式（二叉树）进行后序遍历，得到表达式的后序遍历 序列，即后缀表达式，可对其求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最 后按根结点运算符（+、一、*、/等）进行最后求值。）26. 将算术表达式（a+b）+c * （d+e）+f） * （g+h）转化为二叉树。【天津大学2003 一、3（8分）】【东南大 学2003二（7分）】【东北大学2000三、1（4分）】N正确答案：（正确答案：
14、该算术表达式转化的二叉树如右图所示。27. 试分别画出表示下列两个表达式的二叉树。【华中科技大学2006三、1（6分）】（1）a 一 b+c （2）a+（bc) / d一e*f 正确答案：（正确答案：人们日常使用的表达式是中缀表达式，由于存在括号和运算符的优先级，直接转 换成表达式二叉树比较困难。最好的办法是先将中缀表达式转换成后缀表达式，转换规则巳在第3章的应 用题部分的第21题做了介绍，读者可参照。由后缀表达式转换成表达式二叉树的规则如下。从左到右读 入后缀表达式，遇操作数就入栈，遇操作符就将该操作符做当前的根结点，并从栈内弹出两个操作数，后 弹出的是第一操作数（被乘/除/加/减数）做左子
15、树，先弹出的做右子树，之后将该根结点入栈。继续读 后缀表达式，如上处理，直至表达式结束。限于篇幅，表达式的二又树不再画出。）28. 已知树的广义表表示如下T=（A（B（E（K,L），C（G），D（H（M）,I,J），画出该广义表所对应的树。【天津 大学2006 二 （10分）】 正确答案：（正确答案：树的广义表表示法的特点如下：树是一个广义表，若括号内无元素，则为空树； 若广义表是非空表，则表内第一个元素是树的根。第一个元素后是表，若表内为空，则无子树；否则高层 以逗号分隔的是互为兄弟的子树。对每棵子树，进行如上分解，最后得到广义表对应的子树。）29. 一棵二叉树中的结点的度或为0或为2,则二
16、叉树的枝数为2（n0 1），其中n0是度为0的结点的个 数。【南京理工大学1998六（3分）】 正确答案：（正确答案：证明：设二叉树度为0和2的结点数及总的结点数分别为n0、n2和n，则 n=n0+n2 （1）再设二叉树的分支数为B，除根结点外，每个结点都有一个分支所指，则n=B 1 （2）度 为0的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为n=2*n2+1 （3）由（1）、（3）得 n2=n0-1，代入（1），并由（1）和（2）得 B=2*（n0 1）。证毕。）一棵高度为h的满k叉树有如下性质：根结点所在层次为0；第h层上的结点都是叶子结点；其余各层上 每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编 号，试问：（分数：8.00）（1）.各层的
