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

公众号【研池大叔】，免费分享考研干货！

全国硕士研究生入学统一考试

计算机科学与技术学科联考

2022全国硕士研究生招生考试计算机学科专业基础试题参考答案

一、单项选择题

01.B02.D03.B04.C05.D06.D07.B08.D

09.D10.A11.D12.A13.B14.A15.C16.A

17.C18.B19.D20.A21.C22.C23.D24.A

25.C26.B27.C28.D29.A30.D31.B32.A

33.B34.C35.B36.D37.B38.C39.D40.B

01.B。【解析】当外层循环的变量z■取不同值时，内层循环就执行多少次，因此总循环次数为力

的所有取值之和。假设外层循环共执行后次，当2=1,2,4,8,…,21(2])«2左)时，内层循

环执行i次，因此总循环次数7=1+2+4+8+…+21=2左-1,即T2〃，时间复杂度为

O(n)o

02.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的满三叉树的结点

12345

数=30+3J32+33+34=121,高度为6的满三叉树的结点数=3°+3+3+3+3+3=3640

由于三叉树T的结点数为244,121v244V364,因此T的高度至少为6。

05.D。【解析】可以画一个简单的特例来证明。图1是满足条件的二叉树TL图2是满足条件的

二叉树T2,结点中有值表示这个结点是编码字符。T1和T2的结点数不同，A错误。T1的高

度等于T2的高度，B错误。出现频次不同的字符在T1中也可能处于相同的层，C错误。对

于定长编码集，所有字符一定都在T2中处于相同的层,而且都是叶子结点。

1

公众号【研池大叔】，免费分享考研干货！

06.D。【解析】注意，V是图的边数，E是图的顶点数。A和B明显错误，如图1所示，