【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc

上传人:livefirmly316 文档编号:1389697 上传时间:2019-12-03 格式:DOC 页数:10 大小:69.50KB
下载 相关 举报
【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc_第1页
第1页 / 共10页
【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc_第2页
第2页 / 共10页
【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc_第3页
第3页 / 共10页
【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc_第4页
第4页 / 共10页
【考研类试卷】计算机专业基础综合(树与二叉树)-试卷1及答案解析.doc_第5页
第5页 / 共10页
点击查看更多>>
资源描述

1、计算机专业基础综合(树与二叉树)-试卷 1及答案解析(总分:68.00,做题时间:90 分钟)一、单项选择题(总题数:23,分数:46.00)1.单项选择题 1-40小题。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。(分数:2.00)_2.在下面关于树的相关概念的叙述中,正确的是( )。(分数:2.00)A.只有一个结点的二叉树的度为 1B.二叉树的度一定为 2C.二叉树的左右子树可任意交换D.深度为 K的完全二又树的结点个数小于或等于深度相同的满二叉树3.已知一算术表达式的中缀形式为 A+B*C-DE,后缀形式为 ABC*+DE-,其前缀形式为( )。(分数:2.00)A.一

2、A+B*CDEB.一 A+B*CDEC.一+*ABCDED.一+A*BCDE4.算术表达式 a+b*(c+de)转为后缀表达式后为( )。(分数:2.00)A.ab+cde*B.abcde+*+C.abcde*+D.abcde*+5.某二叉树的先序遍历序列为 IJKLMNO,中序遍历序列为 JLKINMO,则后序遍历序列是( )。(分数:2.00)A.JLKMNOIB.LKNJOMIC.LKJNOMID.LKNOJMI6.设森林 F对应的二叉树为 B,它有 m个结点,B 的根为 P,P 的右子树结点个数为 n,森林 F中第一棵树的结点个数是( )。(分数:2.00)A.m-nB.m-n-1C.

3、n+1D.条件不足,无法确定7.二叉树若用顺序方法存储,则下列四种算法中运算时间复杂度最小的是( )。(分数:2.00)A.先序遍历二叉树B.判断两个指定位置的结点是否在同一层上C.层次遍历二叉树D.根据结点的值查找其存储位置8.设某二叉树中只有度为 0和度为 2的结点,如果此二叉树的高度为 100,那么此二叉树中所包含的结点数最少为( )。(分数:2.00)A.188B.200C.199D.2019.树是结点的有限集合,一棵树中有( )根结点。(分数:2.00)A.有 0个或 1个B.有 0个或多个C.有且只有一个D.有 1个或 1个以上10.下列二叉排序树中,满足平衡二叉树定义的是( )。

4、 (分数:2.00)A.B.C.D.11.把树的根结点的层数定义为 1,其他结点的层数等于其父结点所在层数加上 1。设 T是一棵二叉树,K i 和 K j 是 T中子结点数小于 2的结点中的任意两个,它们所在的层数分别为 K i 和 K j ,当关系式K i -K j 1 一定成立时,则称 T为一棵( )。(分数:2.00)A.满二叉树B.二叉查找树C.平衡二叉树D.完全二叉树12.设森林 F中有三棵树,第一、第二、第三棵树的结点个数分别为 M 1 、M 2 和 M 3 。与森林 F对应的二叉树根结点的右子树上的结点个数是( )。(分数:2.00)A.M 1B.M 1 +M 2C.M 3D.M

5、 2 +M 313.若一棵二叉树具有 10个度为 2的结点,5 个度为 1的结点,则度为 0的结点个数是( )。(分数:2.00)A.10B.11C.16D.不确定14.具有 10个叶结点的二叉树中有( )个度为 2的结点。(分数:2.00)A.8B.9C.10D.1115.在一棵度为 3的树中,度为 3的结点数为 2个,度为 2的结点数为 1个,度为 1的结点数为 2个,则度为 0的结点数为( )个。(分数:2.00)A.4B.5C.6D.716.已知一棵二叉树,共有 n个结点,那么此二叉树的高度为( )。(分数:2.00)A.nlog 2 nB.log 2 nC.log 2 n+1D.不确

