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

一、填空题

1． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

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

【答案】if(top!＝n)data[++top]＝x ；

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

4． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

【解析】当

5． 假定查找有序表

【答案】

表

平均查找次数为

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

【答案】字符

时，100n2>2n，而，2n 时，100n ＜2 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。【解析】折半查找时每个的次数如表所示: 。

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

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

8． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；

【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py

9． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

10．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

二、判断题

11．归并排序辅助存储为O(1)（ ）

【答案】×

【解析】归并排序的辅助存储是O Cn)o

12．广义表(((a，b ，C) ，d ，e ，f)) 的长度是4。（ ）]

【答案】 ×

【解析】长度为1。因为只含一个元素即子表(((a，b ，C) ，d ，e ，f)) 。

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

【答案】 √

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

14．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

【答案】×

【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。

15．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）

【答案】√

【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点，该方法把所以邻接于顶点

的链接成一个带头。在有向图中，为图中每个顶点建立一个入边表的方法称为逆邻接表示法。

16．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）

【答案】 ×

【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。

17．堆是满二叉树。（ ）

【答案】×

【解析】堆的定义:

n 个关键字序列

①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；

大根堆:满足第②种情况的堆。

因此并不能保证堆是满二叉树。