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、