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

一、填空题

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

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

2．

【答案】5

3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

4． 设有N 个结点的完全二叉树顺序存放在向量

【答案】 ＝_____ 中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

5． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何

置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素

成_____，若

【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边

6． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。

本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。

交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

(3)重复(2)直到堆栈为空时为止。

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

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

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

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

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

9． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

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

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

二、判断题

11．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

12．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）

【答案】×

【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。

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

【答案】 √

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

14．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）

【答案】×

【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。

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

【答案】 ×

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

16．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）

【答案】 ×

【解析】队列只在下端(队尾) 增加，在上端(队头) 减少。

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

【答案】 ×

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