计算机专业（基础综合）模拟试卷116.pdfVIP

计算机专业(基础综合)模拟试卷116

一、单选题(本题共40题，每题1.0分，共40分。)

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

while(i!=l)i=i/2；

A、0(log2n)

B、0(n)

C、0(Vn)

2

D、0(n)

标准答案：A

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

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

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

2、若已知一个栈的入枝序列是1,2,3,4o其出栈序列为pl,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)、

(I,3)、(2,3),其中若是(1,2)这个序列，那么3已经在pl位置出栈，不可能再

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

素，即p3一定是3,所以p4不可能是3。

3、执行完下列语句段后，i值为()。intf(intx){rctum((xO)?x*f(x-1)；2)；)int

i；i=f(f(D)；

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种二叉排序树；在4为根

时，1、2、3为左子树结点，对应二叉排序树有5利因此共有5+2+2+5=14种。

5、由元素序列(27,16,75,38,51)构造平衡二叉树，则首次出现的最小不平衡子树的

根(即离插入结点最近且平衡因子的绝对值为2的结点)是()“

A、27

B、38

C、51

D、75

标准答案：D

知识点解析：考查平衡二叉树的构造。由题中所给的结点序列构造平衡二叉树的过

程如图1所示，当插入51后，首次出现不平衡子树，虚线框内即为最小不平衡子

树。

6、在下列二叉树中，()的所有非叶结点的度均为2。I.完全二叉树H.满二又

树m.平衡二叉树w.哈夫变树v.二叉排序树

A、II和IV

B、I和m

c、口、w和v

D、口、HI和w

标准答案：A

知识点解析：考查特殊二叉树的性质。对于I,可能最后一层的叶结点个数为奇

数，即倒数第二层上有非叶结点的度为1。对于n,显然满足。对于m,可能存在

非叶结点只有一个孩子结点。对于m,根据哈夫曼树的构造过程可知所有非叶结点

度均为2。对于V,可能存在非叶结点只有一个孩子结点。因此选A。注意：在哈

夫曼树中没有度为1的结点。图1构造平衡二叉树

7、一个含有n个顶点和P条边的简单无向图，其邻接矩阵存储中零元素的个数是

（）o

A、e

B、2e