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

一、填空题

1． 顺序栈用

【答案】存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

2． 模式串的next 函数值序列为_____。

【答案】01122312

3． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。 【答案】

4．

【答案】5

5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法

，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）

中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ）

{ if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/

{ （2） ;

if （node->rflag）（3）;

else {do t=*x；;

while （*x==node ）;

*x=t;

}

}

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

6． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

=_____

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为

一个元素时，此时堆的元素个数最少，元素个数为

7． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

8． 线性表

【答案】（n －1）/2 当最后一层只有用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

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

9． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

10．设有两个算法在同一机器上运行，其执行时闻分别为

_____。

【答案】15

【解析】当

时，而

，时， 要使前者快于后者，n 至少为

二、选择题

11．在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）

A.5

B.7

C.8

D.14

【答案】A

【解析】根据B 树的定义可知，跟结点最少含有个关键字，高度为2的阶B 树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。

12．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A. 插入

B. 选择

C. 希尔

D. 二路归并

【答案】A

【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的

记录存放在数组中，排序过程的某一中间时刻，R

被划分成两个子区间

插入到有序区

和其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1

个记录

中适当的位置上。使

变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。

13．下面关于求关键路径的说法不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的

B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D. 关键活动一定位于关键路径上

【答案】C

【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。

14．设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。

15．某同步总线的时钟频率为宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。

A.20ns

B.40ns

C.50ns

D.80ns

【答案】C 。

【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。