计算机专业基础综合（数据结构）模拟试卷11 (题后含答案及解析)
题型有：1. 单项选择题 2. 综合应用题
单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1． 一棵哈夫曼树共有99个结点，对其进行哈夫曼编码，共能得到( )种不同的编码。
A．48
B．50
C．99
D．100
正确答案：B
解析：本题考查哈夫曼树的性质。哈夫曼树中只有度为2和度为0的结点，哈夫曼编码是对哈夫
曼树中的叶子结点编码。根据树的性质N0=N2+1，故N0=(N2+N0+1)／2=(99+1)／2=50，哈夫曼树共有50个叶子结点，所以共能得到50个不同的码字。 知识模块：数据结构
2． 一棵含有n个结点的k叉树，可能达到的最大深度为( )，最小深度为( )。
A．n－k+l，logkn+1
B．n，logkn+l
C．n，logkn－1
D．n－k+l，logkn+l
二叉树的深度为k正确答案：A
解析：当k叉树种只有一个层的分支数为n，其他层的分指数均为1时，此时的树具有最大的深度为：n一k+1。 当该k叉树为完全数据结构
4． 有( )棵不同的二叉树，其结点的前序序列为a1，a2，…，an。
A．
B．
C．
D．
正确答案：A
解析：这是一个变形的求n个结点的互不相似的二叉树个数问题，设T(n)表示含n个结点的二叉树个数，T(0)=T(1)=1，T(2)=2，T(n)=T(n—1)×T(0)+T(n一2)×T(1)+…+T(0)×T(n一1)，而递归方程的解为T(n)=。 知识模块：数据结构
5． 有n个叶结点的非满的完全二叉树的高度为( )。
A．2n+1
B．2n－1
C．log22n+1
D．log22n-1
正确答案：A
解析：设j、k分别为度为1、2的结点数目，则结点总数m=n+j+k；由于是非满的，所以必有j=1，且n=k+1，因此有m=2n。设树的高度为h，具有n个结点的完全二叉树的深度为log2n+1。本题中，树的结点个数为2n，有h=log2(2n)+1。所以，有n个叶结点的非满的完全二叉树的高度为log2(2n)+1。 知识模块：数据结构
6． 在一棵二叉树中，单分支结点数为30，双分支结点数为15，则叶子结点数为( )。
A．15
B．16
C．17
D．47
正确答案：B
解析：由二叉树的性质可知：n0=n2+1=16。 知识模块：数据结构
7． 判断线索二叉树中某结点*p有左孩子的条件是( )。
A．p-＞lchild==NULL
B．p-＞lchild==0
C．p-＞hag==0
D．p-＞ltag==1
正确答案：C
解析：有左孩子表示不是线索，即p一＞ltag=0。 知识模块：数据结构
8． 在线索二叉树中，结点*p没有左子树的充要条件是( )。
A．p-＞lchild==NULL
B．p-＞ltag==1
C．p-＞ltag==1且p-＞lchild==NULL
D．以上都不对
正确答案：B
解析：没有左孩子时指针域指向线索，即p一＞ltag=1。 知识模块：数据结构
9． 如果Tl是由有序树T转换而来的二叉树，那么T中结点的前序遍历序列就是T1中结点的( )遍历序列。
A．前序
B．中序
C．后序
D．层次序
正确答案：A
解析：由树转换为二叉树的过程可知本题答案应为A。 知识模块：数据结构
10． 在图中所示的4棵二叉树中，( )不是完全二叉树。
A．图(a)
B．图(b)
C．图(c)
D．图(d)
正确答案：C
解析：由完全二叉树的定义可知(C)不是完全二叉树。 知识模块：数据结构
11． 一棵二叉树如下图所示，其中序遍历序列为( )。
A．abdgcefh
B．dgbaechf
C．gdbehfca
D．abcdefgh
正确答案：B
解析：由中序遍历过程可知本题答案应为B。 知识模块：数据结构
12． 有n个叶子结点的哈夫曼树的结点总数为( )。
A．不确定
B．2n
C．2n+l
D．2n－1
正确答案：D
解析：在哈夫曼树中，由计算公式可计算得结点总数为2n一1，所以选D。 知识模块：数据结构
13． 如图所示的T2是由森林Tl转换而来的二叉树，那么森林T1有( )个叶结点。
A．4
B．5
C．b
D．7
正确答案：C
解析：T2对应的森林T1如下图所示，由图中可以看出，所有的叶子结点总数为6。 知识模块：数据结构
综合应用题41-47小题，共70分。
14． 已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。
正确答案：二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下： BiTree Creat( ){ ／／建立二叉树的二叉链表形式的存储结构 ElemType x： BiTree bt； scanf(”％d＂，&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 涉及知识点：数据结构
15． 判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。
正确答案： 判断此二叉树是否为完全二叉树的算法设计如下： 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)Qu
eueln(Q，P一＞lchild)； ／／左孩子入队 else{ if(P一＞lchild)return 0； ／／前边已有结点为空，本结点不空 else tag=1； ／／首次出现结点为空 if(p一＞rchild&&!tag)QueueIn(Q，P一＞rchild)； ／／右孩子入队 else if(p一＞rchild)return 0； else tag=1； } }／／while return 1 ； }／／Judgecomplete 涉及知识点：数据结构
16． 以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。
正确答案：当森林(树)以孩子兄弟表示法存储时，若结点没有孩子(fch=null)，则它必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟(nsib)子树上叶结点个数之和。 typedef struct node{ elemType 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)); ／／孩子子树和兄弟子树中叶子数之和} 涉及知识点：数据结构
已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L冲序序列为：D，J，G，B，E，H，A，C，K，I，L，F。
17． 写出该二叉树的后序序列。
正确答案：J，G，D，H，E，B，K，L，I，F，C，A。 涉及知识点：数据结构
18． 画出该二叉树。
正确答案：二叉树的形式如下图所示： 涉及知识点：数据结构
19． 求该二叉树的高度以及该二叉树中度为2、1、0的结点个数。
正确答案：高度是5，度为0的结点个数为4，度为1的结点个数为5，度为2的结点个数为3。 涉及知识点：数据结构
有n个结点的二叉树，已知叶结点个数为n0。
20． 写出求度为1的结点的个数的n1的计算公式。
正确答案：设度为2的结点个数为n2，则n=n0+n1+n2。由二叉树的性质n0=n2+l，n=2n0+n1一1，所以度为1的结点的个数n1=n+l一2n0； 涉及知识点：数据结构
21． 若此树是深度为k的完全二叉树，写出n为最小的公式。
正确答案：当树是深度为k的完全二叉树时，n的最小值min(n)=2k-1。 涉及知识点：数据结构
22． 若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。
正确答案：当二叉树中只有度为0和度为2的结点时，n=2n0一1(其中n为树中的总结点数，n0为度为0的结点数目)。 涉及知识点：数据结构
23． 已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。
正确答案：相应的树如下图所示： 树到二叉树的转换规则如下： (1)树的根结点为二叉树的根结点； (2)每个结点的第一个子结点(最左的子树)作为该结点的左孩子： (3)每个结点的右孩子为在树中与该结点的左孩子邻近的兄弟，所有具有兄弟关系的结点用指针链接起来。转换成二叉树如下图所示： 涉及知识点：数据结构
24． 在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3，是否总有a≤b≤c?为什么?
正确答案：不是。如下图所示的二叉搜索树 取从4到12的路径，则S1={1，2，3，7}，S2={4，8，10，12}，S3为空集，取S1中的元素7和S2中的元素4，令a=7，b=4，有a＞b。则上述命题不成立。 涉及知识点：数据结构
25． 假定用两个一维数L[N]和R[N]作为有N个结点l，2，…，N的二叉树的存储结构。L[i]和
R[i]分别指示结点i的左儿子和右儿子；L[i]=0(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论