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)

1、试题答案：A

试题解析：

【考点】本题考查数据结构--绪论--算法和算法分析--算法概念--算法的五大特性。
【解析】算法的健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。故本题选A。

2、试题答案：D

试题解析：

3、试题答案：C

试题解析：

【考点】本题考查数据结构--栈和队列--队列--队列的应用--循环队列。
【解析】在循环队列中，为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时，front=rear；当队满时，front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选C。

4、试题答案：D

试题解析：

【考点】本题考查数据结构--图--图的基本概念--图的定义。
【解析】图结构：元素之间存在任意的多对多的关系，它们之间没有任何约束关系。图形结构中的元素是无序的。故本题选D。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--串--串的模式匹配算法--KMP匹配算法。
【解析】当next[j]=0时，就会从si+1与p1的比较开始。一般情况总是从字符si与next[j]所指的子串字符开始比较。故本题选B。

6、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--森林转换为二叉树。
【解析】在一棵具有m个结点的二叉树中，除根节点外，每个结点都直接被其父结点所指向，占用指针域m-1个，所以二叉树中空指针域为 2m-（m-1）= m+1。假设森林的总结点个数为m，题干给出森林中的非叶子结点个数为n，那么叶子结点个数为m-n，而森林转换为二叉树后的叶子结点是没有左孩子的，即二叉树中的左指针域为空的个数为m-n。因此，右指针域的个数为m+1-（m-n）=n+1。故本题选C。

7、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--树与二叉树的应用--哈/赫夫曼树及其编码--前缀编码。
【解析】如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是前缀编码。选项B中第一个编码0是第三个编码00的前缀，所以不是前缀编码。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的深度优先遍历/搜索。
【解析】当采用邻接矩阵表示图时，深度优先遍历过程中每个顶点都要检查与其相邻的所有其他顶点，这需要在O(n)的时间内完成，因为每个顶点最多有n-1个相邻顶点。由于共有n个顶点，因此深度优先遍历的总时间复杂度为O(n²)。此外，对于一个无向图，由于每条边都可以看作是连接两个顶点的单向边，因此总边数为2e。因此，如果采用邻接表表示图，每个顶点最多有2e个相邻顶点，邻接表表示图的深度优先遍历时间复杂度为O(n+e)。综上所述，本题选C。

9、试题答案：B

试题解析：

【考点】本题考查
1、数据结构--查找--动态查找表--B-树--B-树的性质；
2、数据结构--查找--动态查找表--B+树--B+树的性质。
【解析】B-树不支持顺序存取。故本题选B。

10、试题答案：A

试题解析：

【考点】本题考查
1、数据结构--排序--内部排序--起/冒泡排序--起/冒泡排序的空间复杂度；
2、数据结构--排序--内部排序--归并排序--归并排序的空间复杂度。
【解析】由下表知，冒泡排序和合并排序的空间复杂度为O（1）、O（n）。故本题选A。