《计算机专业基础综合历年真题试卷汇编1.pdf》由会员分享，可在线阅读，更多相关《计算机专业基础综合历年真题试卷汇编1.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！计算机专业基础综合历年真题试卷汇编 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 解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次
2、序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d 为入栈次序，则出栈序列的个数为?”，对于n 个不同元素进栈，出栈序列的个数为 C 2n n=14。3.假设栈初始为空，将中缀表达式 a b+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是_。（分数：2.00）A.+(*-B.+(-*C.+(*-*D.+-*解析：解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a若为(，入栈；b若为)，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删
3、除(；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 i，树中结点总数为N，则树中各
4、结点的度之和等于 N-1，即 N=1+N 1+2N 2+3N 3+4N 4=N 0+N 1+N 2+N 3+N 4，根据题设中的数据，即可得到N 0=82，即树 T 的叶结点的个数是 82。5.已知一棵完全二叉树的第6 层(设根为第1 层)有8 个叶结点，则该完全二叉树的结点个数最多是_。（分数：2.00）A.39 B.52 C.111 D.119 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！解析：解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉
5、树的高度可能为 6 或 7，显然树高为 7时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 82=16 个叶结点，故完全二叉树的结点个数最多为(2 7-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，
6、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 解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵
7、二叉树，所以题意相当于“以序列a，b，c，d 为入栈次序，则出栈序列的个数为?”，对于n 个不同元素进栈，出栈序列的个数为 C n+1 n=14。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 或在序列首或在序列
8、尾，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 为
9、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 对应的查找树
10、不是二叉排序树，因为在 91 为根的左子树中出现了比 91 大点的结点 94。12.在任意一棵非空二叉排序树 T 1 中，删除某结点 v 之后形成二叉排序树 T 2，再将 v 插入 T 2 形成二叉排序树 T 3。下列关于 T 1 与 T 3 的叙述中，正确的是_。若 v 是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v 是 T 1 的叶结点，则 T 1 与 T 3 相同 若 v 不是 T 1 的叶结点，则 T 1 与 T 3 不同 若v 不是 T 1 的叶结点，则 T 1 与 T 3 相同（分数：2.00）A.仅、B.仅、C.仅、D.仅、解析：解析：在一棵二叉排序树中删除一个结点后
11、再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。13.下列二叉排序树中，满足平衡二叉树定义的是_。（分数：2.00）A.B.C.D.解析：解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余 3 个选项均可以找到不符合该条件的结点。在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。14.在下图所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37所在结
12、点的左、右子结点中保存的关键字分别是_。（分数：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，则该平衡二叉树的结点总数为_。（分数
13、：2.00）A.10 B.20 C.32 D.33 解析：解析：所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为 N、左右子树的高度分别为 N-1和 N-2、所有非叶结点的平衡因子均为 1 的平衡二叉树，总结点数的公式为：C N=C N-1+C N-2+1，C 1=1，C 2=2，C 3 2+1+1=4，可推出 C 6=20。画图法：先画出 T 1 和T 2；然后新建一个根结点，连接 T 2、T 1 构成 T 3；新建一个根结点，连接 T 3、T 2 构成 T 4；依此类推，直到画出 T 6，可知 T 6 的结点数为 20。排除法：对于选项 A，高度为
14、 6、结点数为 10 的树怎么也无法达到平衡。对于选项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.现有一棵无重复关键字
15、的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是_。（分数：2.00）A.根结点的度一定为2 B.树中最小元素一定是叶结点 C.最后插入的元素一定是叶结点 D.树中最大元素一定是无左子树 解析：解析：只有两个结点的平衡二叉树的根结点的度为 1，A 错误。中序遍历后可以得到一个降序序列，树中最小元素一定无左子树(可能有右子树)，因此不一定是叶结点，B 错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C 错误。18.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系
16、是_。父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系（分数：2.00）A.只有 B.和 C.和 D.、和 解析：解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点 v 就变成结点 u 第一个孩子的右孩子，符合要求。情形结点 u 和 v 是兄弟结点的关系，但二者之欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！中还有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点 u
17、的右孩子，符合要求。情形：若结点 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 解析：解析：树转换为
18、二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前 115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。20.将森林 F 转换为对应的二叉树 T，F 中叶结点的个数等于_。（分数：2.00）A.T中叶结点的个数 B.T中度为 1 的结点个数 C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数 解析：解析：将森林转化为二叉树即相当于用孩子兄弟表示法表示森林
19、。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F 中叶结点的个数就等于 T 中左孩子指针为空的结点个数，选 C。此题还可以通过一些特例来排除 A、B、D 选项。21.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是_。（分数：2.00）A.B.C.D.解析：解析：题中所给二叉树的后序序列为d，b，c，a。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无
20、右子树，右链域指向其后继结点 a。故选 D。22.若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是_。（分数：2.00）A.X的父结点 B.以 Y 为根的子树的最左下结点 C.X的左兄弟结点 Y D.以 Y 为根的子树的最右下结点 解析：解析：根据后序线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知 X 结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！23.若对如下
21、的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是_。（分数：2.00）A.e、c B.e、a C.d、c D.b、a 解析：解析：线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在 x 左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a，选 D。24.对 n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是 _。（分数：2.00）A.该树一定是一棵完全二叉树 B.树中一定没有度为1 的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不
22、小于下一层任一结点的权值 解析：解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1 的结点，B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点 P 的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点 P 的左、右子树根结点处于同层的结点中，若存在权值大于结点 P 权值的结点 Q，那么结点 Q 的兄弟结点中权值较小的一个应该与结点 P 作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。25.5 个字符有如下 4 种编
23、码方案，不是前缀编码的是_。（分数：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.2
24、4，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.和 解析：解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次(出度和入度)，故
25、所有顶点的度之和为边数的两倍，正确。n 个顶点、n-1 条边可以构成无向连通图，比如树，错误。顶点数为 N(N1)的无向完全图中不存在度为 1 的顶点，错误。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！二、综合应用题(总题数：3，分数：8.00)28.综合应用题 41-47小题。_ 解析：29.已知有 6 个顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。请写出图 G 的邻接矩阵 A。（分数：2.00）_ 正确答案：(正确答案：在上三角矩阵 A66中，第 1 行至第 5 行主对
26、角线上方的元素个数分别为 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）_ 正确
27、答案：(正确答案：算法的基本设计思想：基于先序递归遍历的算法思想是用一个 static变量记录、wpl，把每个结点的深度作为递归函数的 一个参数传递，算法步骤如下：若该结点是叶结点，那么变量wpl加上该结点的深度与权值之积；若该结点是非叶结点，那么若左子树不为空，对左子树调用递归算法：若右子树不为空，对右子树 调用递归算法，深度参数均为本结点的深度参数加 1；最后返回计算出的 wpl即可。基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶结点时，累计 wpl；当遍历到非叶结点时，把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增 1；队列空时遍历结束，返回
28、 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 PreOrde
29、r(BiTree root，int deep)static int wpl=0；定义一个 static变量存储 wpl if(root-lchild=NuLLroot-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
30、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；lastNode用来记录当前层的最后一个结点 BiTree newlastNode；newlastNode用来记录下一层的最后一个结点 lastNode=root；lastNode初始化为根结
31、点 newlastNode=NULL；newlastNode初始化为空 qend2+=root；根结点入队 while(end1!=end2)f层次遍历，若队列欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！不空则循环 BiTree t=qend1+；拿出队列中的头一个元素 if(t-ichild=NULL&t-lchild=NULL)wpl+=deep*t-weight；若为叶结点，统计 wpl if(t-ichild!=NULL)若非叶结点把左结点入队 qend2+=t-ichild；newlastNode=t-ichiid；并设下一层的最后一个结点为该结点的左结点 if(t-rchild!=NULL)处理叶结点 qend2+=t-rchild；newlastNode=t-rchild；if(t=lastNode)若该结点为本层最后一个结点，更新 lastNode lastNode=newlastNode；deep+=1；层数加 1 return wpl；返回 wpl)解析：解析：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。