1、计算机专业基础综合（数据结构）模拟试卷 3 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在下面关于树的相关概念的叙述中，正确的是( )。（A）只有一个结点的二叉树的度为 1（B）二叉树的度一定为 2（C）二叉树的左右子树可任意交换（D）深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树2 已知一算术表达式的中缀形式为 A+B*C-DE，后缀形式为 ABC*+DE一，其前缀形式为( ) 。（A）一 A+B*CDE（B）一 A+B*CDE（C） -+*ABCDE（D）-+A*BC DE3 算术表达
2、式 a+b*(c+d e)转为后缀表达式后为( ) 。（A）ab+cde*（B） abcde+*+（C） abcde*+（D）abcde* +4 某二叉树的先序遍历序列为 IJKLMNO，中序遍历序列为 JLKINMO，则后序遍历序列是( )。（A）JLKMNOI（B） LKNJOMI（C） LKJNOMI（D）LKNOJMI5 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 P，P 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是 ( )。（A）m-n（B） m-n-1（C） n+1（D）条件不足，无法确定6 二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的
3、是( )。（A）先序遍历二叉树（B）判断两个指定位置的结点是否在同一层上（C）层次遍历二叉树（D）根据结点的值查找其存储位置7 设某二叉树中只有度为 0 和度为 2 的结点，如果此二叉树的高度为 100，那么此二叉树中所包含的结点数最少为( )。（A）188（B） 200（C） 199（D）2018 树是结点的有限集合，一棵树中有( )根结点。（A）有 0 个或 1 个（B）有 0 个或多个（C）有且只有一个（D）有 1 个或 1 个以上9 下列二叉排序树中，满足平衡二叉树定义的是( )。10 把树的根结点的层数定义为 1，其他结点的层数等于其父结点所在层数加上 I。设 T 是一棵二叉树，K
4、i 和 Kj 是 T 中子结点数小于 2 的结点中的任意两个，它们所在的层数分别为 Ki 和 Kj，当关系式|K i 一 Kj|1一定成立时，则称 T 为一棵( ) 。（A）满二叉树（B）二叉查找树（C）平衡二叉树（D）完全二叉树11 设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1、M 2 和M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是( )。（A）M 1（B） M1+M2（C） M3（D）M 2+M312 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是( )。（A）10（B） 11（C） 16（D）不确定13 具
5、有 10 个叶结点的二叉树中有( )个度为 2 的结点。（A）8（B） 9（C） 10（D）1114 在一棵度为 3 的树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为1 的结点数为 2 个，则度为 O 的结点数为( )个。（A）4（B） 5（C） 6（D）715 已知一棵二叉树，共有 n 个结点，那么此二叉树的高度为( )。（A）nlog 2n（B） log2n（C） log2n+1（D）不确定16 已知一棵二叉树，第 m 层上最多含有结点数为 ( )。（A）2 m（B） 2m-1 一 1（C） 2m-1（D）2 m-117 有关二叉树下列说法正确的是( )。（A）二叉
6、树就是度为 2 的树（B）一棵二叉树的度可以小于 2（C）二叉树中至少有一个结点的度为 2（D）二叉树中任何一个结点的度都为 218 一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。（A）CABDEFG（B） ABCDEFG（C） DACEFBG（D）BAECFDG19 已知一个二叉树有 1025 个结点，那么由此推断二叉树的高 h 为( )。（A）11（B） 10（C） 111025（D）10102420 一棵完全二叉树，共有 n 个结点，那么，其叶结点数共有( )个。（A）n2（B） n（C） (n-1) 2（D）(n+1) 221 ( )的遍历仍需要栈的支持。（
7、A）前序线索树（B）中序线索树（C）后序线索树（D）中序线索树和前序线索树22 已知一棵二叉树高度为 h，在此二叉树中只有度为 0 和度为 2 的结点，那么这棵二叉树的结点个数最少为( )。（A）2h（B） 2h 一 1（C） 2h+1（D）h+1二、综合应用题41-47 小题，共 70 分。23 已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。24 判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。25 以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。26 已知一棵二叉树的前序序列为：A，B，D，G，J ，E ，H ，C，F，I，
8、K，L ；中序序列为：D，J，G，B，E，H，A，C，K，I，L，F。(1)写出该二又树的后序序列。(2)画出该二叉树。(3)求该二叉树的高度以及该二叉树中度为 2、1、0 的结点个数。27 有 n 个结点的二叉树，已知叶结点个数为 n0。 (1)写出求度为 1 的结点的个数的n1 的计算公式。 (2)若此树是深度为 k 的完全二叉树，写出 n 为最小的公式。 (3)若二叉树中仅有度为 0 和度为 2 的结点，写出求该二叉树结点个数 n 的公式。28 已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。29 在一棵表示有序集 S 的二叉搜索树 (binary search
9、tree)中，任意一条从根到叶结点的路径将 S 分为 3 部分：在该路径左边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素组成的集合S3。S=S 1S2S3。若对于任意的 aS1，b S2，c S3，是否总有 abc?为什么?计算机专业基础综合（数据结构）模拟试卷 3 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 只有一个结点的二叉树的度为零。二叉树的度可以为 0、1、2：二叉树的左右子树不能任意交换。【知识模块】 数据结构2 【
10、正确答案】 D【试题解析】 根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)一 DE，前缀表达式：-+A*BCDE。【知识模块】 数据结构3 【正确答案】 B【试题解析】 根据表达式 a+b*(c+de)可知其后缀表达式为 abcde+*+。【知识模块】 数据结构4 【正确答案】 C【试题解析】 由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。 由此图可以确认后序遍历的序列为LKJNOMI。【知识模块】 数据结构5 【正确答案】 A【试题解析】 F 对应的二叉树共有 m 个结点，右子树上 n 个，左子树上有(m 一n 一 1)个，第一株树包括根和左子树，
11、共(m 一 n)个。【知识模块】 数据结构6 【正确答案】 B【试题解析】 选项 A、C、D 运算的时间复杂度都是 O(n)，而选项 B 的运算的时间复杂度为 O(1)，因为对于指定位置 p 和 q 的两个结点，判断是否在同一层上，只需判断两者log 2p=log2q是否成立。【知识模块】 数据结构7 【正确答案】 C【试题解析】 除根结点层只有 1 个结点外，其他各层均有两个结点，结点总数=2(100 一 1)+1=199。【知识模块】 数据结构8 【正确答案】 C【试题解析】 根据树的基本定义可知，每个树只能有且只有一个根结点。【知识模块】 数据结构9 【正确答案】 B【试题解析】 考查平
12、衡二叉树的定义。根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过 1。而其余三个选项均可以找到不符合的结点。【知识模块】 数据结构10 【正确答案】 C【试题解析】 此题干的叙述符合平衡二叉树的定义。【知识模块】 数据结构11 【正确答案】 D【试题解析】 森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为 M2+M3。【知识模块】 数据结构12 【正确答案】 B【试题解析】 根据二叉树的性质可知，度为 0 的结点个数比度为 2 结点个数多一个，即 n0=n2+1。【知
13、识模块】 数据结构13 【正确答案】 B【试题解析】 根据二叉树的性质 n0=n2+1，可知度为 2 的结点个数为 9。【知识模块】 数据结构14 【正确答案】 C【试题解析】 一棵度为 3 的树，总结点数 n=n0+n1+n2+n3，而总分支总数为n00+n12+n21+n32，由于分支总数加 1 为结点总数，可得出 n0=6。【知识模块】 数据结构15 【正确答案】 D【试题解析】 已知一棵二叉树共有 n 个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。【知识模块】 数据结构16 【正确答案】 C【试题解析】 根据二叉树的性质，二叉树的第 m 层上最多有 2m-1。【知识模块】
14、 数据结构17 【正确答案】 B【试题解析】 本题考查二叉树的概念。【知识模块】 数据结构18 【正确答案】 B【试题解析】 由题可得 A 为根结点，并且 B 为 A 的孩子结点。选项 A，C 应为A 的左孩子，其前序序列应为 AC。选项 B，当 B 为 A 的右孩子，C 为 B 的右孩子时，满足题目要求。选项 C，类似选项 A，其前序序列应为 AD。选项D，B 为 A 的左孩子，C 为 A 的右子树的根，E 为 C 的左子树，FDG 为 C 的右子树，其前序序列应为 ABEC。【知识模块】 数据结构19 【正确答案】 C【试题解析】 右完全二叉树中 10252 10，即最少需要 11 层，最
15、多需要有 1025 层。【知识模块】 数据结构20 【正确答案】 D【试题解析】 此问题可以利用二叉树及完全二叉树的性质来求解。设 i、j 、k 分别为度为 0、1、2 的结点数目，则 n=i+j+k。根据二叉树的性质有 i=k+1，即 k=i 一 1，代入上式，得 n=2i+j1，即 i=(n-j+1)2。由于完全二又树中最多只有一个度为 1 的结点，同时考虑到 i 为整数，(1)当 j=0 时，此时 n=i+k=2k+1 为奇数，则 i=(n+1)2；(2)当 j=1 时，此时 n=i+k+1=2k+2 为偶数，则 i=(n+1)2 向下取整。所以选 D。【知识模块】 数据结构21 【正确
16、答案】 C【试题解析】 由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进行遍历。【知识模块】 数据结构22 【正确答案】 B【知识模块】 数据结构二、综合应用题41-47 小题，共 70 分。23 【正确答案】 二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下：BiTree Creat() 建立二叉树的二叉链表形式的存储结构ElemType x：BiTree bt；scanf(”d” ，&x) ； 本题假定结点数据域为整型if(x=0)bt=null；else if(x0)bt=(BiNode*)m
17、alloc(sizeof(BiNode)；bt 一data=x ：bt 一lchild=Creat()；bt 一rchild=Creat()：else error(”输入错误”)；return(bt)；结束 BiTree【知识模块】 数据结构24 【正确答案】 判断此二又树是否为完全二叉树的算法设计如下：int JudgeComplete(BiTree bt)判断二叉树是否是完全二叉树，如是，返回 1；否则，返回 0int tag=0；BiTree P=bt，Q ： Q 是队列，元素是二叉树结点指针，容量足够大if(P=null)return 1：QueueInit(Q)；Queueln(Q，
18、P)； 初始化队列，根结点指针入队while(!QueueEmpty(Q)P=QueueOut(Q)： 出队if(p 一lchild&!tag)QueueIn(Q ，P 一lchild)； 左孩子入队elseif(P 一lehild)retum 0： 前边已有结点为空，本结点不空else tag=1； 首次出现结点为空if(p 一rchild&!tag)Queueln(Q ，P 一rchild)； 右孩子入队else if(p 一 rchild)return 0；else tag=1： whilereturn 1； JudgeComplete【知识模块】 数据结构25 【正确答案】 当森林(树
19、)以孩子兄弟表示法存储时，若结点没有孩子(fch=null)，则它必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟(nsib)子树上叶结点个数之和。typedef struct nodeelemType data； 数据域struct node *fch，*nsib； 孩子与兄弟域*Tree；int Leaves(Tree t) 计算以孩子一兄弟表示法存储的森林的叶子数if(t)if(t 一fch=：null) 若结点无孩子，则该结点必是叶子return(1+Leaves(t-nsib)； 返回叶子结点和其兄弟子树中的叶子结点数else return(Leaves(t-fch)+
20、Leaves(t-nsib)； 孩子子树和兄弟子树中叶子数之和【知识模块】 数据结构26 【正确答案】 此题只需从前序序列、中序序列得到唯一确定的二叉树即可。(1)J，G，D，H，E，B，K，L，I，F，C，A。(2)二叉树的形式如下图所示：(3)高度是 5，度为 0 的结点个数为 4，度为 1 的结点个数为 5，度为 2 的结点个数为 3。【知识模块】 数据结构27 【正确答案】 (1)设度为 2 的结点个数为 n2，则 n=n0+n1+n2。由二叉树的性质n0=n2+1，n=2n 0+n1 一 1，所以度为 1 的结点的个数 n1=n+1 一 2n0； (2)当树是深度为 k 的完全二叉树
21、时，n 的最小值 min(n)=2k-1。 (3) 当二叉树中只有度为 0 和度为2 的结点时，n=2n 0 一 1(其中 n 为树中的总结点数，n 0 为度为 0 的结点数目)。【知识模块】 数据结构28 【正确答案】 相应的树如下图所示： 树到二叉树的转换规则如下： (1)树的根结点为二叉树的根结点； (2)每个结点的第一个子结点(最左的子树) 作为该结点的左孩子； (3)每个结点的右孩子为在树中与该结点的左孩子邻近的兄弟，所有具有兄弟关系的结点用指针链接起来。 转换成二叉树如下图所示：【知识模块】 数据结构29 【正确答案】 不是。如下图所示的二叉搜索树：取从 4 到 12 的路径，则 S1=1，2，3，7，S2=4，8，10 ，12，S 3 为空集，取 S1 中的元素 7 和 S2 中的元素 4，令a=7，b=4，有 ab。则上述命题不成立。【知识模块】 数据结构
