国家二级ACCESS机试(选择题)模拟试卷128(题后含答案及解析).pdf

国家二级ACCESS机试（选择题）模拟试卷128(题后含答案及解析)

题型有：1.选择题

选择题

1．设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是

A．堆排序

B．希尔排序

C．有序链表查找

D．循环链表中寻找最大项

正确答案：B

解析：希尔排序(ShdlSort)是插入排序的一种。也称缩小增量排序，是直接

插入排序算法的一种更高效的改进版本。排序方法最坏时间复杂度：直接插入为

O(n2)、简单选择为O(n2)、起泡排序为O(n2)、快速排序为O(n2)、堆排序为

O(nlog2n)、归并排序为O(nlog2n)。

2．设循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一

系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情

况下需要的比较次数为

A．0

B．1

C．49

D．5n

正确答案：A

解析：front指定队头位置，删除一个元素就将front顺时针移动一位；rear

指尾指针，指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；操

作后，循环队列的队头指针等于尾指针-1，说明此时队列已经是空队列，那么就

不用比较了。

3．设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则

后序序列为

A．DGHEBIJFCA

B．JIHGFEDCBA

C．GHIJDEFBCA

D．ABCDEFGHIJ

正确答案：A

解析：前序遍历中，第一个字母是根结点，也就是A是根结点；在中序遍

历中，根结点前面的是左子树、后面的是右子树。前序中，B在A的后面，中

序中在左子树中，可知B为A的左结点。中序中D在B的前面，前序中在B的

后面，可知D为B的左结点，GEH为B的右子树。前序中顺序为EGH，由此

可知，E为B的右结点，G为E的左结点、H为E的右结点。右子树中，前序

中C在最前，因为右子树根结点，也就是A的右结点，根据前序中的子树FIJ

和中序中的IFJ子树可知F为C的右结点，I为F的左结点、J为F的右结点。

由此可画出这个二叉树，然后根据二叉树可的后序序列为DGHEBIJFCA。

4．设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要

的比较次数为

A．15

B．30

C．60

D．120

正确答案：D

解析：插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的

大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。最坏情况计

算方法(n*(n-1))／2=16*15／2=120。

5．软件生命周期可分为定义阶段、开发阶段和维护阶段，下面属于开发阶

段任务的是

A．软件运行

B．可行性研究

C．软件开发计划

D．软件集成测试

正确答案：D

解析：开发阶段由三个阶段组成：设计、实现和测试。可行性研究和软件开

发计划属于定义阶段；软件运行属于维护阶段。

6．软件测试的目的是

A．发现程序中的错误

B．修改程序中的错误

C．避免程序中的错误

D．发现和修改程序中的错误

正确答案：A

解析：软件测试的目的是：发现一些可以通过测试避免的开发风险；实施测

试来降低所发现的风险；确定测试何时可以结束；在开发项目的过程中将测试看

作是一个标准项目。

7．十进制整数设为整数类I，则下面属于类I的实例的是

A．-518

B．0．518

C．518E-2

D．518

正确答案：A

解析：整数的全体构成整数集，整数集是一个数环。在整数系中，零和正整

数统称为自然数。一1、-2、一3、…、-n、…(n，为非