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

国家二级ACCESS机试(选择题)模拟试卷128(题后含答案及解析)--第1页

国家二级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的

国家二级ACCESS机试(选择题)模拟试卷128(题后含答案及解析)--第1页

国家二级ACCESS机试(选择题)模拟试卷128(题后含答案及解析)--第2页

后面，可知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．软件生命周期可分为定义阶段、开发阶段和维护阶段，下面属于开发阶