2022408真题解析优质文档.docVIP

2022年408真题解析

单选题

下列程序段的时间复杂度是（）。

intsum=0;

for(inti=1;in;i*=2)

for(intj=0;ji;j++)

sum++;

A.?O(logn)

B.?O(n)

C.?O(nlogn)

D.?O(n2)

解答：本题为多层循环中嵌套循环指针相关类型题，且指针变化非线性，所以只能用定义法求解，用?r表示执行的轮次，则有?i=2r?1?：

本题选B。

这道题难度非常大，只能用定义法。归根结底基础还是要打扎实，用定义法求解永远不会出错。

给定有限符号集S，in和out均为S中所有元素的任意排列。对于初始为空的栈ST，下列叙述中，正确的是（）。

对于入栈和出栈，关于入栈序列S1和出栈序列S2的说法正确的是：

A.若in是ST的入栈序列，则不能判断out是否为其可能的出栈序列

B.若out是ST的出栈序列，则不能判断in是否为其可能的入栈序列

C.若in是ST的入栈序列，out是对应in的出栈序列，则in与out一定不同

D.若in是ST的入栈序列，out是对应in的出栈序列，则in与out可能互为倒序

解答：

本题考察对栈的理解。简化下表述如下：

A.入栈序列不能推导出栈序列

B.出栈序列不能推导入栈序列

C.入栈序列和出栈序列一定不同

D.入栈序列和出栈序列可以相反

题目意思为给定?n?个互不相同的元素，这些元素组成集合S。

如果入栈序列由?n?个互不相同的元素组成，出栈序列有??（卡特兰数）种可能，而且入栈顺序推导出栈顺序可逆。

给定入栈序列，只要判断给定的出栈序列是否为??中的一个序列，所以A错误。当然也可以不必要这复杂，根据入栈序列检查出栈序列是否符合栈先进后出的性质。

同理，给定出栈序列，只要判断给定的入栈序列是否为??中的一个序列，B错误。当然也可以不必要这复杂，根据入栈序列检查出栈序列是否符合栈先进后出的性质。

关于C选项，如果每个元素入栈后马上出栈，得到的出栈序列与入栈序列完全相同，所以C错误。也可以举特例，假设入栈序列只有一个元素，得到的入栈序列和出栈序列一定相同。

关于D选项，如果序列元素全部入栈后再依次出栈，得到的出栈序列与入栈序列完全相反，所以D正确。

本题选D。

评：这道题主要考察栈先进后出的特性。408如果加大难度，会考察入栈序列长度大于栈深度的情况，即序列元素不可能全部入栈后再依次出栈，只能部分入栈即需要执行出栈。

若结点p与q在二叉有哪些信誉好的足球投注网站树T中的中序遍历中相邻，且p在q之前，则下列p与q的关系中，不可能的是（）。

I.q是p的双亲

II.q是p的右孩子

III.q是p的右兄弟

IV.q是p的双亲的双亲

A.仅I

B.仅III

C.仅II、III

D.仅II、IV

解答：

由题意，p是q的前驱，q是p的后继，则p是q的左子树的最右结点，或者q是p的右子树的最左结点。

很明显，p和q只存在父子和祖孙关系，不存在兄弟关系。反证法也可以证明，假设p和q为兄弟，则中序遍历为左右根，p个q的双亲结点必然位于p和q之间，与“结点p与q在二叉有哪些信誉好的足球投注网站树T中的中序遍历中相邻”的题目条件矛盾，所以p和q为兄弟关系不成立，III错误。

下面分别讨论：

情况一：p是q的左子树的最右结点，那么p一定没有右孩子。此时p是q的子孙结点，其中包含p是q的左孩子结点的情况，此时q是p的双亲，I正确。也包含q是p的祖父结点的情况，此时q是p的双亲的双亲，IV正确。

情况二：q是p的右子树的最左结点，那么q一定没有左孩子。此时q是p的子孙结点，其中包含q是p的右孩子结点的情况，此时q是p的双亲，II正确。

综上，只有III错误，注意，这里选不可能的。

本题选B。

若三叉树T有244个结点（叶结点的高度为1），则T的高度至少是（）。

A.4

B.5

C.6

D.7

解答：

关键词“至少”，很容易想到完全二叉树，设树高?h?：

本题选C。

对于任意给定的含?n(n2)?个字符集的有限集S，用二叉树表示S的哈夫曼编码集合定长编码集，分别得到二叉树T1和T2。下列叙述中，正确的是（）。

A.T1和T2的结点数相同

B.T1的高度大于T2的高度

C.出现频次不同的字符在T1中处于不同的层

D.出现频次不同的字符在T2中处于相同的层

解答：

本题多出了一个概念，等长编码。等长编码是一种简单且译码具有唯一性的编码方式，这种编码方式的特点是每个字符的编码长度相同。

由哈夫曼编码和等长编码两种方式生成的二叉树T1和T2。T1为哈夫曼树，T2为等长编码树。

但是哈夫曼树考虑了词频，需要用到前缀编码，按照词频从大到小排序，一般词频越高的编码长度越短。

本题选D。

对于无向图?G=(V,E)?