计算机基础综合历年真题汇编1(总分：62.00，题型时间： 90分钟)1。单项选择题(总题数：27，分值：54.00)1。单项选择题1-40小题。在以下每道题给出的四个选项中，只有一个选项是最符合题型要求的。(分数：2.00)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _(分数：2.00)A.13B.14 C.15D.16解析：解析：根据二叉树的前序遍历和中序遍历的递归算法中递归工作栈的状态变化，得出前序序列和中序序列的关系，等价于前序序列为堆叠顺序，中序序列为堆叠顺序。因为前序序列和中序序列可以唯一确定一棵二叉树，所以标题相当于“取序列A、B、C、D为堆叠顺序，则堆叠序列个数为”。对于堆叠的n个不同元素，堆叠序列的数量是C=14。3.2n。假设堆栈初始为空，在将中缀表达式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.41B.82 C.113D.122解析：解析：设树中度数为i(i=0，1，2，3，4)的节点个数为N，树中节点总数为N，则树中每个节点的度数I之和等于N-1，即N=1N23N。05.已知一棵完全二叉树的第6层有8个叶节点(设根为第1层)，那么该完全二叉树的最大节点数是_ _ _ _ _ _ _ _ _。(得分：2.00)A.39B.52C.111 D.119分析：分析：完全二叉树除了最底层右侧缺失部分叶节点外，其余部分都小于完全二叉树，而最后一层以上是完全二叉树，只有最后两层有叶节点。如果第6层有叶节点，完整二叉树的高度可能是6或7，显然树高为7时节点更多。如果第6层有8个叶节点，前6层是全二叉树，而第7层缺少82=16个叶节点，那么完整的7棵全二叉树的最大节点数是(2 -1)-16=111个节点。6.如果一棵完整的二叉树有768个节点，那么二叉树的叶节点数是_ _ _ _ _ _。(得分：2.00)A.257B.258C.384 D.385解析：解析：根据一棵完全二叉树的性质，最后一个分支节点的序号为=384，所以叶节点数为768-384=384。7.给定的二叉树如下图所示。设n代表二叉树的根，l代表根节点的左子树，r代表根节点的右子树。如果遍历的节点序列为3，1，7，5，6，2，4，则遍历方式为_ _ _ _ _ _ _ _ _。(得分：2.00)A.LRNB.NRLC.RLND.KNL 分析：分析遍历的节点序列，可以看出根节点是在中间访问的，而右边的子树节点在左边的子树之前，即遍历方式是RNL。本题考察的遍历方法并不是二叉树的三种基本遍历方法。对于考生来说，掌握遍历的思想很重要。8.前序序列为A、B、C、D的不同二叉树的个数是_ _ _ _ _ _ _ _ _。

(得分：2.00)A.13B.14 C.15D.16解析：解析：根据二叉树的前序遍历和中序遍历的递归算法中递归工作栈的状态变化，得出前序序列和中序序列的关系相当于前序序列为堆叠顺序，中序序列为堆叠顺序。因为前序序列和中序序列可以唯一确定一棵二叉树，所以标题相当于“取序列A、B、C、D为堆叠顺序，则堆叠序列个数为”。对于堆叠的n个不同元素，堆叠序列的数量是C=14。N 19。如果二叉树的一阶遍历序列和二阶遍历序列分别是1，2，3，4和4，3，2，1，那么二叉树的中阶遍历序列不会是_ _ _ _ _ _。(得分：2.00)A.1，2，3，4B.2，3，4，1C.3，2，4，1 D.4，3，2，1分析：前序序列为NLR，后序序列为LRN。因为前同步码序列和后同步码序列正好相反，所以不可能有一个。1是根节点，因为根节点只能有左子节点(或右子节点)。因此，在中间序列中，1要么在序列的开头，要么在序列的结尾，ABCD满足要求。只考虑以1的子节点2为根节点的子树，它只能有左子(或右子)。因此，在中序序列中，ABD在序列的开头或结尾都满足要求。10.如果二叉树的第一个遍历序列是A，E，B，D，C，第二个遍历序列是B，C，D，E，A，那么根节点的子节点是_ _ _ _ _ _。(得分：2.00) A .只有e B .有E，bC。还有E，cD。无法确定分析：分析：前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中节点的祖先关系：当两个节点的前序序列为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，35C.21，89，77，29，36，38D.12，25，71，12，12，12，14，12，12，14，12。在任一非空二叉排序树T中，删除一个节点v形成二叉排序树T，然后将v插入T形成二叉122排序树T.下列关于T和T的说法中，正确的是_ _ _ _ _ _ _ _ _。I .如果v是t的叶节点，则t不同于T313113。二。如果v是t的叶节点，则t与t. iii相同。如果v不是t的叶节点，则t不同于t. iv。如果113113v不是T的叶节点，那么T与T 113相同(得分：2.00)a . Only，B. Only，C. Only，d . Only，解析：在二叉排序树中删除一个节点后，将该节点插入到二叉排序树中。如果被删除的节点是叶节点，那么在插入该节点后，后续的二叉排序树将被删除。如果被删除的节点不是叶节点，那么再次插入这个节点后，后面的二叉树会发生变化，不完全一样。13.下列二叉排序树中，满足平衡二叉树定义的是_ _ _ _ _ _ _ _ _。(得分：2.00)A.B. C.D解析：解析：根据平衡二叉树的定义，任意节点的左右子树高度差的绝对值不超过1。剩下的三个选项可以找到不满足这个条件的节点。在做题过程中，如果答案不明显，可以先写出每个非叶节点的平衡因子，再做判断。14.在下图所示的平衡二叉树中，插入关键字48，得到新的平衡二叉树。在新的平衡二叉树中，关键字37所在的节点的左右子节点中存储的关键字是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _的关键字

