2022年计算机408统考真题解析.docx

会员专享推荐 · 你可能也用得上更多

开通会员，畅读全站文档

本篇文档已为你保留

本篇文档价值 ~~¥35.00~~会员免费解锁

全文不限次阅读，剩余内容即刻解锁
高速下载通道，免排队、无等待
专属客服 1 对 1 答疑，优先响应
每日赠送下载券，本篇文档免费送

有 86 篇商业计划书正在上传

下载原文档

全国硕士研究生入学统一考试计算机科学与技术学科联考2022全国硕士研究生招生考试计算机学科专业基础试题参考答案一、单项选择题01.B 02.D 03.B 04.C 05.D 06.D 07.B 08.D 09.D 10.A 11.D 12.A 13.B 14.A 15.C 16.A 17.C 18.B 19.D 20.A 21.C 22.C 23.D 24.A 25.C 26.B 27.C 28.D 29.A 30.D 31.B 32.A 33.B 3 4.C 35.B 36.D 37.B 38.C 39.D 40.B 01.B。【解析】当外层循环的变量i取不同值时，内层循环就执行多少次，因此总循环次数为i的所有取值之和。假设外层循环共执行k次，当i=1,2,4,8,…,2-¹(2k-¹<n≤2*)时，内层循环执行i次，因此总循环次数T=1+2+4+8+…+2k-¹=2k-1,即n<T<2n,时间复杂度为O(n)。02.D。【解析】通过模拟出入栈操作，可以判断入栈序列in和出栈序列out是否合法。因此，已知in序列可以判断out序列是否为可能的出栈序列；已知out序列也可以判断in序列是否为可能的入栈序列，A和B错误。如果每个元素入栈后立即出栈，则in序列和out序列相同，C错误。如果所有元素都入栈后才依次出栈，则in序列和out序列互为倒序，D正确。03.B。【解析】对于此类题，每种情况只需举出一个反例即可。如图1所示，q是p的双亲，中序遍历序列为{p,q},I可能。如图2所示，q是p的右孩子，中序遍历序列为{p,q},Ⅱ可能。如图4所示，q是p的双亲的双亲，中序遍历序列为{x,p,q},IV可能。如图3所示，q是p的右兄弟，F是q和p的父结点，中序遍历要求先遍历左子树，再访问根结点，最后遍历右子树，因此一定先访问p,再访问F,最后访问q,p和q不可能相邻出现，Ⅲ不可能。图1图2图3图4 04.C。【解析】高度一定的三叉树中结点数最多的情况是满三叉树。高度为5的满三叉树的结点数=3⁰+3¹+3²+3³+3⁴=121,高度为6的满三叉树的结点数=3⁰+3¹+3²+3³+3⁴+3⁵=364。由于三叉树T的结点数为244,121<244<364,因此T的高度至少为6。05.D。【解析】可以画一个简单的特例来证明。图1是满足条件的二叉树T1,图2是满足条件的二叉树T2,结点中有值表示这个结点是编码字符。T1和T2的结点数不同，A错误。T1的高度等于T2的高度，B错误。出现频次不同的字符在T1中也可能处于相同的层，C错误。对于定长编码集，所有字符一定都在T2中处于相同的层，而且都是叶子结点。图1图2 06.D。【解析】注意，V是图的边数，E是图的顶点数。A和B明显错误，如图1所示，V||<E|,但图G不连通；如图2所示，VI>E,但图G不连通。如图3所示，在无向图中至少要有|V|-1个顶点才可能连通，顶点数小于IVI-1一定不可能连通，C错误，D正确。图1图2图3 07.B。【解析】在AOE网中，活动的时间余量=结束顶点的最迟开始时间-开始顶点的最早开始时间-该活动的持续时间。根据关键路径算法得到下表。结点编号。