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、