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

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

1、算法的健壮性是指（ ）。

A、当输入不合法数据时，程序会采取应急措施

B、算法是正确的

C、程序不会被病毒所染

D、算法执行不会陷入无限循环

2、根据大O记号的定义，下列表示中不正确的是（ ）。

A、

B、

C、

D、

3、循环队列存储在一维数组q中，设数组的允许长度是maxSize，数组下标从0开始。如果采用在循环队列中至少保留一个空闲元素的方法来区分空队列和满队列，判断队列为满的条件是（ ）。

A、front=-rear

B、（front+1）%maxSize== rear

C、（rear+1）%maxSize==front

D、front+rear=maxSize

4、图结构是（ ）关系。

A、一对多

B、多对一

C、一对一

D、多对多

5、设有主串s=s1s2...sn和子串p=p1p2…pm。在字符串的KMP匹配算法中，当某趟匹配在字符si和sj的比较匹配时，下趟匹配（ ）。

A、总是从字符si与p1的比较开始

B、可能从字符si+1与p1的比较开始

C、不可能从字符si+1与p1的比较开始

D、总是从字符si+1与p1的比较开始

6、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非叶结点，则B中右指针为空的结点有（ ）个。

A、n-1

B、n

C、n+1

D、n+2

7、下列编码中，（ ）不是前缀编码。

A、（00，01，10，11）

B、（0，1，00，11）

C、（0，10，110，111）

D、（1，01，000，001）

8、在图采用邻接矩阵存储时，深度优先遍历算法的时间复杂度应为（ ）。

A、O(n)

B、O(n+e)

C、O(n²)

D、O(n³)

9、下面关于B和B+树的叙述中，不正确的是（ ）。

A、两者都可用于文件的索引结构

B、两者都能有效地支持顺序存取

C、两者都能有效地支持随机存取

D、两者的叶子结点都在同一层次上

10、设有n个元素的序列，分别使用冒泡排序和合并排序对其进行排序，则所需的除元素列以外的辅助空间复杂度依次为（ ）。

A、O(1)和O(n)

B、O(1)和O(nlog₂n)

C、O(n)和O(1)

D、O(n)和O(n)