全国硕士研究生入学统一考试计算机科学与技术学科联考2022全国硕士研究生招生考试计算机学科专业基础试题参考答案一、单项选择题01.B02.D03.B04.C05.D06.D07.B08.D09.D10.A11.D12.A13.B14.A15.C16.A17.C18.B19.D20.A21.C22.C23.D24.A25.C26.B27.C28.D29.A30.D31.B32.A33.B34.C35.B36.D37.B38.C39.D40.B01.B。【解析】当外层循环的变量z■取不同值时，内层循环就执行多少次，因此总循环次数为力的所有取值之和。假设外层循环共执行后次，当2=1,2,4,8,…,21(2"]<)«2左)时，内层循环执行i次，因此总循环次数7=1+2+4+8+…+21=2左-1,即"T<2〃，时间复杂度为O(n)o02.D。【解析】通过模拟出入栈操作，可以判断入栈序列in和出栈序列。ut是否合法。因此，已知in序列可以判断out序列是否为可能的出栈序列;已知out序列也可以判断in序列是否为可能的入栈序列，A和B错误。如果每个元素入栈后立即出栈，则in序列和。ut序列相同，C错误。如果所有元素都入栈后才依次出栈，则in序列和out序列互为倒序，D正确。03.B。【解析】对于此类题，每种情况只需举出一个反例即可。如图1所示，q是p的双亲，中序遍历序列为｛p,qb，I可能。如图2所示，q是p的右孩子，中序遍历序列为｛p,q｝,II可能。如图4所示，q是p的双亲的双亲，中序遍历序列为｛x,p,q｝,IV可能。如图3所示，q是p的右兄弟，F是q和p的父结点，中序遍历要求先遍历左子树,再访问根结点,最后遍历右子树，因此一定先访问p,再访问F,最后访问q,p和q不可能相邻出现，皿不可能。04.Co【解析】高度一定的三叉树中结点数最多的情况是满三叉树。高度为5的满三叉树的结点数=30+3J32+33+34=121,高度为6的满三叉树的结点数=3°+31+32+33+34+35=3640由于三叉树T的结点数为244,121v244V364,因此T的高度至少为6。05.D。【解析】可以画一个简单的特例来证明。图1是满足条件的二叉树TL图2是满足条件的二叉树T2,结点中有值表示这个结点是编码字符。T1和T2的结点数不同，A错误。T1的高度等于T2的高度，B错误。出现频次不同的字符在T1中也可能处于相同的层，C错误。对于定长编码集，所有字符一定都在T2中处于相同的层,而且都是叶子结点。106.D。【解析】注意，V是图的边数，E是图的顶点数。A和B明显错误，如图1所示，|V|＜|E|,但图G不连通;如图2所示，|V|＞|E|,但图G不连通。如图3所示,在无向图中至少要有|V|-1个顶点才可能连通，顶点数小于IM-1一定不可能连通，C错误，D正确。c的时间余量=vl(3)_ve(2)-l=5_2_l=2,g的时间余量==vl(6)-ve(3)-1=12-5-1=6,h的时间余量=vl(5)-ve(4)-l=11-8-1=2,j的时间余量=vl(6)-ve(5)-1=12-9-1=2,时间余量最大的活动是g。08.Do【解析】在5阶B树中，除根结点外的非叶结点的关键字数左需要满足24后44。当被删关键字x不在终端结点(最低层非叶结点)时，可以用x的前驱(或后继)关键字y来替代x,然后在相应结点中删除y。情况①：删除260,将其前驱H0放入260处，删除110后的结点＜100＞不满足5阶B树定义，从左兄弟中借85,将85放入根中，将根中的90移入结点＜100＞变为＜90，100＞。情况②：删除260,将其后继280放入260处，结点＜300不满足5阶B树定义且左右兄弟都不够借，结点＜300＞可以和左兄弟＜100,110＞以及关键字280合并成一个新的结点＜100,110,280,300＞。情况③：在情况②中，结点＜300＞也可以和右兄弟＜400,500＞以及关键字350合并成一个新的结点＜300,350,400,500＞。综上，T1根结点中的关键字序列可能是＜60,85,110,350＞或＜60,90,350或＜60,90,280,仅D不可能。09.Do【解析】填装因子越大，说明哈希表中存储的元素越满，发生冲突的可能性就越高，导致平均查找长度越大。散列函数、冲突解决策略也会影响发生冲突的可能性。I、ILin都正确。10.Ao【解析】送分概念题。王道书对归并的定义原话是“归并的含义是将两个或两个以上的有序表合并成一个新的有序表”，而二路归并是将两个有序表合并为一个新的有序表。11.D。【解析】直接插入排序和快速排序的特点如下表所示。适合初始序列情况适合元素数量空间复杂度稳定性直接插入排序大部分元素有序较少0(1)稳定快速排序基本无序较多O(log2九)不稳定2可见，I、n、in、iv都是采用直接插入排序而...
