当前位置：问答库＞考研试题

一、填空题

1． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

2． 已知如下程序段：

语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。

【答案】（1）n ＋1 （2）n

（3）n （n ＋3）/2 （4）n （n ＋l ）/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。

3． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。 4 ．

求REPLACE （S ，V , m ）=_____。

【答案】

已

知

5． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）

【答案】93

【解析】对于上三角矩阵，

6． 当两个栈共享一存储区时，栈利用一维数组当栈1空时

，

【答案】

为_____，栈2空时

，

将

代入得93。 表示，两栈顶指针为

在B

则

为_____，栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

7． 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

8． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

9． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

11．建立索引文件的目的是_____。

【答案】提高查找速度

12．设二维数组A 的行和列的下标范围分别为

【答案】时，则i=2，j=3。

和每个元素占2个单元，按行优先顺处的元素为_____。

当其值为

序存储，第一个元素的存储起始位置为b ，则存储位置为

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是

二、选择题

13．广义表

【答案】D

head 操作就是得到广义表中第一个的原子。【解析】

操作就是得到除第一个原子外剩下元

素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。

14．下列有关浮点数加减运算的叙述中，正确的是（ ）。

对阶操作不会引起阶码上溢或下溢

右规和尾数舍入都可能引起价码上溢

左规时可能引起阶码下溢

尾数溢出时结果不一定溢出 A. 仅B. 仅C. 仅

D. 【答案】D

【解析】浮点数的加减运算步骤包括：①对阶，使两个操作数的小数点位置对齐，阶码小的尾数右移，可能产生溢出，但是阶码不会溢出；②尾数求和，将对阶后的尾数按定点数加（减）运算规则运算；③规格化，包括左规和右规，左规时阶码减少，可能出现阶码下溢，而右规时，阶码増加可能出现阶码上溢；④舍入，该过程可能需要右规调整，因此可能出现阶码上溢；⑤溢出判断，浮点数的溢出与否是由阶码的符号决定的，而不是由尾数溢出判断的，因此尾数溢出时结果不一定溢出。因此

15．数据序列结果。

A. 选择排序 B. 起泡排序 C. 插入排序 D. 堆排序 【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

16．下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。

A. 连续结构

则式子

的值为（ ）。

均正确。

只能是下列排序算法中的（ ）的两趟排序后的