计算机专业基础综合数据结构（树与二叉树）-试卷1
(总分：62.00，做题时间：90分钟)
一、 单项选择题(总题数：23，分数：46.00)
1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
__________________________________________________________________________________________
2.在下面关于树的相关概念的叙述中，正确的是( )。
 A.只有一个结点的二叉树的度为1
 B.二叉树的度一定为2
 C.二叉树的左右子树可任意交换
 D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树 √
只有一个结点的二叉树的度为零。二叉树的度可以为0、1、2；二叉树的左右子树不能任意交换。
3.已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为( )。
 A.一A+B*C／DE
 B.一A+B*CD／E
 C.一+*ABC／DE
 D.一+A*BC／DE √
根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)一D／E，前缀表达式：一+A*BC／DE。
4.算术表达式a+b*(c+d／e)转为后缀表达式后为( )。
 A.ab+cde／*
 B.abcde／+*+ √
 C.abcde／*++
 D.abcde*／++
根据表达式a+b*(c+d／e)可知其后缀表达式为abcde／+*+。
5.某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是( )。
 A.JLKMNOI
 B.LKNJOMI
 C.LKJNOMI √
 D.LKNOJMI
由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。由此图可以确
认后序遍历的序列为LKJNOMI。
6.设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是( )。
 A.m-n √
 B.m一n—1
 C.n+1
 D.条件不足，无法确定
F对应的二叉树共有m个结点，右子树上n个，左子树上有(m—n一1)个，第一株树包括根和左子树，共(m一n)个。
7.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是( )。
 A.先序遍历二叉树
 B.判断两个指定位置的结点是否在同一层上 √
 C.层次遍历二叉树
 D.根据结点的值查其存储位置
选项A、C、D运算的时间复杂度都是O(n)，而选项B的运算的时间复杂度为O(1)，因为对于指定位置p和q的两个结点，判断是否在同一层上，只需判断两者［log 2 p]=[log 2 q]是否成立。
8.设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为( )。
 A.188
 B.200
 C.199 √
 D.201
除根结点层只有1个结点外，其他各层均有两个结点，结点总数=2×(100一1)+1=199。
9.树是结点的有限集合，一棵树中有( )根结点。
 A.有0个或1个
 B.有0个或多个
 C.有且只有一个 √
 D.有1个或1个以上
根据树的基本定义可知，每个树只能有且只有一个根结点。
10.下列二叉排序树中，满足平衡二叉树定义的是( )。
 A.
 B. √
 C.
 D.
考查平衡二叉树的定义。 根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个选项均可以到不符合的结点。
11.把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。设T是一棵二叉树，K i 和K j 是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λK i 和λK j ，当关系式|λK i 一λK j |≤1一定成立时，则称T为一棵( )。
 A.满二叉树
 B.二叉查树
 C.平衡二叉树 √
 D.完全二叉树
此题干的叙述符合平衡二又树的定义。
12.设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M 1 、M 2 和M 3 。与森林F对应的二叉树根结点的右子树上的结点个数是( )。
 A.M 1
 B.M 1 +M 2
 C.M 3
 D.M 2 +M 3 √
森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为M2+M3。
13.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。
 A.10
 B.11 √
 C.16
 D.不确定
根据二叉树的性质可知，度为0的结点个数比度为2结点个数多一个，即n 0 =n 2 +1。
14.具有10个叶结点的二叉树中有( )个度为2的结点。
 A.8
 B.9 √
 C.10
 D.11
根据二叉树的性质n 0 =n 2 +1，可知度为2的结点个数为9。
15.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为O的结点数为( )个。
 A.4
 B.5
 C.6 √
 D.7
一棵度为3的树，总结点数n=n 0 +n 1 +n 2 +n 3 ，而总分支总数为n 0 ×0+n 1 ×2+n 2 ×1+n 3 ×2，由于分支总数加1为结点总数，可得出n 0 =6。
16.已知一棵二叉树，共有n个结点，那么此二叉树的高度为( )。
 A.nlog 2 n
 B.log 2 n
 C.[log 2 n]+1
 D.不确定 √
已知一棵二叉树共有n个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。
17.已知一棵二叉树，第m层上最多含有结点数为( )。
 A.2 m
 B.2 m-1 一1
 C.2 m-1 √
 D.2 m 一1
根据二叉树的性质，二叉树的第m层上最多有2 m-1 。
18.有关二叉树下列说法正确的是( )。
 A.二叉树就是度为2的树
 B.一棵二又树的度可以小于2 √
 C.二叉树中至少有一个结点的度为2
 D.二叉树中任何一个结点的度都为2
本题考查二又树的概念。
19.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( )。
 A.CABDEFG
 B.ABCDEFG √
 C.DACEFBG
 D.BAECFDG
由题可得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……。
20.已知一个二叉树有1025个结点，那么由此推断二叉树的高h为( )。
 A.11
 B.10
 C.11一1025 √
 D.10～1024
右完全二叉树中1025＞2 10 ，即最少需要11层，最多需要有1025层。
21.一棵完全二叉树，共有n个结点，那么，其叶结点数共有( )个。
 A.n／2
 B.n
 C.(n-1)／2
 D.(n+1)／2 √
此问题可以利用二叉树及完全二叉树的性质来求解。 设i、j、k分别为度为0、1、2的结点数目，则n=i+j+k。 根据二叉树的性质有i=k+1，即k=i一1，代入上式，得n=2i+j—1，即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。
22.( )的遍历仍需要栈的支持。
 A.前序线索树
 B.中序线索树
 C.后序线索树 √
 D.中序线索树和前序线索树
由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进行遍历。
23.已知一棵二叉树高度为h，在此二叉树中只有度为0和度为2的结点，那么这棵二叉树的结点个数最少为( )。
 A.2h
 B.2h一1 √
 C.2h+1
 D.h+1
二、 综合应用题(总题数：8，分数：16.00)
二叉树公式
24.综合应用题41-47小题。
__________________________________________________________________________________________
25.已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。
__________________________________________________________________________________________
正确答案：(正确答案：二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下： BiTree Creat(){ ／／建立二叉树的二叉链表形式的存储结构 ElemType X； BiTree bt； scanf(”％dIt，&x); ／／本题假定结点数据域为整型 if(x==0)bt=null： else if(x＞0){ bt=(BiNode*)malloc(sizeof(BiNode))； bt一＞data=x： bt一＞lchild=Creat()； bt一＞rchild=Creat()； } else error(”输入错误”)； return(bt)； }／／结束BiTree)
26.判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。
__________________________________________________________________________________________
正确答案：(正确答案：判断此二叉树是否为完全二叉树的算法设计如下： int JudgeComplete(BiTree bt){ ／／判断二叉树是否是完全二叉树，如是，返回1；否则，返回0 int tag=0； BiTree P=bt，Q[]； ／／Q是队列，元素是二叉树结点指针，容量足够大 if(p==null)return 1； QueueInit(Q)： QueueIn(Q，P)； ／／初始化队列，根结点指针入队 while(!QueueEmpty(Q)){ P=QueueOut(Q)； ／／出队 if(p一＞lchild&&!tag)Queueln(Q，P-＞lchild)； ／／左孩子入队 else{ if(P一＞lchild)return 0： ／／前边已有结点为空，本结点不空 else tag=1； ／／首次出现结点为空 if(p一＞rchild&&!tag)Queueln(Q，P-＞rchild)：
／／右孩子入队 else if(p一＞rchild)return 0； else tag=1； } }／／while return 1； }／／Judgecomplete)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。