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

一、填空题

1． 表达式

【答案】

2． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若则

的地址为

3． 在哈希函数

将

代入得33。

中，P 值最好取_____。

则

的地址为

若

，）则

的后缀表达式是_____。

的地址为_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

4． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；

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） ;

第 2 页，共 57 页

树每个结点至多有_____个儿子，除

根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

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． 完善算法：求KMP 算法.next 数组。

END ； 【答案】

7． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）（2）

链表未到尾就一直进行

将当前结点作为头结点后的第一元素结点插入

8． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

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

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

10．VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

二、选择题

11．设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。

A. 求子串 B. 判断是否相等

第 3 页，共 57 页

C. 模型匹配 D. 连接 【答案】C

【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。

12．对序

列

A.1 B.4 C.3 D.2

【答案】B

【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。

13．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。

A.b ，a , c , d ，e B.d ，b , a , c ，e C.d ，b , c , a ，e D.e ，c ，b , a ，d

【答案】C

【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。

假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：

选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL

14．已知循环队列存储在一维数组中，且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是（ ）。

A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，

第 4 页，共 57 页

用希尔排序方法排序，经一趟后序列变

为

则该次采用的增量是（ ）。