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

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

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

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

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

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

voidfun(intn){inti，k；for(i=1；ilt;=n；i十十)for(j=1；jlt;=n；

j十十){k=1：while(klt;=n)k=5*k：}}

A．O(n2log2n)

B．O(nlog5n)

C．O(n2log5n)

D．O(n3)

正确答案：C

解析：基本运算语句是k=5*k，设其执行时间为T(n)。对于j每循环一

次，该语句的执行次数为m，有：5m≤n，即m≤log5n。所以：

2．利用栈求表达式的值时，设立运算数栈OPND。假设OPND只有两个

存储单元，在下列表达式中，不发生溢出的是()。

A．A—B*(C—D)

B．(A—B)*C—D

C．(A—B*C)—D

D．(A—B)*(C—D)

正确答案：B

解析：利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及进行后

缀表达式求值这两步操作可以和在一起进行，需要设立运算符栈OPTR和运算数

栈OPND两个栈。例如求选项A的表达式A—B*(C—D)的过程如下表所示：

按照上述过程可知，选项A求值时，运算数栈OPND的大小至少为4。例

如求选项B的表达式(A—B)*C—D的过程如下表所示：按照上述

过程可知，选项B求值时，运算数栈OPND的大小至少为2。类似地，选

项C、D求值时，运算数栈OPND的大小至少为3、3。因此本题答案为B。

3．已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序

列是()。

A．dacb

B．cadb

C．dbca

D．以上答案都不对

正确答案：B

解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进

行的队列。分析选项A，输入序列为abcd，输出序列为dacb，由输出受限

性质可知以da开头的结果只有dabc，选项A为错误答案。分析选项B，输

入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后

在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的

序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输

出d，再输出b。最后得到输出序列为cadb。分析选项C，输入序列为abcd，

输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac，选项C为错

误答案。

4．一个具有1025个结点的二叉树的高h为()。

A．11

B．10

C．11至1025之间

D．10至1024之间

正确答案：C

解析：一棵二叉树每层只有1个结点，则具有1025个结点的二叉树的最大

高度为1025。一个具有1025个结点的完全二叉树的高度为11。这一个具有1025

个结点的二叉树的高h为11至1025之间。

5．以下关于二叉排序树的说法正确的是()。I在二叉排序树中，每个

结点的关键字都比左孩子关键字大，比右孩子关键字小。Ⅱ每个结点的关键

字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。

Ⅲ在二叉排序树中，新插入的关键字总是处于最底层。Ⅳ在二叉排序树中，

新结点总是作为叶子结点来插入的。V二叉排序树的查找效率和二叉排序树

的高度有关。

A．I、Ⅱ、Ⅳ、V

B．Ⅱ、Ⅲ、Ⅳ

C．I、Ⅲ、V

D．I、Ⅳ、V

正确答案：D

解析：对于二叉排序树，左子树上所有记录的关