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

一、填空题

1． 一个字符串中_____称为该串的子串。

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

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

【答案】提高查找速度

3． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

4． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

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

【答案】O(m＋n)

6． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

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

；2；k

7． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】的次数最小。总次数为

。

第 2 页，共 55 页

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测

8．

【答案】5

＝_____

9． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

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

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

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

a 中存放待排序的关键字

第 3 页，共 55 页

【答案】

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

12．数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

13．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

14．假定查找有序表

【答案】

表

平均查找次数为

15．二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

。

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

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

二、判断题

16．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）

【答案】 √

【解析】因为顺序表的插入删除会移动大量的元素。

17．2，n ，a 2，a n

若…，…，桟的输入序列是1，输出序列是a 1，（ ）

【答案】 ×

【解析】出找序列不一定满足a 1＞a i+1... ＞a n ，比如1进栈，然后出找，a 1＝1。

第 4 页，共 55 页

则有:。

。