计算机专业基础综合历年真题试卷汇编

计算机专业基础综合历年真题试卷汇编1

(总分：62.00，做题时间：90分钟)

一、 单项选择题(总题数：27，分数：54.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）

__________________________________________________________________________________________

解析：

2.先序序列为a，b，c，d的不同二叉树的个数是_______。

（分数：2.00）

A.13

B.14 √

C.15

D.16

解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序

序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地

确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个

n

不同元素进栈，出栈序列的个数为 C =14。

2n

3.假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，

栈中的元素依次是_______。

（分数：2.00）

A.+(*-

B.+(-* √

C.／+(*-*

D.／+-*

解析：解析：将中缀表达式转换为后缀表达式的算法思想如下： 从左向右开始扫描中缀表达式； 遇到数

字时，加入后缀表达式； 遇到运算符时： a．若为‘(’，入栈； b．若为‘)’，则依次把栈中的的运算

符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’； c．若为除括号外的其他运算符，当其优先级

高于除‘(’以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和

优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。 当扫描的中缀表达式结束时，

栈中的所有运算符依次出栈加入后缀表达式。

4.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1

的结点，则树T的叶结点个数是_______。

（分数：2.00）

A.41

B.82 √

C.113

D.122

解析：解析：设树中度为i(i=0，1，2，3，4)的结点数分别为N ，树中结点总数为N，则树中各结点的

i

度之和等于N-1，即N=1+N +2N +3N +4N =N +N +N +N +N ，根据题设中的数据，即可得到

123401234

N =82，即树T的叶结点的个数是82。

0

5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是_______。

（分数：2.00）

A.39

B.52

C.111 √

D.119

解析：解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满

二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7

时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完

7

全二叉树的结点个数最多为(2 -1)-16=111个结点。

6.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是_______。

（分数：2.00）

A.257

B.258

C.384 √

D.385

解析：解析：根据完全二叉树的性质，最后一个分支结点的序号为=384，故叶子结点的个数为

768-384=384。

7.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历

后的结点序列为3，1，7，5，6，2，4，则其遍历方式是_______。

（分数：2.00）

A.LRN

B.NRL

C.RLN

D.KNL √

解析：解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍

历的方式是RNL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌

握遍历的思想。

8.先序序列为a，b，c，d的不同二叉树的个数是_______。

（分数：2.00）

A.13

B.14 √

C.15

D.16

解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序

序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地

确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个

n

不同元素进栈，出栈序列的个数为 C =14。

n+1

9.若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍

历序列不会是_______。

（分数：2.00）

A.1，2，3，4

B.2，3，4，1

C.3，2，4，1 √

D.4，3，2，1

解析：解析：前序序列为NLR，后序序列为LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结

点同时存在左右孩子，即二叉树的高度为4。1为根结点，由于根结点只能有左孩子(或右孩子)，因此，在

中序序列中，1或在序列首或在序列尾，ABCD皆满足要求。仅考虑以1的孩子结点2为根结点的子树，它

也只能有左孩子(或右孩子)，因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求。

10.若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结

点_______。

（分数：2.00）

A.只有e √

B.有e、b

C.有e、c

D.无法确定

解析：解析：前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两

个结点的前序序列为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。

11.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是_______。

（分数：2.00）

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

解析：解析：各选项对应的查找过如下图，BCD对应的查找树都是二叉排序树，A对应的查找树不是二叉排

序树，因为在91为根的左子树中出现了比91大点的结点94。

12.在任意一棵非空二叉排序树T 中，删除某结点v之后形成二叉排序树T ，再将v插入T 形成二叉

122

排序树T 。下列关于T 与T 的叙述中，正确的是_______。 Ⅰ．若v是T 的叶结点，则T 与T

313113

不同 Ⅱ．若v是T 的叶结点，则T 与T 相同 Ⅲ．若v不是T 的叶结点，则T 与T 不同 Ⅳ．若

113113

v不是T 的叶结点，则T 与T 相同

113

（分数：2.00）

A.仅Ⅰ、Ⅲ

B.仅Ⅰ、Ⅳ

C.仅Ⅱ、Ⅲ √

D.仅Ⅱ、Ⅳ

解析：解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶

子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那

么再插入这个结点后，后来的二叉树会发生变化，不完全相同。

13.下列二叉排序树中，满足平衡二叉树定义的是_______。

（分数：2.00）

A.

B. √

C.

D.

解析：解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余3个选

项均可以找到不符合该条件的结点。在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因

子都写出来再进行判断。

14.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37

所在结点的左、右子结点中保存的关键字分别是_______。

（分数：2.00）

A.13，48

B.24，48

C.24，53 √

D.24，90

解析：解析：插入48以后，该二叉树根结点的平衡因子由-1变为-2，在最小不平衡子树根结点的右子树

(R)的左子树(L)中插入新结点引起的不平衡属于RL型平衡旋转，需要做两次旋转操作(先右旋后左旋)。

调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。

15.若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为_______。

（分数：2.00）

A.10

B.20 √

C.32

D.33

解析：解析：所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。

对于高度为N、左右子树的高度分别为N-1和N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点

数的公式为：C =C +C +1，C =1，C =2，C 2+1+1=4，可推出C =20。 画图法：先画出T 和

NN-1N-212361

T ；然后新建一个根结点，连接T 、T 构成T ；新建一个根结点，连接T 、T 构成T ；……

2213324

依此类推，直到画出T ，可知T 的结点数为20。 排除法：对于选项A，高度为6、结点数为10的树

66

怎么也无法达到平衡。对于选项C，结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树

刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。

同理D错误。只可能选B。

16.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支

结点的个数是_______。

（分数：2.00）

A.0

B.1

C.2

D.3 √

解析：解析：利用7个关键字构建平衡二叉树T，平衡因子为O的分支结点个数为3，构建的平衡二叉树如

下图所示。构造及调整的过程如下：

17.现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。下列关于该平

衡二叉树的叙述中，正确的是_______。

（分数：2.00）

A.根结点的度一定为2

B.树中最小元素一定是叶结点

C.最后插入的元素一定是叶结点

D.树中最大元素一定是无左子树 √

解析：解析：只有两个结点的平衡二叉树的根结点的度为1，A错误。中序遍历后可以得到一个降序序列，

树中最小元素一定无左子树(可能有右子树)，因此不一定是叶结点，B错误。最后插入的结点可能会导致

平衡调整，而不一定是叶结点，C错误。

18.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，

u和v可能具有的关系是_______。Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系

（分数：2.00）

A.只有Ⅱ

B.Ⅰ和Ⅱ √

C.Ⅰ和Ⅲ

D.Ⅰ、Ⅱ和Ⅲ

解析：解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森

林关系中可能是兄弟关系或原本就是父子关系。 情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，

结点v就变成结点u第一个孩子的右孩子，符合要求。 情形Ⅱ．结点u和v是兄弟结点的关系，但二者之

中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合

要求。

情形Ⅲ：若结点u的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者最

左父结点的两棵子树中，不可能出现在同一条路径中。

根据树与二叉树的转换规则，将这4种情况

转换成树种结点的关系。(1)在原来的树中u是v的父结点的父结点；(2)在树中u是v的父结点；(3)在树

中u是v的父结点的兄弟；(4)在树中u与v是兄弟关系。由此可知Ⅰ和Ⅱ正确。

19.己知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是_______。

（分数：2.00）

A.115

B.116

C.1895

D.1896 √

解析：解析：树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转

换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896。通常本

题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，

故无右孩子的结点个数=2011-115=1896。

20.将森林F转换为对应的二叉树T，F中叶结点的个数等于_______。

（分数：2.00）

A.T中叶结点的个数

B.T中度为1的结点个数

C.T中左孩子指针为空的结点个数 √

D.T中右孩子指针为空的结点个数

解析：解析：将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的

第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那

么转化为二叉树时，该结点就没有左结点，所以F中叶结点的个数就等于T中左孩子指针为空的结点个数，

选C。此题还可以通过一些特例来排除A、B、D选项。

21.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是_______。

（分数：2.00）

A.

B.

C.

D. √

解析：解析：题中所给二叉树的后序序列为d，b，c，a。结点d无前驱和左子树，左链域空，无右子树，

右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前

驱结点b，无右子树，右链域指向其后继结点a。故选D。

22.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是_______。

（分数：2.00）

A.X的父结点 √

B.以Y为根的子树的最左下结点

C.X的左兄弟结点Y

D.以Y为根的子树的最右下结点

解析：解析：根据后序线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，

利用后序遍历的方式可知X结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在

解题的过程中可以画出如下草图。

23.若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是_______。

（分数：2.00）

A.e、c

B.e、a

C.d、c

D.b、a √

解析：解析：线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写

出二叉树的中序遍历序列：edbxac，中序遍历中在x左边和右边的字符，就是它在中序线索化的左、右线

索，即b、a，选D。

24.对n(n≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是_______。

（分数：2.00）

A.该树一定是一棵完全二叉树 √

B.树中一定没有度为1的结点

C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

解析：解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1的结

点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C正确；

哈夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的

权值，在与结点P的左、右子树根结点处于同—层的结点中，若存在权值大于结点P权值的结点Q，那么

结点Q的兄弟结点中权值较小的一个应该与结点P作为左、右子树构造新的二叉树。综上可知，哈夫曼树

中任一非叶结点的权值一定不小于下一层任一结点的权值。

25.5个字符有如下4种编码方案，不是前缀编码的是_______。

（分数：2.00）

A.01，0000，0001，001，1

B.011，000，001，010，1

C.000，001，010，011，100

D.0，100，110，1110，1100 √

解析：解析：前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。选

项D中编码110是编码1100的前缀，违反了前缀编码的规则，所以D不是前缀编码。

26.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_______。

（分数：2.00）

A.24，10，5和24，10，7

B.24，10，5和24，12，7

C.24，10，10和24，14，11

D.24，10，5和24，14，6 √

解析：解析：在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项A为例：若两个10分别属于

两棵不同的子树，根的权值不等于其孩子的权值和，不符：若两个10属同棵子树，其权值不等于其两个孩

子(叶结点)的权值和，不符。B、C选项的排除方法一样。

27.下列关于无向连通图特性的叙述中，正确的是_______。Ⅰ．所有顶点的度之和为偶数Ⅱ．边数大于顶

点个数减1Ⅲ．至少有一个顶点的度为1

（分数：2.00）

A.只有Ⅰ √

B.只有Ⅱ

C.Ⅰ和Ⅱ

D.Ⅰ和Ⅲ

解析：解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次(出度和入度)，故

所有顶点的度之和为边数的两倍，Ⅰ正确。n个顶点、n-1条边可以构成无向连通图，比如树，Ⅱ错误。顶

点数为N(N≥1)的无向完全图中不存在度为1的顶点，Ⅲ错误。

二、 综合应用题(总题数：3，分数：8.00)

28.综合应用题41-47小题。

__________________________________________________________________________________________

解析：

29.已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)

保存在如下的一维数组中。请写出图G的邻接矩阵A。

（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：在上三角矩阵A[6][6]中，第1行至第5行主对角线上方的元素个数分别为5、4、

3、2、1，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。

采用“平移”的思想，

分别将前5、4、3、2、1个元素，移动到矩阵对角线(“0”)右边的行上。 故，图G的邻接矩阵A如下图

所示。

)

解析：解析：考查上三角矩阵的存储。

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链

表存储，结点结构为：

其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点

的指针，请设计求T的WPL的算法，要求：（分数：6.00）

(1).给出算法的基本设计思想；（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：算法的基本设计思想： ①基于先序递归遍历的算法思想是用一个static变量记录、

wpl，把每个结点的深度作为递归函数的 一个参数传递，算法步骤如下： 若该结点是叶结点，那么变量

wpl加上该结点的深度与权值之积； 若该结点是非叶结点，那么若左子树不为空，对左子树调用递归算法：

若右子树不为空，对右子树 调用递归算法，深度参数均为本结点的深度参数加1； 最后返回计算出的wpl

即可。 ②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数， 当遍历到叶结点时，

累计wpl； 当遍历到非叶结点时，把该结点的子树加入队列； 当某结点为该层的最后一个结点时，层数

自增1； 队列空时遍历结束，返回wpl。)

解析：

(2).使用C或C++语言，给出二叉树结点的数据类型定义；（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：二叉树结点的数据类型定义如下： typedef struct BiTNode{ int weight； struct

BiTNode *lchild，*rchild； }BiTNode，*BiTree；)

解析：

(3).根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（分数：2.00）

__________________________________________________________________________________________

正确答案：(正确答案：算法的代码如下： ①基于先序遍历的算法： int WPL(BiTree root){ return

wpl_PreOrder(root，0)； } int wpl PreOrder(BiTree root，int deep){ static int wpl=0；／／定义

一个static变量存储wpl if(root-＞lchild==NuLL＆＆root-＞lchild==NULL)／／若为叶结点，累积wpl

wpl+=deep*root-＞weight， if(root-＞ichiid!；NuLL)／／若左子树不空，对左子树递归遍历

wpl_PreOrder(root-＞ichild，deep+1)， if(root-＞rchiidI=NULL)／／若右子树不空，对右于树递归遍

历 wpl_PreOrder(root-＞rchild，deep+1)； return wpl； } ②基于层次遍历的算法： #define MaxSize

100／／设置队列的最大容量 int wpl LevelOrder(BiTree root){ BiTree q[MaxSize]；／／声明队列，

end1为头指针，end2为尾指针 int end1，end2，／／队列最多容纳MaxSize-1个元素 end1=end2=0；／

／头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl=deep=0；／／初始化wpl和深度 BiTree

lastNode；／／lastNode用来记录当前层的最后一个结点 BiTree newlastNode；／／newlastNode用来记

录下一层的最后一个结点 lastNode=root；／／lastNode初始化为根结点 newlastNode=NULL；／／

newlastNode初始化为空 q[end2++]=root；／／根结点入队 while(end1!=end2)f／／层次遍历，若队列

不空则循环 BiTree t=q[end1++]；／／拿出队列中的头一个元素 if(t-＞ichild==NULL&&t-＞

lchild==NULL){ wpl+=deep*t-＞weight； }／／若为叶结点，统计wpl if(t-＞ichild!=NULL){／／若非

叶结点把左结点入队 q[end2++]=t-＞ichild； newlastNode=t-＞ichiid； }／／并设下一层的最后一个

结点为该结点的左结点 if(t-＞rchild!=NULL){／／处理叶结点 q[end2++]=t-＞rchild； newlastNode=t-

＞rchild； } if(t==lastNode){／／若该结点为本层最后一个结点，更新lastNode lastNode=newlastNode；

deep+=1；／／层数加1 } } return wpl；／／返回wpl })

解析：解析：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，

可以使用先序遍历或层次遍历解决问题。