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

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

1、现实生活中具有谱系结构的数据，在计算机中处理时一般采用（ ）结构表示。

A、线性

B、树

C、图

D、集合

2、设后缀表达式为：“43*293/+2-/”，式中，每个操作数均为一位整数，则表达式的值为（ ）。

A、6

B、4

C、8

D、A、B、C三者都不是

3、设二叉树根结点的层次为1，在所有含135个结点的二叉树中，最小高度是（ ）。

A、6

B、7

C、8

D、9

4、设A、X和Y是二叉树B中的三个结点，X是A的左孩子，Y是X的左孩子。T是与B对应的树：在T中，A是Y的（ ）。

A、孩子

B、兄弟

C、双亲

D、祖先（非双亲）

5、下面哪一种结构必定是完全二叉树（ ）。

A、哈夫曼树

B、二叉搜索树

C、 AVL搜索树

D、堆

6、在有序表（10，20，30，40，50，60，70，80，90）中以对半搜索法查找元素30和45时，所需的关键字值间的比较次数分别为（ ）。

A、3，3

B、3，4

C、4，4

D、A，B，C三者都不是

7、假定从无向图G的任何一个顶点出发进行一次深度优先搜索，都可以访问图中每个顶点，则该图一定是（ ）。

A、连通图

B、完全图

C、有回路的图

D、一棵树

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

A、逆拓扑有序

B、拓扑有序

C、无序的

D、按关键字有序

9、初始序列经第一趟排序后，不能确定任何一个元素最终位置的排序算法是（ ）。

A、两路合并排序

B、冒泡排序

C、快速排序

D、简单选择排序

10、快速排序和冒泡排序的最坏情况时间复杂度分别为（ ）。

A、

B、

C、

D、

1、试题答案：B

试题解析：

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的逻辑结构。
【解析】具有谱系结构的数据在现实生活中非常常见，例如家族谱、公司组织架构等。在计算机中处理这类数据时，一般采用树形结构表示。树形结构可以清晰地表达出数据元素之间的层级关系，易于操作和管理。而线性结构、图结构和集合结构不具备表达层级关系的特点，不适合表示谱系结构的数据。故本题选B。

2、试题答案：B

试题解析：

【考点】本题考查数据结构--栈和队列--栈--栈的应用--表达式的计值--后缀表达式的计值。
【解析】将后缀表达式转换为中缀表达式的过程可以通过栈来实现，具体步骤如下：
（1）从左到右扫描后缀表达式中的每个元素，对于每个元素进行如下处理：
a. 如果是操作数，直接入栈。
b. 如果是运算符，弹出栈顶的两个元素作为右操作数和左操作数，将它们按照“左操作数、运算符、右操作数”的形式组成一个中缀表达式并入栈。

（2）扫描结束后，栈中剩余的元素就是转换后的中缀表达式。
后缀表达式“43*293/+2-/”转中缀表达式的过程如下，得到中缀表达式为(4*3)/ (2+(9/3))-2=4。故本题选B。

3、试题答案：C

试题解析：

4、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--二叉树转换为树。
【解析】二叉树B中，X是A的左孩子，Y是X的左孩子，因此，Y是A的左孙子。在对应的树T中，A是Y的祖先，而不是 Y 的双亲。祖先是指从一个节点到根节点的路径上的所有节点，因此 A 是 Y 的祖先（非双亲）。故本题选D。

5、试题答案：D

试题解析：

【考点】本题考查数据结构--排序--内部排序--选择排序--堆排序--堆--堆的性质。
【解析】堆是一种特殊的树形数据结构，其中每个父节点的值都小于等于（或大于等于）其孩子节点的值，且堆总是一个完全二叉树。故本题选D。

6、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--静态查找表--折半查找。
【解析】
（1）(0+8)/2=4，50>30，进而在左半部分进行折半查找；(0+3)/2=1，20<30，进而在右半部分进行折半查找；(2+3)/2=2，30=30。查找30成功，共进行了3次比较。
（2）(0+8)/2=4，50>45，进而在左半部分进行折半查找；(0+3)/2=1，20<45，进而在右半部分进行折半查找；(2+3)/2=2，30<45，进而在右半部分进行折半查找；(3+3)/2=3，40<45。查找45失败，共进行了4次比较。
综上所述，在有序表（10，20，30，40，50，60，70，80，90）中以对半搜索法查找元素30和45时，所需的关键字值间的比较次数分别为3、4。故本题选B。

7、试题答案：A

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的深度优先遍历/搜索。
【解析】如果从无向图G的任何一个顶点出发进行一次深度优先搜索，都可以访问图中每个顶点，那么图G必定是连通图。因为深度优先搜索会遍历图中的所有连通分量，如果从某个顶点出发无法到达其他顶点，则说明这个顶点所在的连通分量与其他连通分量不连通，即整个图不连通。而如果能够访问每个顶点，则说明图中的所有连通分量都被遍历到了，即整个图是连通的。故本题选A。

8、试题答案：A

试题解析：

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

9、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--归并排序--归并排序的基本思想。
【解析】归并排序每趟产生的有序区只是局部有序，所以在最后一趟排序结束前所有元素不一定在其最终位置上。故本题选A。

10、试题答案：D

试题解析：