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

一、填空题

1． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3，4先出栈的序列有34521、34215、34251共3个。

2． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

3． 栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

4． 在单链表中设置头结点的作用是_____。

【答案】方便运算

5． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

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

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

第 2 页，共 42 页

7． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

8． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或

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

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

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

10．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

二、判断题

11．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）

【答案】 ×

【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。

12．堆是满二叉树。（ ）

【答案】×

【解析】堆的定义:

n 个关键字序列

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

第 3 页，共 42 页

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

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

13．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）

【答案】X

【解析】数据的逻辑结构是指数据元素之间的逻辑关系。

14．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）

【答案】√

【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。

15．对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）

【答案】√

【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。

16．内排序要求数据一定要以顺序方式存储。（ ）

【答案】×

【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类:一类 是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。

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

【答案】 ×

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

18．栈和队列都是限制存取点的线性结构。（ ）

【答案】 √

19．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）

【答案】×

【解析】不是，当二元查找树是一棵单支树时，时间性能是O(n)。而折半查找依然是

第 4 页，共 42 页