1、全国自考数据结构导论（二叉树）模拟试卷 1 及答案与解析一、单项选择题1 已知一棵高度为 5 的二叉树，则该二叉树的其结点总数为_。（A）617（B） 516（C） 632（D）5312 按照二叉树的定义，具有 4 个结点的二叉树共有_种。（A）5（B） 10（C） 12（D）143 已知一棵满二叉树有 47 个结点，则该二叉树有_个叶子结点。（A）6（B） 12（C） 24（D）484 若一棵二叉树有 12 个度为 0 的结点，6 个度为 1 的结点，则有_个度为 2的结点。（A）5（B） 7（C） 11（D）185 具有 16 个结点的满二叉树，其高度为_。（A）3（B） 4（C） 5（D
2、）66 二叉排序树根结点的左子树中所有结点关键字值_右子树中所有结点的关键字值。（A）小于（B）等于（C）大于等于（D）大于7 在下列存储结构中，属于二叉树存储结构的是_。（A）三叉链表（B）孩子兄弟链式存储结构（C）双亲存储结构（D）孩子链式存储结构8 对下图所示的一棵二叉树进行遍历，得到的遍历序列为 CADGEFB，则该遍历序列是_的结果。（A）前序遍历（B）中序遍历（C）后序遍历（D）层次遍历9 已知一棵二叉树的前序遍历序列与中序遍历序列相同，则该二叉树是_。（A）左单支树（B）右单支树（C）完全二叉树（D）满二叉树10 具有 n 个结点的线索二叉树上，含有_个线索。（A）n1（B） n
3、（C） n+1（D）011 若对图中所示的二叉树进行中序线索化，则结点 D 的左右线索域的指针分别指向_结点。（A）C，E（B） A，E（C） C，G（D）A。G12 分别用下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是_。（A）100 ， 70，40，90，140，150，110（B） 100，70，90，40，140，110，150（C） 100，140，110，150，70，40，90（D）100 ， 40，70，90，140，110，15013 有 n 个叶子的哈夫曼树的结点总数为_个。（A）n（B） 2n（C） 2n1（D）2n+114 以下图中，哪个是哈夫曼树_。二、
4、填空题15 若一棵完全二叉树的结点个数为 10，则编号最大的分支结点的编号为_。16 已知采用二叉链表作为存储结构的一棵二叉树共有 10 个结点，则二叉链表中共有_个指针域。17 一棵具有 10 个结点的二叉树共有 5 个叶结点，则该二叉树有_个度为 2的结点，_个度为 1 的结点。18 一棵具有 31 个结点的满二叉树，它的高度是_，共有_个叶结点。19 若二叉树的中序遍历序列与后序遍历序列相同，则该二叉树一定满足_。20 一棵二叉树的中序遍历序列为 CAEFDRB，后序遍历序列为 CFEDABR，则它的前序遍历序列为_。21 已知采用顺序存储结构的一棵二叉树，其存储映像为 则其前序遍历序列
5、为_。22 根据遍历方法不同，线索二叉树分为_、_和_。23 树的后序遍历序列与其对应二叉树的_遍历序列相同。24 若二叉树的右子树为空，则与其对应的森林有_棵树。25 在哈夫曼树中，权值校大的叶结点一定离根结点_。26 哈夫曼树不存在度为_的结点。27 若一个二叉树的叶子是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_序列中的最后一个结点。28 二叉树的先序序列和中序序列相同的条件是_。29 若以4 ， 5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。三、应用题30 画出一棵后序遍历序列与中序遍历序列相同的二叉树。31 已知二叉树的前序遍历序列 HACDFGBE
6、，中序遍历序列为 CAFDCHEB，请画出该二叉树，并给出后序遍历序列。32 如下图所示，给出表达式树的前序遍历序列、中序遍历序列和后序遍历序列。33 已知某密码电文由 5 个字母 A，B，C，D，E 组成，每个字母在电文中的出现频率分别是 12，7，21，8，6，请给出 5 个字母的哈夫曼编码。34 已知关键字序列为53，17，19，61，98，75，79，63，46，40 ，请给出利用这些关键字构造的二叉排序树。35 对如下图所示的二叉排序树，给出删除关键字 85 后的二叉排序树。36 具有 n 个结点的完全二叉树，顺序存储在一维数组 A1，z 中，设计算法将A 中顺序存储变为二叉链表存储
7、的二叉树。37 试编写出先序、中序和后序遍历的非递归算法。全国自考数据结构导论（二叉树）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 D【知识模块】 二叉树2 【正确答案】 D【知识模块】 二叉树3 【正确答案】 C【知识模块】 二叉树4 【正确答案】 C【知识模块】 二叉树5 【正确答案】 C【知识模块】 二叉树6 【正确答案】 A【知识模块】 二叉树7 【正确答案】 A【知识模块】 二叉树8 【正确答案】 B【知识模块】 二叉树9 【正确答案】 B【知识模块】 二叉树10 【正确答案】 C【知识模块】 二叉树11 【正确答案】 D【知识模块】 二叉树12 【正确答案】 D【知识模
8、块】 二叉树13 【正确答案】 C【试题解析】 由于在哈夫曼树中只有度为 2 和度为 0 的结点，由二叉树的性质可得 n2=n0-1，而叶子树为 n，所以哈夫曼树的结点总数为 2n 一 1，因此选 C。【知识模块】 二叉树14 【正确答案】 B【知识模块】 二叉树二、填空题15 【正确答案】 5【知识模块】 二叉树16 【正确答案】 20【知识模块】 二叉树17 【正确答案】 4 1【知识模块】 二叉树18 【正确答案】 5 16【知识模块】 二叉树19 【正确答案】 任何结点都没有右子树【知识模块】 二叉树20 【正确答案】 RACDEFB【知识模块】 二叉树21 【正确答案】 FACEBD
9、【知识模块】 二叉树22 【正确答案】 前序线索二叉树 中序线索二叉树 后序线索二叉树【知识模块】 二叉树23 【正确答案】 中序【知识模块】 二叉树24 【正确答案】 1【知识模块】 二叉树25 【正确答案】 较近【知识模块】 二叉树26 【正确答案】 1【知识模块】 二叉树27 【正确答案】 先序遍历【知识模块】 二叉树28 【正确答案】 左子树为空的单支树【知识模块】 二叉树29 【正确答案】 69【知识模块】 二叉树三、应用题30 【正确答案】 【知识模块】 二叉树31 【正确答案】 后序遍历序列为：CFGDAEBH【知识模块】 二叉树32 【正确答案】 前序遍历序列：一*+ABC+D
10、*EF中序遍历序列：(A+B)*C-(D+E*F)( 注：括号是人为加上的，表示计算的顺序 )后序遍历序列：AB+C*DEF*+一【知识模块】 二叉树33 【正确答案】 编码：A 一一 011 B001 C1 D一 010 E000【知识模块】 二叉树34 【正确答案】 【知识模块】 二叉树35 【正确答案】 【知识模块】 二叉树36 【正确答案】 voidCrerateB_t(BiTreeT 一data=Ai;if(2*iichild，2*i);elseT 一1child=NULL；if(2*i+1rchild ，2*i+1);elseT 一rchild=NULL;在该算法中，可以将数组 A
11、 设为全局变量。【试题解析】 遍历是二叉树各种操作的基础；可以利用遍历来建立二叉树。本题就是利用先序遍历，由顺序存储结构的完全二叉树建立起二叉链表存储结构的完全二叉树。顺序存储结构中，编号为 i 的结点的左孩子的编号为 2i，右孩子的编号为2i+1。【知识模块】 二叉树37 【正确答案】 (1)先序遍历。void PreOrderTraverse(BiTree bt) *二叉树 bt 采用二叉链表存储，对其进行先序遍历*if(bt) *二叉树非空*InitStack(S)；Push(S，bt)；while(!EmptyStack(S)while(GetTop(S，p)Pop(s，P);visit(P 一data);while(GetTop(s，q)一rchild=pvisit(P 一data);if(!EmptyStack(s)Push(s，GetTop(s，P)一rchild);【试题解析】 将一个递归算法转换成一个非递归算法，利用栈就可消除递归，根据对二叉树进行先序、中序和后序遍历的思想，其非递归算法描述如下。【知识模块】 二叉树