6、定17.已知一棵二叉树,第 m层上最多含有结点数为( )。(分数:2.00)A.2 mB.2 m-1 一 1C.2 m-1D.2 m 一 118.有关二叉树下列说法正确的是( )。(分数:2.00)A.二叉树就是度为 2的树B.一棵二叉树的度可以小于 2C.二叉树中至少有一个结点的度为 2D.二叉树中任何一个结点的度都为 219.一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是( )。(分数:2.00)A.CABDEFGB.ABCDEFGC.DACEFBGD.BAECFDG20.已知一个二叉树有 1025个结点,那么由此推断二叉树的高 h为( )。(分数:2.00)A.11B

7、.10C.111025D.10102421.一棵完全二叉树,共有 n个结点,那么,其叶结点数共有( )个。(分数:2.00)A.n2B.nC.(n-1)2D.(n+1)222.( )的遍历仍需要栈的支持。(分数:2.00)A.前序线索树B.中序线索树C.后序线索树D.中序线索树和前序线索树23.已知一棵二叉树高度为,在此二叉树中只有度为 0和度为 2的结点,那么这棵二叉树的结点个数最少为( )。(分数:2.00)A.2hB.2h-1C.2h+1D.h+l二、综合应用题(总题数:8,分数:22.00)24.综合应用题 41-47小题。_25.已知一个二叉树,用二叉链表形式存储,给出此二叉树建立过

8、程算法(可不描述结构体)。(分数:2.00)_26.判别给定的二叉树是否是完全二叉树,并给出设计的算法(可不描述结构体)。(分数:2.00)_27.以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。(分数:2.00)_已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L;中序序列为:D,J,G,B,E,H,A,C,K,I,L,F。(分数:6.00)(1).写出该二叉树的后序序列。(分数:2.00)_(2).画出该二叉树。(分数:2.00)_(3).求该二叉树的高度以及该二叉树中度为 2、1、0 的结点个数。(分数:2.00)_有 n个结点的二叉树,已知叶结点个数为

9、 n。(分数:6.00)(1).写出求度为 1的结点的个数的 n 1 的计算公式。(分数:2.00)_(2).若此树是深度为 k的完全二叉树,写出 n为最小的公式。(分数:2.00)_(3).若二叉树中仅有度为 0和度为 2的结点,写出求该二叉树结点个数 n的公式。(分数:2.00)_28.已知一棵树的结点表示如下,其中各兄弟结点是依次出现的,画出对应的二叉树。 (分数:2.00)_29.在一棵表示有序集 S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将 s分为3部分:在该路径左边结点中的元素组成的集合 S 1 ;在该路径上的结点中的元素组成的集合 S 2

10、 ;在该路径右边结点中的元素组成的集合 S 3 。S=S 1 S 2 S 3 。若对于任意的 aS 1 ,bS 2 ,cS 3 ,是否总有 abc?为什么?(分数:2.00)_计算机专业基础综合(树与二叉树)-试卷 1答案解析(总分:68.00,做题时间:90 分钟)一、单项选择题(总题数:23,分数:46.00)1.单项选择题 1-40小题。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。(分数:2.00)_解析:2.在下面关于树的相关概念的叙述中,正确的是( )。(分数:2.00)A.只有一个结点的二叉树的度为 1B.二叉树的度一定为 2C.二叉树的左右子树可任意交换D.深度为

