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

一、填空题

1． 模式串

的next 函数值序列为_____。

【答案】01122312

2． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。

【答案】

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，

所以

3． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【答案】

【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

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

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

6． 假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

7．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

8． 组成串的数据元素只能是_____。

【答案】字符

9． 索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

10．在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

11．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

12．表达式的后缀表达式是_____。

【答案】

二、选择题

13．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：

若record 变量的首地址为A. B. C. D. 【答案】D 。

则地址

中内容及record.c 的地址分别为（ ）。

【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址

中存放a , 地址

中存放b , 地址

中空闲，

地址中存放c 。

14．在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。

I . LRU 算法 A. 仅 II B .仅 I II C. 仅I III D. 仅 II III 【答案】A

【解析】Belady 现象只有FIFO 算法才会出现

15．

，用直接插入排序方法对下面4个序列进行排序（由小到大）元素比较次数最少的是（ ）。

【答案】C

II. FIFO 算法 III. OPT 算法