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

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

2． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

3． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

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

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

5． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

6．

设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

7． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。

【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

8． 中缀式运算结果为_____。

【答案】

对应的前缀式为_____，若

则后缀式的

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

9． 完善算法：求KMP 算法.next 数组。

END ；

【答案】 10．假定查找有序表

【答案】37/12

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

表

平均查找次数为

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

二、判断题

11．深度为k 的二叉树中结点总数小于等于

【答案】√

【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为

12．设模式串的长度为m , 目标串的长度为n ，当且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）

【答案】

【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。

13．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）

【答案】×

【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。

（ ）

并且序列在基本有序的情况下，直接插入排序也会提高。

14．强连通分量是无向图的极大强连通子图。（ ）

【答案】×

【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。

15．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）

【答案】×

【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

16．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）

【答案】√

【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。

17．二叉树中除叶结点外，任一结点点的值大于等于该结点

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

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

【答案】√

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

19．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）

【答案】√

【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

其左子树根结点的值小于该结点的值；其右子树根结

的值，则此二叉树一定是二叉排序树。（ ）