11、K的完全二又树的结点个数小于或等于深度相同的满二叉树 解析:解析:只有一个结点的二叉树的度为零。二叉树的度可以为 0、1、2;二叉树的左右子树不能任意交换。3.已知一算术表达式的中缀形式为 A+B*C-DE,后缀形式为 ABC*+DE-,其前缀形式为( )。(分数:2.00)A.一 A+B*CDEB.一 A+B*CDEC.一+*ABCDED.一+A*BCDE 解析:解析:根据题目给出的中缀和后缀表达式可以得到其算术表达式为:(A+B*C)一 DE,前缀表达式:一+A*BCDE。4.算术表达式 a+b*(c+de)转为后缀表达式后为( )。(分数:2.00)A.ab+cde*B.abcde+*+

12、 C.abcde*+D.abcde*+解析:解析:根据表达式 a+b*(c+de)可知其后缀表达式为 abcde+*+。5.某二叉树的先序遍历序列为 IJKLMNO,中序遍历序列为 JLKINMO,则后序遍历序列是( )。(分数:2.00)A.JLKMNOIB.LKNJOMIC.LKJNOMI D.LKNOJMI解析:解析:由先序和中序遍历序列确定一棵二叉树,再给出这棵二叉树的后序遍历序列。6.设森林 F对应的二叉树为 B,它有 m个结点,B 的根为 P,P 的右子树结点个数为 n,森林 F中第一棵树的结点个数是( )。(分数:2.00)A.m-n B.m-n-1C.n+1D.条件不足,无法确

13、定解析:解析:F 对应的二叉树共有 m个结点,右子树上 n个,左子树上有(mn 一 1)个,第一株树包括根和左子树,共(mn)个。7.二叉树若用顺序方法存储,则下列四种算法中运算时间复杂度最小的是( )。(分数:2.00)A.先序遍历二叉树B.判断两个指定位置的结点是否在同一层上 C.层次遍历二叉树D.根据结点的值查找其存储位置解析:解析:选项 A、C、D 运算的时间复杂度都是 O(n),而选项 B的运算的时间复杂度为 O(1),因为对于指定位置 p和 q的两个结点,判断是否在同一层上,只需判断两者log 2 p=log 2 q是否成立。8.设某二叉树中只有度为 0和度为 2的结点,如果此二叉

14、树的高度为 100,那么此二叉树中所包含的结点数最少为( )。(分数:2.00)A.188B.200C.199 D.201解析:解析:除根结点层只有 1个结点外,其他各层均有两个结点,结点总数=2(1001)+l=199。9.树是结点的有限集合,一棵树中有( )根结点。(分数:2.00)A.有 0个或 1个B.有 0个或多个C.有且只有一个 D.有 1个或 1个以上解析:解析:根据树的基本定义可知,每个树只能有且只有一个根结点。10.下列二叉排序树中,满足平衡二叉树定义的是( )。 (分数:2.00)A.B. C.D.解析:解析:考查平衡二叉树的定义。 根据平衡二叉树的定义有,任意结点的左右子

15、树高度差的绝对值不超过 1。而其余三个选项均可以找到不符合的结点。11.把树的根结点的层数定义为 1,其他结点的层数等于其父结点所在层数加上 1。设 T是一棵二叉树,K i 和 K j 是 T中子结点数小于 2的结点中的任意两个,它们所在的层数分别为 K i 和 K j ,当关系式K i -K j 1 一定成立时,则称 T为一棵( )。(分数:2.00)A.满二叉树B.二叉查找树C.平衡二叉树 D.完全二叉树解析:解析:此题干的叙述符合平衡二又树的定义。12.设森林 F中有三棵树,第一、第二、第三棵树的结点个数分别为 M 1 、M 2 和 M 3 。与森林 F对应的二叉树根结点的右子树上的结点

