2006年数据结构考研真题答案及解析

本文提供2006年数据结构考研真题答案及解析，以下为具体内容

1、下面关于倒排文件的说法中正确的是（ ）。

A、倒排文件是对主关键字建立索引的

B、倒排文件是对次关键字建立索引的

C、倒排序文件的优点是维护简单

D、采用倒排文件是为了节省存储空间

2、下列术语中，（ ）与数据的存储结构无关。

A、循环队列

B、堆栈

C、散列表

D、单链表

3、用DFS遍历一个有向无环图，并在DFS算法退栈返回时打印当前顶点，则输出的顶点序列是（ ）。

A、拓扑有序的

B、无序的

C、逆拓扑有序的

D、按顶点编号次序的

4、下面（ ）算法可用于求无向图的所有连通分量。

A、广度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

5、可以使用大O记号表示一个算法的时间复杂度。下列表示中正确的是（ ）。

A、

B、

C、

D、

6、设线性表非空，采用下列（ ）所描述的链表可以在O（1）时间内在表尾插入一个新结点。

A、带表头结点的单链表，一个链表指针指向表头结点

B、带表头结点的单循环链表，一个链表指针指向表头结点

C、不带表头结点的单链表，一个链表指针指向表的第一个结点

D、不带表头结点的单循环链表，一个链表指针指向表的第一个节点

7、设主串为“abceabceyabceabceab”，子串为“abceabcea”，则在KMP匹配第一趟失配后下一趟匹配开始时，子串指针指示的字符是（ ）。

A、a

B、b

C、c

D、e

8、二叉树中第5层上的结点个数最多为（ ），假定根节点层次为1。

A、8

B、15

C、16

D、32

9、设有以元素10，9，20，6，85，23，21，17 为叶结点的8路合并胜方树，在输出一个元素后，将有一个新元素补充到相应的叶结点中。在重构的胜方树中，应有（ ）个元素需要修正。

A、1

B、2

C、3

D、4

10、在一棵二叉搜索树上搜索一个元素的平均时间复杂度为（ ）。

A、

B、

C、

D、

1、试题答案：B

试题解析：

【考点】本题考查数据结构--文件--多关键字文件--倒排文件--倒排文件的特点。
【解析】
A和B：倒排文件是对次关键字建立索引的，是一种常见的信息检索技术，可以快速地查找包含某个关键字的文档。
C：倒排文件的缺点是维护困难，在同一个倒排文件中不同关键字的记录数不同，各倒排表的长度也不等。
D：倒排文件是为了提高检索效率，并非节省存储空间。
综上所述，本题选B。

2、试题答案：B

试题解析：

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的存储结构/物理结构。
【解析】数据的存储结构主要有：顺序存储、链式存储、索引存储、散列存储。循环队列属于顺序存储结构，散列表属于散列存储结构，单链表属于链式存储结构。而堆栈是一种逻辑结构，其既可用顺序存储结构存储，也可以用链式存储结构存储。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的深度优先遍历/搜索。
【解析】在深度优先遍历的过程中，我们先访问当前节点的所有前驱节点（即入边指向当前节点的节点），然后再访问当前节点。因此，如果按照这种方式遍历整个图，每个节点的所有前驱节点都已经被访问过了。如果在DFS算法的递归调用返回时打印相应的顶点，则这样输出的顶点序列的次序是按照节点被访问的时间顺序从晚到早输出的。由于在有向无环图中，拓扑排序的顺序是按照节点被访问的时间顺序从早到晚排列的，因此这种输出顶点序列的次序被称为逆拓扑序列。故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查数据结构--图--图的基本概念--图的术语--连通性--无向图连通性--连通分量。
【解析】求无向图的所有连通分量的方法：深度优先遍历、广度优先遍历、并查集。故本题选A。
广度优先遍历算法可以用于求无向图的所有连通分量。在广度优先遍历时，从一个起点开始遍历，遍历过程中将所有与该起点相邻的节点加入队列中，然后遍历队列中的节点，将与这些节点相邻的节点加入队列中。当遍历结束时，队列中所有节点即为同一个连通分量中的节点。重复以上过程，直到遍历完整个图，就可以得到所有的连通分量。

5、试题答案：A

试题解析：

6、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--链表的综合对比。
【解析】对于不带表头结点的单循环链表在O（1）时间内在表尾插入一个新结点的实例如下所示，由此可知其可以在O（1）时间内实现该操作。故本题选D。

7、试题答案：A

试题解析：

【考点】本题考查数据结构--串--串的模式匹配算法--KMP匹配算法--KMP匹配算法的应用。
【解析】在KMP匹配的第一趟匹配过程中，前8个字符均匹配成功，第9个字符匹配失败，而next[9]=1。因此，下一趟匹配开始时，子串指针指示的字符是第一个字符a。故本题选A。

8、试题答案：C

试题解析：

9、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树。
【解析】在8路合并胜方树中，每个非叶结点的度数为8，如果一个叶结点补充新元素后，该结点的父节点需要重新计算赢家，可能会导致沿着该结点到根节点路径上的结点的赢家改变。因此，至多有4个结点需要修正，即从该叶节点到根节点的路径上所有结点。由于只输出了一个元素，可能不会影响路径上所有结点的赢家，因此修正的结点数量可能小于4。具体需要修正多少个结点，取决于该叶节点到根节点路径上的结点的原始赢家是否改变。因此，最多有4个元素需要修正。故本题选D。

10、试题答案：D

试题解析：