国家二级（VB）机试模拟试卷9（共360题）.pdfVIP

家二级V（B）机试模拟试卷9共（9

套）

(共360题)

家二级V（B）机试模拟试卷第1套

一、选择题本（题共40题，每题1.0分，共40分。）

1、下列叙述中正确是（）。

A、算法空间复杂度与算法所处理数据存储空间有关

B、算法空间复杂度是指算法程序控制结构复杂程度

C、算法空间复杂度是指算法程序中指令条数

D、压缩数据存储空间不会降低算法空间复杂度

标准答案：A

知识点解析：算法空间复杂度是指执行这个算法所需要内存空间，包括3个部

分：输入数据所占存储空间；程序本身所占存储空间；算法执行过程中所需要

额外空间。为了降低算法空间复杂度，主要应减少输入数据所占存储空间以

及额外空间，通常采用压缩存储技术。A选项正确，

2、下列各组排序法中，最坏情况下比较次数相同是（）。

A、希尔排序与堆排序

B、简单插入排序与希尔排序

C、简单选择排序与堆排序

D、冒泡排序与快速排序

标准答案：D

知识点解析：对长度为n线性表，下表为常用排序算法最坏情况下比较次数。

收杯情况下的比校次数

力法

tf泡排序06)

急单插入推序0(一)

高电选推第r0(

快速排序0(/)

堆排序0(nlon)上表中未包括希尔排序，因为希尔排序时间效

率与所取增量序列有关，如果增员:序列为：di=n/2,+尸/2,在最坏情况

下，希尔排序所需要比较次数为0-（7）。由表格可知冒泡排序与快速排序比较

次数相同，D选项正确c

3、设栈存储空间为Sl（：50）,初始状态为top=51。现经过一系列正常入栈与

退栈操作后，lop=20,则栈中元素个数为（）。

A、31

B、30

C、21

D、20

标准答案：A

知识点脑析：栈是一种特殊线性表，它所有插入与删除都限定在表同一端进

行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变

量。栈为空时，栈顶指针top=0,经过入栈和退栈运算，指针始终指向栈顶元素。

初始状态为lop=51,当lop=20时，元素依次存储在单元20：50中，个数为50-

19=31,A选项正确。

4、某二叉树共有400个结点，其中有100个度为1结点，则该二叉树中叶子

结点数为（）。

A、149

B、150

C、151

D、不存在这样二叉树

标准答案：D

知识点解析：在树结构中，一个结点所拥有后件个数称为该结点度。对任何一

棵二又树，度为0结点即（叶子结点）总是比度为2结点多一个。二叉树中有

400个结点，设叶子结点个数为nO,度为1结点个数为100,设度为2结点个

数为n2。400=n0+100+n2Kn0=n2+l,则n0=15