(得分：2.00)A.13，48B.24，48C.24，53 D.24，90分析：插入48后，这个二叉树的根节点的平衡因子从-1变为-2，这是由于在最小不平衡子树的根节点的右子树(R)的左子树(L)中插入了一个新节点。调整后，关键字37所在节点的左右子节点中存储的关键字分别为24和53。15.如果平衡二叉树的高度是6，所有非叶节点的平衡因子都是1，那么平衡二叉树的节点总数是_ _ _ _ _ _ _ _ _。(得分：2.00)A.10B.20 C.32D.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-212361T；然后创建一个新的根节点，连接T和T形成T；创建一个新的根节点，连接T和T形成T；2213324等等直到画出T，说明T的节点数是20。排除：对于选项A，高度为6，节点数为10的树66达不到平衡。对于选项C，当有很多节点时，考虑更极端的情况，即完整二叉树中只有32个节点，只有第6层最左边的叶子。虽然满足了平衡的条件，但是很明显删除一些节点仍然不会影响平衡，最少的节点不是这样的。d同样是错的。可能只有B. 16。如果将关键字1、2、3、4、5、6、7依次插入到初始为空的平衡二叉树T中，那么T中平衡因子为0的分支节点数为_ _ _ _ _ _。(得分：2.00)A.0B.1C.2D.3 解析：用7个关键词构建一棵平衡二叉树T，平衡因子为O的分支节点数为3。构建的平衡二叉树如下图所示。施工和调整的过程如下：17。有一个平衡二叉树(AVL树)没有重复的关键字，按中间顺序遍历可以得到一个降序。下列关于平衡二叉树的说法中，正确的是_ _ _ _ _ _ _ _ _。(得分：2.00) A .根节点的度必须是2B。树中最小的元素一定是叶节点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在两个节点最左边父节点的两个子树中，不能出现在同一路径中。根据树和二叉树之间的转换规则，将这四种情况转换为树种节点之间的关系。(1)在原树中，u是v的父节点的父节点；(2) U是树中V的父节点；(3) U是树中V的父节点的兄弟；(4) U和V是树上的兄弟。因此，I和II是正确的。

19.已知一棵有2011个节点的树有116个叶节点，该树对应的二叉树中没有右子的节点数是_ _ _ _ _ _ _ _ _。(得分：2.00)A.115B.116C.1895D.1896 解析：树转换成二叉树时，树中每个分支节点的所有子节点中最右边的子节点没有右子，根节点转换后没有右子。因此，对应二叉树中没有右子的节点数=分支节点数1=2011-。通常这个问题要用特殊的方法来解决。假设问题含义中的树具有下图所示的结构，对应的二叉树中只有前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 .左同胞节点YD。Y根子树分析的右下节点：根据后序线索二叉树的定义，X节点是一个叶子节点，有一个左兄弟，所以这个节点是右子节点。通过使用后序遍历，可以知道X节点的后序后继是它的父节点，也就是。为了更形象，在解题过程中可以画以下草图。23.如果下面的二叉树是按中间顺序排列的， 节点X的左右线索分别指向节点_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _和节点_ _ _ _ _ _ _ _ _ _ _ _ _ _之间_ _ _ _(得分：2.00)A.e，cB.e，aC.d，cD.b，a 分析：线索二叉树的线索实际上指向对应遍历序列的特定节点的前任节点和后继节点，所以先写出二叉树的中序遍历序列：edbxac。 在中序遍历中，X左边和右边的字符是中序线索的左边和右边。24.为n(n2)个不同权重的字符构造一个霍夫曼树。下列关于霍夫曼树的说法中，错误的是_ _ _ _ _ _ _。(得分：2.00) A .树必须是完全二叉树 B .树中不能有度为1的节点。c .树中权重最小的两个节点必须是兄弟节点。d .树中任何非叶节点的权重不得小于下一级任何节点的权重。解析：霍夫曼树是一种加权路径长度最小的二叉树，不一定是完全二叉树。霍夫曼树中没有度数为1的节点，B是正确的；构造霍夫曼树时，先选取两个权值最小的节点作为左右子树，构造新的二叉树，C正确；Huffman树中任意非叶节点P的权重是其左右子树根的权重之和，且其权重不小于其左右子树根的权重。如果有一个节点Q与节点P的左右子树根在同一层，那么节点Q的具有较小权重的兄弟节点应该构造一个新的二叉树w

