2022年408计算机学科专业基础真题解析

一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）

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

int sum=0;

for(int i=1;i<n;i*=2)

for(int j=0;j<i;j++)

sum++;

A.O(logn)

B.O(n）

C.O(nlogn)

D.O(n2)

【答案】B

【考点】本题考查时间复杂度的运算。

【解析】分析循环体可知，循环内的执行代码为sum++;该代码的执行次数即为for循环执行的次数。首先分析外层for循环，第一次执行，i=1；第二次执行，i=2；第三次执行，i=4……设for循环执行Tn1次，则i=2Tn1。将该结果带入循环，2Tn1<n，Tn1<log2n。因此，Tn1=log2n-1。其次分析内层for循环，当i=1时，执行2次；当i=2时，执行2次；……；当i=2Tn1，循环执行2Tn1次。设内层for循环执行的次数为Tn2，则Tn2=20+21+22+……+2Tn1=2Tn1+1-1。Tn2=2log2n-1+1-1=2log2n-1=n-1。由此得出时间复杂度为O(n)。因此故本题选B。

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

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

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

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

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

【答案】D

【考点】本题考查栈的应用。

【解析】本题的重点在于深刻理解栈的“后进先出”的特性。当已知栈的入栈序列时，可以得到有限个可能的出栈序列，因此A错误。同理，当已知栈的出栈序列时，可以得到有限个可能的入栈序列，因此B错误。若元素每次入栈之后即实行出栈操作，则可以实现入栈和出栈序列相同，因此C选项错误。若先将所有元素入栈，之后再将元素出栈，则可以实现入栈和出栈互为倒序，因此D正确。故本题选D。