2025年计算机专业(基础综合)模拟试卷116(题后含答案及解析) .pdfVIP

百川东到海，何时复西归?少壮不努力，老大徒伤悲。——汉乐府

计算机专业（基础综合）模拟试卷116(题后含答案及解析)

题型有：1.单项选择题2.综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，

只有一个选项是最符合题目要求的。

1．设n是描述问题规模的正整数，下列程序片段的时间复杂度是()。

i=n*n；while(i!=1)i=i／2；

A．0(log2n)

B．0(n)

C．0()

D．0(n2)

正确答案：A

解析：考查时间复杂度。将算法中基本运算的执行次数的数量级作为时间复

杂度。基本运算是“i=i／2；”，设其执行次数为k，则(n*n)／(2k)=1，得k=log2n2，

因此k=log2n2=2log2n，即k的数量级为log2n，因此时间复杂度为O(log2n)。

2．若已知一个栈的入栈序列是1，2,3，4。其出栈序列为p1，p2,p3,p4，

则p2,p4不可能是()。

A．2、4

B．2、1

C．4、3

D．3、4

正确答案：C

解析：考查出入栈序列。对于A，可能的顺序是：1入，1出，2入，2出，

3入，3出，4入，4出。对于B，可能的顺序是：1．A,2入，3入，3出，2出，

4入，4出，1出。对于D，可能的顺序是：1入，1出，2入，3入，3出，2出，

4入，4出。C则没有对应的序列，因为当4在栈中时，意味着前面的所有元素

(1、2、3)都已经在栈中或者曾经入过栈，那么此时若4在第二个位置出栈，即

栈中还有两个元素，且这两个元素是保持有序的(即相对的入栈顺序)，只能为(1，

2)、(1，3)、(2，3)，其中若是(1，2)这个序列，那么3已经在p1位置出栈，不

可能再在p4位置出栈，若是(1，3)和(2，3)这种情况中任一中，3一定是下一个

出栈的元素，即p3一定是3，所以p4不可能是3。

3．执行完下列语句段后，i值为()。intf(intx){return((x＞0)?x*f(x

一1)：2)；)inti；i=f(f(1))；

A．2

B．4

C．8

D．无限递归

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

正确答案：B

解析：考查递归程序的执行。f(1)=1*f(0)=2：i=f(f(1))=f(2)=2*f(1)=2*2=4，

选B。

4．含有4个元素值均不相同的结点的二叉排序树有()种。

A．4

B．6

C．10

D．14

正确答案：D

解析：考查二叉排序树。分别设4个元素值为1、2、3、4，构造二叉排序

树：在1为根时，对应2、3、4为右子树结点，右子树可有5种对应的二叉排序

树；在2为根时，对应1为左子树，3、4为右子树结点，可有2种二叉排序树：

在3为根时，1、2为左子树结点，4为右子树，可有2