计算机专业基础综合历年真题试卷汇编2 (题后含答案及解析)
题型有：1. 单项选择题 2. 综合应用题
单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1． 先序序列为a，b，c，d的不同二叉树的个数是_______。
A．13
B．14
C．15
D．16
正确答案：B
解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和
中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为C2nn=14。 知识模块：数据结构
2． 假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。
A．+(*-
B．+(-*
C．／+(*-*
D．／+-*
正确答案：B
解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇
到数字时，加入后缀表达式；遇到运算符时：a．若为‘(’，入栈；b．若为‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’；c．若为除括号外的其他运算符，当其优先级高于除‘(’以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。 知识模块：数据结构
3． 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是_______。
A．41
B．82
C．113
D．122
正确答案：B
解析：设树中度为i(i=0，1，2，3，4)的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。 知识模块：数据结构
4． 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是_______。
A．39
B．52
C．111
D．119
正确答案：C
解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或
7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为(27-1)-16=111个结点。 知识模块：数据结构
5． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是_______。
A．257
B．258
C．384
D．385
正确答案：C
解析：根据完全二叉树的性质，最后一个分支结点的序号为=384，故叶子结点的个数为768-384=384。 知识模块：数据结构
6． 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是_______。
A．LRN
B．NRL
C．RLN
D．KNL
正确答案：D
解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是RNL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。 知识模块：数据结构
7． 先序序列为a，b，c，d的不同二叉树的个数是_______。
A．13
B．14
C．15
D．16
正确答案：B
解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为Cn+1n=14。 知识模块：数据结构
二叉树前序中序后序图解
8． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是_______。
A．1，2，3，4
B．2，3，4，1
C．3，2，4，1
D．4，3，2，1
正确答案：C
解析：前序序列为NLR，后序序列为LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为4。1为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1或在序列首或在序列尾，ABCD皆满足要求。仅考虑以1的孩子结点2为根结点的子树，它也只能有左孩子(或右孩子)，因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求。 知识模块：数据结构
9． 若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点_______。
A．只有e
B．有e、b
C．有e、c
D．无法确定
正确答案：A
解析：前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为XY与后序序列为YX时，则X为Y的祖先。考虑前序序列a，e，b，d，c、后序序列b，c，d，e，a，可知a为根结点，e为a的孩子结点；此外，a的孩子结点的前序序列e，b，d，c、后序序列b，c，d，e，可知e是bcd的祖先，故根结点的孩子结点只有e。故选A。 知识模块：数据结构
10． 对于下列关键字序列，不可能构成某二叉排序树中一条查路径的序列是_______。
A．95，22，91，24，94，71
B．92，20，91，34，88，35
C．21，89，77，29，36，38
D．12，25，71，68，33，34
正确答案：A
解析：各选项对应的查过如下图，BCD对应的查树都是二叉排序树，A对应的查树不是二叉排序树，因为在91为根的左子树中出现了比91大点的结点94。 知识模块：数据结构
11． 在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是_______。Ⅰ．若v是T1的叶结点，则T1与T3不同Ⅱ．若v是T1的叶结点，则T1与T3相同Ⅲ．若v不是T1的叶结点，则T1与T3不同Ⅳ．若v不是T1的叶结点，则T1与T3相同
A．仅Ⅰ、Ⅲ
B．仅Ⅰ、Ⅳ
C．仅Ⅱ、Ⅲ
D．仅Ⅱ、Ⅳ
正确答案：C
解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。 知识模块：数据结构
12． 下列二叉排序树中，满足平衡二叉树定义的是_______。
A．
B．
C．
D．
正确答案：B
解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余3个选项均可以到不符合该条件的结点。在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。 知识模块：数据结构
13． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是_______。
A．13，48
B．24，48
C．24，53
D．24，90
正确答案：C
解析：插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树(R)的左子树(L)中插入新结点引起的不平衡属于RL型平衡旋转，需要做两次旋转操作(先
右旋后左旋)。调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。 知识模块：数据结构
14． 若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为_______。
A．10
B．20
C．32
D．33
正确答案：B
解析：所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为N、左右子树的高度分别为N-1和N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点数的公式为：CN=CN-1+CN-2+1，C1=1，C2=2，C32+1+1=4，可推出C
6=20。画图法：先画出T1和T2；然后新建一个根结点，连接T2、T1构成T3；新建一个根结点，连接T3、T2构成T4；……依此类推，直到画出T6，可知T6的结点数为20。排除法：对于选项A，高度为6、结点数为10的树怎么也无法达到平衡。对于选项C，结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D错误。只可能选B。 知识模块：数据结构

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