16、个数是( )。(分数:2.00)A.M 1B.M 1 +M 2C.M 3D.M 2 +M 3 解析:解析:森林转换成对应的二叉树,第一棵树的根结点作为此二叉树的根结点,第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的,因此结点数为 M2+M3。13.若一棵二叉树具有 10个度为 2的结点,5 个度为 1的结点,则度为 0的结点个数是( )。(分数:2.00)A.10B.11 C.16D.不确定解析:解析:根据二叉树的性质可知,度为 0的结点个数比度为 2结点个数多一个,即 n 0 =n 2 +1。14.具有 10个叶结点的二叉树中有( )个度为 2的结点。

17、(分数:2.00)A.8B.9 C.10D.11解析:解析:根据二叉树的性质 n 0 =n 2 +1,可知度为 2的结点个数为 9。15.在一棵度为 3的树中,度为 3的结点数为 2个,度为 2的结点数为 1个,度为 1的结点数为 2个,则度为 0的结点数为( )个。(分数:2.00)A.4B.5C.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个结点,那么此二叉树的高度为( )。(分数:2.00)A.

18、nlog 2 nB.log 2 nC.log 2 n+1D.不确定 解析:解析:已知一棵二叉树共有 n个结点,但二叉树的形式没有给出,因此,二叉树的高度不能确定。17.已知一棵二叉树,第 m层上最多含有结点数为( )。(分数:2.00)A.2 mB.2 m-1 一 1C.2 m-1 D.2 m 一 1解析:解析:根据二叉树的性质,二又树的第 m层上最多有 2 m-1 。18.有关二叉树下列说法正确的是( )。(分数:2.00)A.二叉树就是度为 2的树B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2D.二叉树中任何一个结点的度都为 2解析:解析:本题考查二叉树的概念。19.

