1、计算机专业基础综合历年真题试卷汇编 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 先序序列为 a，b，c ，d 的不同二叉树的个数是 _。（A）13（B） 14（C） 15（D）162 假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是_。（A）+(*-（B） +(-*（C） +(*-*（D）+-*3 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点， 10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1
2、 的结点，则树 T 的叶结点个数是 _。（A）41（B） 82（C） 113（D）1224 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则该完全二叉树的结点个数最多是_。（A）39（B） 52（C） 111（D）1195 若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是_。（A）257（B） 258（C） 384（D）3856 给定二叉树如下图所示。设 N 代表二叉树的根， L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是_。（A）LRN（B） NRL（C） RLN（D）KNL7 先序序列为
3、a，b，c ，d 的不同二叉树的个数是 _。（A）13（B） 14（C） 15（D）168 若一棵二叉树的前序遍历序列和后序遍历序列分别为 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，19 若一棵二叉树的前序遍历序列为 a，e ，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点_。（A）只有 e（B）有 e、b（C）有 e、c（D）无法确定10 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是_。（A）95，22，91，24，94，71（B） 92，20，9
4、1，34，88，35（C） 21，89，77，29，36，38（D）12，25，71，68，33，3411 在任意一棵非空二叉排序树 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）仅、12 下列二叉排序树中，满足平衡二叉树定义的是_。13 在下图
5、所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是_。（A）13，48（B） 24，48（C） 24，53（D）24，9014 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为_。（A）10（B） 20（C） 32（D）3315 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则T 中平衡因子为 0 的分支结点的个数是_。（A）0（B） 1（C） 2（D）316 现有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序
6、序列。下列关于该平衡二叉树的叙述中，正确的是_。（A）根结点的度一定为 2（B）树中最小元素一定是叶结点（C）最后插入的元素一定是叶结点（D）树中最大元素一定是无左子树17 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是_。父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系（A）只有（B） 和（C） 和（D）、和18 己知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是_。（A）115（B） 116（C） 1895（D）189619 将森林 F 转换为对应的二叉树 T
7、，F 中叶结点的个数等于 _。（A）T 中叶结点的个数（B） T 中度为 1 的结点个数（C） T 中左孩子指针为空的结点个数（D）T 中右孩子指针为空的结点个数20 下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是_。21 若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是_。（A）X 的父结点（B）以 Y 为根的子树的最左下结点（C） X 的左兄弟结点 Y（D）以 Y 为根的子树的最右下结点22 若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是_。（A）e、c（B） e、a（C） d、c（D）b、a23 对 n(n2)
8、个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是_。（A）该树一定是一棵完全二叉树（B）树中一定没有度为 1 的结点（C）树中两个权值最小的结点一定是兄弟结点（D）树中任一非叶结点的权值一定不小于下一层任一结点的权值24 5 个字符有如下 4 种编码方案，不是前缀编码的是_。（A）01，0000，0001，001，1（B） 011，000，001，010，1（C） 000，001，010，011，100（D）0，100，110，1110，110025 下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_。（A）24，10，5 和 24，10，
9、7（B） 24，10，5 和 24，12，7（C） 24，10，10 和 24，14，11（D）24，10，5 和 24，14，626 下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1（A）只有（B）只有 （C） 和（D）和二、综合应用题41-47 小题，共 70 分。27 已知有 6 个顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先) 保存在如下的一维数组中。请写出图 G 的邻接矩阵 A。27 二叉树的带权路径长度(WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，
10、采用二叉链表存储，结点结构为：其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求：28 给出算法的基本设计思想；29 使用 C 或 C+语言，给出二叉树结点的数据类型定义；30 根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。计算机专业基础综合历年真题试卷汇编 2 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列
11、和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a，b ，c，d 为入栈次序，则出栈序列的个数为?”，对于 n 个不同元素进栈，出栈序列的个数为 C2nn=14。【知识模块】 数据结构2 【正确答案】 B【试题解析】 将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a若为(，入栈；b若为)，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除( ；c若为除括号外的其他运算符，当其优先级高于除(以外的栈顶运算符时，直接入栈。否则从栈
12、顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。【知识模块】 数据结构3 【正确答案】 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 【正确答案】 C【试题解析】 完全二叉树比满二叉树只是在最下面一层的右边缺少了部分
13、叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 82=16 个叶结点，故完全二叉树的结点个数最多为(2 7-1)-16=111 个结点。【知识模块】 数据结构5 【正确答案】 C【试题解析】 根据完全二叉树的性质，最后一个分支结点的序号为=384，故叶子结点的个数为 768-384=384。【知识模块】 数据结构6 【正确答案】 D【试题解析】 分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历
14、的方式是 RNL。本题考查的遍历方法并不是二叉树的3 种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。【知识模块】 数据结构7 【正确答案】 B【试题解析】 根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a，b ，c，d 为入栈次序，则出栈序列的个数为?”，对于 n 个不同元素进栈，出栈序列的个数为 Cn+1n=14。【知识模块】 数据结构8 【正确答案】 C【试题解析】 前序序列为 NLR，后序序列为 LRN，由于前序序
15、列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点 2 为根结点的子树，它也只能有左孩子(或右孩子)，因此，在中序序列中，2 或在序列首或序列尾，ABD皆满足要求。【知识模块】 数据结构9 【正确答案】 A【试题解析】 前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为Y 的祖先。考虑前序序列a，e ，b ，d，c、后序序列b，c，d
16、，e，a ，可知 a 为根结点，e 为 a 的孩子结点；此外，a 的孩子结点的前序序列e， b，d，c、后序序列 b，c，d，e，可知 e 是 bcd的祖先，故根结点的孩子结点只有 e。故选 A。【知识模块】 数据结构10 【正确答案】 A【试题解析】 各选项对应的查找过如下图，BCD 对应的查找树都是二叉排序树，A 对应的查找树不是二叉排序树，因为在 91 为根的左子树中出现了比 91 大点的结点 94。【知识模块】 数据结构11 【正确答案】 C【试题解析】 在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点
17、之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。【知识模块】 数据结构12 【正确答案】 B【试题解析】 根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余 3 个选项均可以找到不符合该条件的结点。在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。【知识模块】 数据结构13 【正确答案】 C【试题解析】 插入 48 以后，该二叉树根结点的平衡因子由-1 变为-2，在最小不平衡子树根结点的右子树(R)的左子树(L)中插入新结点引起的不平衡属于 RL 型平衡旋转，需要做两次旋转操作(先右旋后左
18、旋)。调整后，关键字 37所在结点的左、右子结点中保存的关键字分别是 24、53。【知识模块】 数据结构14 【正确答案】 B【试题解析】 所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为 N、左右子树的高度分别为 N-1 和 N-2、所有非叶结点的平衡因子均为 1 的平衡二叉树，总结点数的公式为：C N=CN-1+CN-2+1， C1=1，C 2=2，C 32+1+1=4，可推出 C6=20。画图法：先画出 T1 和 T2；然后新建一个根结点，连接 T2、T 1 构成T3；新建一个根结点，连接 T3、T 2 构成 T4；依此类推，直到画出 T6，可知
19、T6 的结点数为 20。排除法：对于选项 A，高度为 6、结点数为 10 的树怎么也无法达到平衡。对于选项 C，结点较多时，考虑较极端情形，即第 6 层只有最左叶子的完全二叉树刚好有 32 个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理 D 错误。只可能选 B。【知识模块】 数据结构15 【正确答案】 D【试题解析】 利用 7 个关键字构建平衡二叉树 T，平衡因子为 O 的分支结点个数为 3，构建的平衡二叉树如下图所示。构造及调整的过程如下：【知识模块】 数据结构16 【正确答案】 D【试题解析】 只有两个结点的平衡二叉树的根结点的度为 1，A 错误
20、。中序遍历后可以得到一个降序序列，树中最小元素一定无左子树(可能有右子树)，因此不一定是叶结点，B 错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C 错误。【知识模块】 数据结构17 【正确答案】 B【试题解析】 森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点 v 就变成结点 u 第一个孩子的右孩子，符合要求。情形结点 u 和 v 是兄弟结点的关系，但二者之中还有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点
21、 u的右孩子，符合要求。 情形：若结点 u 的父结点与 v 的父结点是兄弟关系，则转换后，结点 u 和 v 分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。根据树与二叉树的转换规则，将这 4 种情况转换成树种结点的关系。(1)在原来的树中 u 是 v 的父结点的父结点； (2)在树中 u 是v 的父结点；(3)在树中 u 是 v 的父结点的兄弟；(4)在树中 u 与 v 是兄弟关系。由此可知和正确。【知识模块】 数据结构18 【正确答案】 D【试题解析】 树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的
22、结点个数=分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。【知识模块】 数据结构19 【正确答案】 C【试题解析】 将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F 中叶结点的个数就等于 T 中左孩子指针为空的结点个数，选 C。此题还可以通过一些特例来排除 A、B、D 选项
23、。【知识模块】 数据结构20 【正确答案】 D【试题解析】 题中所给二叉树的后序序列为 d，b ，c ，a。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。故选 D。【知识模块】 数据结构21 【正确答案】 A【试题解析】 根据后序线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知 X 结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。【知识模块】 数
24、据结构22 【正确答案】 D【试题解析】 线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在 x 左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a，选 D。【知识模块】 数据结构23 【正确答案】 A【试题解析】 哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为 1 的结点，B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点 P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点
25、P 的左、右子树根结点处于同层的结点中，若存在权值大于结点 P 权值的结点 Q，那么结点 Q 的兄弟结点中权值较小的一个应该与结点 P 作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。【知识模块】 数据结构24 【正确答案】 D【试题解析】 前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。选项 D 中编码 110 是编码 1100 的前缀，违反了前缀编码的规则，所以 D 不是前缀编码。【知识模块】 数据结构25 【正确答案】 D【试题解析】 在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项 A为例：若两个
26、 10 分别属于两棵不同的子树，根的权值不等于其孩子的权值和，不符：若两个 10 属同棵子树，其权值不等于其两个孩子(叶结点)的权值和，不符。B、C 选项的排除方法一样。【知识模块】 数据结构26 【正确答案】 A【试题解析】 每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次(出度和入度) ，故所有顶点的度之和为边数的两倍，正确。n 个顶点、n-1条边可以构成无向连通图，比如树，错误。顶点数为 N(N1)的无向完全图中不存在度为 1 的顶点，错误。【知识模块】 数据结构二、综合应用题41-47 小题，共 70 分。27 【正确答案】 在上三角矩阵 A66中，第 1 行至第 5
27、行主对角线上方的元素个数分别为 5、4、3、2、1，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。 采用“平移”的思想，分别将前 5、4、3、2、1 个元素，移动到矩阵对角线 (“0”)右边的行上。故，图 G 的邻接矩阵 A 如下图所示。【试题解析】 考查上三角矩阵的存储。【知识模块】 数据结构【知识模块】 数据结构28 【正确答案】 算法的基本设计思想：基于先序递归遍历的算法思想是用一个 static 变量记录、wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶结点，那么变量 wpl 加上该结点的深度与权值之积；若该结点是非叶结点，那么若左子树不为空，
28、对左子树调用递归算法：若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加 1；最后返回计算出的 wpl 即可。基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶结点时，累计 wpl；当遍历到非叶结点时，把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增 1；队列空时遍历结束，返回 wpl。【知识模块】 数据结构29 【正确答案】 二叉树结点的数据类型定义如下：typedef struct BiTNodeint weight；struct BiTNode *lchild，*rchild；BiTNode，*BiTree；【知识模块】 数据结构
29、30 【正确答案】 算法的代码如下：基于先序遍历的算法：int WPL(BiTree root)return wpl_PreOrder(root，0)；int wpl PreOrder(BiTree root，int deep)static int wpl=0；定义一个 static 变量存储 wplif(root-lchild=NuLLroot-lchild=NULL) 若为叶结点，累积 wplwpl+=deep*root-weight，if(root-ichiid!；NuLL)若左子树不空，对左子树递归遍历wpl_PreOrder(root-ichild，deep+1)，if(root-r
30、chiidI=NULL)若右子树不空，对右于树递归遍历wpl_PreOrder(root-rchild，deep+1)；return wpl；基于层次遍历的算法：#define MaxSize 100设置队列的最大容量int wpl LevelOrder(BiTree root)BiTree qMaxSize；声明队列， end1 为头指针， end2 为尾指针int end1，end2，队列最多容纳 MaxSize-1 个元素end1=end2=0；头指针指向队头元素，尾指针指向队尾的后一个元素int wpl=deep=0；初始化 wpl 和深度BiTree lastNode；lastNod
31、e 用来记录当前层的最后一个结点BiTree newlastNode； newlastNode 用来记录下一层的最后一个结点lastNode=root；lastNode 初始化为根结点newlastNode=NULL； newlastNode 初始化为空qend2+=root；根结点入队while(end1!=end2)f层次遍历，若队列不空则循环BiTree t=qend1+；拿出队列中的头一个元素if(t-ichild=NULL&t-lchild=NULL)wpl+=deep*t-weight ；若为叶结点，统计 wplif(t-ichild!=NULL) 若非叶结点把左结点入队qend2+=t-ichild ；newlastNode=t-ichiid ；并设下一层的最后一个结点为该结点的左结点if(t-rchild!=NULL)处理叶结点qend2+=t-rchild ；newlastNode=t-rchild；if(t=lastNode)若该结点为本层最后一个结点，更新 lastNodelastNode=newlastNode；deep+=1；层数加 1return wpl；返回 wpl【试题解析】 考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。【知识模块】 数据结构
