[考研类试卷]计算机专业基础综合(树与二叉树)模拟试卷3及答案与解析.doc

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

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,其他结点的层数等于其父结点所在层数加上。设T 是一棵二叉树,K

4、i 和 Kj 是 T 中子结点数小于 2 的结点中的任意两个,它们所在的层数分别为 Ki 和 Kj,当关系式|K i 一 K j|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)(D)不确定16 已知一棵二叉树,第 m 层上最多含有结点数为 ( )。(A)2 m(B) 2m-1 一 1(C) 2m-1(D)2 m-1 一 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) (n1)2(D)(n+1) 221 ( )的遍历仍需要栈的支持。(A)前序线

7、索树(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,K,L ;中序

8、序列为:D,J,G,B,E,H,A,C,K,I,L,F。(1)写出该二叉树的后序序列。(2)画出该二叉树。(3)求该二叉树的高度以及该二叉树中度为 2、1、0 的结点个数。27 有凡个结点的二叉树,已知叶结点个数为 n0。 (1)写出求度为 1 的结点的个数的n1 的计算公式。 (2)若此树是深度为后的完全二叉树,写出乃为最小的公式。 (3)若二叉树中仅有度为 0 和度为 2 的结点,写出求该二叉树结点个数 n 的公式。28 已知一棵树的结点表示如下,其中各兄弟结点是依次出现的,画出对应的二叉树。 29 在一棵表示有序集 S 的二叉搜索树 (binary search tree)中,任意一条从

9、根到叶结点的路径将 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 【正确答案】 D【试题

10、解析】 根据题目给出的中缀和后缀表达式可以得到其算术表达式为:(A+B*C)一 DE,前缀表达式:一+A*BCDE。【知识模块】 树与二叉树3 【正确答案】 B【试题解析】 根据表达式 a+b*(c+de)可知其后缀表达式为 abcde+*+。【知识模块】 树与二叉树4 【正确答案】 C【试题解析】 由先序和中序遍历序列确定一棵二叉树,再给出这棵二叉树的后序遍历序列。 由此图可以确认后序遍历的序列为 LKJNOMI。【知识模块】 树与二叉树5 【正确答案】 A【试题解析】 F 对应的二叉树共有 m 个结点,右子树上 n 个,左子树上有(mn一 1)个,第一株树包括根和左子树,共(mn)个。【知

11、识模块】 树与二叉树6 【正确答案】 B【试题解析】 选项 A、C、D 运算的时间复杂度都是 O(n),而选项 B 的运算的时间复杂度为 O(1),因为对于指定位置 p 和 g 的两个结点,判断是否在同一层上,只需判断两者*43 是否成立。【知识模块】 树与二叉树7 【正确答案】 C【试题解析】 除根结点层只有 1 个结点外,其他各层均有两个结点,结点总数=2(1001)+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。【知识模块】 树与二叉树17 【正确

14、答案】 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 层,最多需要有 1025

15、 层。【知识模块】 树与二叉树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 【正确答案】 C【试题解析

16、】 由于后序遍历先访问子树后访问根结点,从本质上要求运行栈中存放祖先的信息,即使对二叉树进行后序线索化,仍然不能脱离栈的支持对此二叉树进行遍历。【知识模块】 树与二叉树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*)malloc(si

17、zeof(BiNode);bt-data=x;bt-lchild=Creat();bt-rchild=Creat();else elTor(“输入错误”);return(bt);结束 BiTree【知识模块】 树与二叉树24 【正确答案】 判断此二叉树是否为完全二叉树的算法设计如下:int JudgeComp|ete(BiTree bt)判断二叉树是否是完全二叉树,如是,返回 1;否则,返回 0int tag=0;BiTree P=bt,Q ; Q 是队列,元素是二叉树结点指针,容量足够大if(p=null)return 1;Queuelnit(Q);Queueln(Q,p) ; 初始化队列,

18、根结点指针入队while(!QueueEmpty(Q)P=QueueOut(Q); 出队if(p-lchild&!tag)Queueln(Q,p 一lchild); 左孩子入队elseif(p 一lchild)return 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)+Leaves(t 一nsib

20、); 孩子子树和兄弟子树中叶子数之和【知识模块】 树与二叉树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+l,n=2n 0+n1 一 1,所以度为 1 的结点的个数 n1=n+1-2n0; (2) 当树是深度为k 的完全二叉树时,n 的最小值 mi

21、n(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,S 2=4,8,10,12,S 3 为空集,取 S1 中的元素 7 和 S2 中的元素 4,令 a=7,b=4,有 ab。则上述命题不成立。【知识模块】 树与二叉树

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

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

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