19、一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是( )。(分数:2.00)A.CABDEFGB.ABCDEFG C.DACEFBGD.BAECFDG解析:解析:由题可得 A为根结点,并且 B为 A的孩子结点。选项 A,C 应为 A的左孩子,其前序序列应为 AC。选项 B,当 B为 A的右孩子,C 为 B的右孩子时,满足题目要求。选项 C,类似选项 A,其前序序列应为 ADC。选项 D,B 为 A的左孩子,C 为 A的右子树的根,E 为 C的左子树,FDG 为 C的右子树,其前序序列应为 ABEC。20.已知一个二叉树有 1025个结点,那么由此推断二叉树的高 h为( )。(分

20、数:2.00)A.11B.10C.111025 D.101024解析:解析:右完全二叉树中 10252 10 ,即最少需要 11层,最多需要有 1025层。21.一棵完全二叉树,共有 n个结点,那么,其叶结点数共有( )个。(分数:2.00)A.n2B.nC.(n-1)2D.(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为整数,

21、(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.( )的遍历仍需要栈的支持。(分数:2.00)A.前序线索树B.中序线索树C.后序线索树 D.中序线索树和前序线索树解析:解析:由于后序遍历先访问子树后访问根结点,从本质上要求运行栈中存放祖先的信息,即使对二叉树进行后序线索化,仍然不能脱离栈的支持对此二叉树进行遍历。23.已知一棵二叉树高度为,在此二叉树中只有度为 0和度为 2的结点,那么这棵二叉树的结点个数最少为( )。(分数:2.00)A.2hB.2h-1

22、 C.2h+1D.h+l解析:二、综合应用题(总题数:8,分数:22.00)24.综合应用题 41-47小题。_解析:25.已知一个二叉树,用二叉链表形式存储,给出此二叉树建立过程算法(可不描述结构体)。(分数:2.00)_正确答案:(正确答案:二叉树是递归定义的,以递归方式建立最简单。二叉树建立过程如下: BiTree Creat() 建立二叉树的二叉链表形式的存储结构 ElemType x; BiTree bt; scanf(”d”,x);本题假定结点数据域为整型 if(X=O)bt=null; else if(x0) bt=(BiNode*)malloc(sizeof(BiNode);

23、bt-data=x: bt 一lchild=Creat(): bt 一rchild=Creat(): else elTor(”输入错误”); return(bt); 结束 BiTree)解析:26.判别给定的二叉树是否是完全二叉树,并给出设计的算法(可不描述结构体)。(分数:2.00)_正确答案:(正确答案:判断此二叉树是否为完全 Z树的算法设计如下: int JudgeComplete(BiTree bt) 判断二叉树是否是完全二叉树,如是,返回 1;否则,返回 0 int tag=0; BiTree P=bt,Q; Q 是队列,元素是二又树结点指针,容量足够大 if(p=null)retu

24、rn 1; QueueInit(Q); QueueIn(Q,P); 初始化队列,根结点指针入队 while(!QueueEmpty(Q) P=QueueOut(Q): 出队 if(p-lehild int Leaves(Tree t) 计算以孩子一兄弟表示法存储的森林的叶子数 if(t) if(t 一fch=null) 若结点无孩子,则该结点必是叶子 return(1+Leaves(t 一nsib); 返回叶子结点和其兄弟子树中的叶子结点数 else return(Leaves(t 一feh)+Leaves(t 一nsib); 孩子子树和兄弟子树中叶子数之和 )解析:已知一棵二叉树的前序序列为

25、:A,B,D,G,J,E,H,C,F,I,K,L;中序序列为:D,J,G,B,E,H,A,C,K,I,L,F。(分数:6.00)(1).写出该二叉树的后序序列。(分数:2.00)_正确答案:(正确答案:J,G,D,H,E,B,K,L,I,F,C,A。)解析:(2).画出该二叉树。(分数:2.00)_正确答案:(正确答案:二叉树的形式如下图所示: )解析:(3).求该二叉树的高度以及该二叉树中度为 2、1、0 的结点个数。(分数:2.00)_正确答案:(正确答案:高度是 5,度为 0的结点个数为 4,度为 1的结点个数为 5,度为 2的结点个数为3。)解析:有 n个结点的二叉树,已知叶结点个数为

26、 n。(分数:6.00)(1).写出求度为 1的结点的个数的 n 1 的计算公式。(分数:2.00)_正确答案:(正确答案:设度为 2的结点个数为 n 2 ,则 n=n 0 +n 1 +n 2 。由二叉树的性质 n 0 =n 2 +1,n=2n 0 +n 1 一 1,所以度为 1的结点的个数 n 1 =n+12n 0 。)解析:(2).若此树是深度为 k的完全二叉树,写出 n为最小的公式。(分数:2.00)_正确答案:(正确答案:当树是深度为 k的完全二叉树时,n 的最小值 min(n)=2 k-1 。)解析:(3).若二叉树中仅有度为 0和度为 2的结点,写出求该二叉树结点个数 n的公式。(

27、分数:2.00)_正确答案:(正确答案:当二叉树中只有度为 0和度为 2的结点时,n=2n 0 -1(其中 n为树中的总结点数,n 0 为度为 0的结点数目)。)解析:28.已知一棵树的结点表示如下,其中各兄弟结点是依次出现的,画出对应的二叉树。 (分数:2.00)_正确答案:(正确答案:相应的树如下图所示: 树到二叉树的转换规则如下: (1)树的根结点为二叉树的根结点: (2)每个结点的第一个子结点(最左的子树)作为该结点的左孩子; (3)每个结点的右孩子为在树中与该结点的左孩子邻近的兄弟,所有具有兄弟关系的结点用指针链接起来。 转换成二叉树如下图所示: )解析:29.在一棵表示有序集 S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将 s分为3部分:在该路径左边结点中的元素组成的集合 S 1 ;在该路径上的结点中的元素组成的集合 S 2 ;在该路径右边结点中的元素组成的集合 S 3 。S=S 1 S 2 S 3 。若对于任意的 aS 1 ,bS 2 ,cS 3 ,是否总有 abc?为什么?(分数:2.00)_正确答案:(正确答案:不是。如下图所示的二叉搜索树: )解析:

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 考试资料 > 大学考试

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1