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

一、填空题

1． 在循环队列中，队列长度为n ，存储位置从0到，

【答案】

编号，以rear 指示实际的队尾元素，现

要在此队列中插入一个新元素，新元素的位置是（ ）。

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

【答案】2

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

3． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】

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

4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

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

元素个数为

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

5． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

6． 如下的算法分别是后序线索二叉树求给定结点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 ）

7． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串 8

．

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

【答案】

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

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

10．阅读下列程序，指出其功能，并写出空格处应填上的语句。

的元素，如该元素已在哈希表中，报告出错。

【答案】

【解析】本题是在哈希表ht[]中插入值为

已

知

二、判断题

11．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）

【答案】√

【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。

12．数据元素是数据的最小单位。（ ）

【答案】

【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。

13．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）

【答案】×

【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。

14．串是一种数据对象和操作都特殊的线性表。（ ）

【答案】

【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。

15．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为

【答案】

【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是

16．直接访问文件也能顺序访问，只是一般效率不高。（ ）

【答案】×

【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。

17． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）

【答案】×

【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

18．取线性表的第i 个元素的时间同i 的大小有关。（ ）

【答案】

【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。

19．拓扑排序的有向图中，最多存在一条环路。（ ）

【答案】×

【解析】要进行拓扑排序，需要满足一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在 顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件, 所以拓扑排序的有

（ ）。