25.5字符有以下四种编码方案。不按前缀编码的是_ _ _ _ _ _ _ _ _。(得分：2.00)A.01，0000，0001，001，1B.011，000，001，010，011，100D.0，100，110，1110选项D中的代码110是代码1100的前缀，违反了前缀编码的规则，所以D不是前缀编码。26.以下选项分别给出了从根到两个叶节点的路径上的权重序列。能属于同一个霍夫曼树的是_ _ _ _ _ _ _ _ _。(得分：2.00)A.24，10，5和24，10，7B.24，10，5和24，12，7C.24，10，10和24，14，11D.24，10，5和24，14，6 分析：仅以分析选项A为例：如果两个十属于两个不同的子树，则根的权重不等于其子树的权重之和，不一致；如果两个十属于同一个子树，则权重不等于其两个子树(叶节点)的权重之和，这是不一致的。选项b和c以同样的方式排除。27.下列关于无向连通图特征的说法中，正确的是_ _ _ _ _ _ _ _。.所有顶点的度数之和是偶数。边数大于顶点数减1。至少有一个顶点的度为1(得分：2.00) A .仅b .仅c .和d .和分析：每条边连接两个节点，计算顶点的度和时每条边计算两次(出度和入度)。n个顶点和n-1条边可以形成一个无向连通图，比如一棵树。二错误。顶点数为N(N1)的无向完全图中不存在度数为1的顶点，为错误。二。综合应用题(总题数：3，分值：8.00)28。综合应用题41-47。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _请写出图g的邻接矩阵A。(分数：2.00) _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _利用“平移”的思想，将前5、4、3、2、1元素移到矩阵对角线(“0”)的右行。 所以图G的邻接矩阵A如下图所示。)解析：解析：考察上三角矩阵的存储。二叉树的加权路径长度(WPL)是二叉树中所有叶节点的加权路径长度的总和。给定一个二叉树T，存放在一个二叉链表中，节点结构如下：叶子节点的权值字段保存节点的非负权值。设root为T的根节点的指针，请为T设计WPL算法，要求：(得分：6.00)(1)。给出了算法的基本设计思想；(分数：2.00)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Wpl，每个节点的深度作为递归函数的参数传递。算法步骤如下：如果节点是叶节点，变量wpl加上节点的深度和权重的乘积；如果节点是非叶节点，那么如果左子树不为空，调用左子树上的递归算法；如果右子树不为空，调用右子树上的递归算法，深度参数为本节点所有深度参数加1；最后，返回计算出的wpl。基于层次遍历的算法思想是用队列进行层次遍历，记录当前层数。当遍历到叶节点时，wpl是累积的；当遍历到非叶节点时，将该节点的子树添加到队列中；当一个节点是该层的最后一个节点时，层数增加1；队列遍历结束，返回wpl。

)解析：(2)使用C或C语言，给出二叉树节点的数据类型定义；(分数：2.00)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ structBiTNode * l child，* rchild}BiTNode，* BiTree)分析：(3)根据设计思路，用C或C语言描述算法，重点给出注释。(分数：2.00)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ } int wpl PreOrder(BiTree root，int deep){ static int wpl=0；//定义一个静态变量存储WPL IF(root-> l child==null & & root-> l child==null)//如果是叶节点，累加WPL WPL=deep * root-> weight，if (root-> ichiid！null)//如果左子树不为空，递归遍历WPL _ preorder(root-> I chid，deep1)，If(root-> rchiidi=null)//如果右子树不为空，递归遍历WPL _ preorder (root-> rchild，deep 1)到右子树；返回wpl} 基于层次遍历的算法：# define maxsize 100//设置队列int WPL级别顺序的最大容量(bitree root){ bitree q[maxsize]；//声明队列，end1是头指针，end2是尾指针int end1，end2，//队列最多能容纳MaxSize-1个元素，end 1=end 2=0；//头指针指向队列头的元素，尾指针指向队列尾的下一个元素，int wpl=deep=0；//初始化wpl和深度BiTreelastNode；//lastnode用于记录最后一个节点BiTree newlastNode当前层的；//NewLastNode用于记录下一层的最后一个节点，lastNode=root；//lastnode初始化为根节点newlastNode=NULL；//NewLastNode初始化为null Q[end 2]=root；//根节点在while(end1！=end 2)f//层次遍历，如果队列不为空，循环bitree t=q[end 1]；//取出队列中的第一个元素if(t-> I child==nullt-> l child==null){ wpl=deep * t-> weight；}//如果是叶节点，则计数WPLIF (T-> I Child！=null){//如果是非叶节点，将左节点Q [end2]=t-> iChild入队；new last node=t-> ichi id；}//并将下一层的最后一个节点设置为左节点if (t-> rchild！=null){//处理叶节点q[end 2]=t-> r chid；new last node=t-> rchild；} If(t==lastNode){//如果该节点是本层的最后一个节点，则更新lastNode lastNode=newlastNode；深度=1；//层数加1}}返回wpl；//Return wpl})解析：解析：检查一棵二叉树的加权路径长度。二叉树的加权路径长度是每个叶节点的深度和权重的乘积之和。可以通过一阶遍历或者层次遍历来解决问题。