2012年408考研真题-数据结构

8.【2012统考真题】求整数n(n≥0)的阶乘的算法如下，其时间复杂度是(）。

int fact(int n){

if(n<=1) return 1;

return n*fact (n-1);

}

A. O(log2n)        B. O(n)        C. O(nlog2n)        D. O(n^2)

解析：

观察代码，我们不难发现使用了递归调用。递归调用要找出口，也就是跳出递归的条件。

本题跳出递归的条件是n=1；从fact(n)不断地往下递归知道fact(1)，在这过程中，总共执行了n次，时间复杂度为O(n).

11.【2012统考真题】已知操作符包括“+”、“-”、“*”、“/”、“（”和“）”。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。栈初始时为空时，转换过程中同时保存在栈中的操作符的最大个数是(A)。A.5        B.7        C.8        D.11

解析：

a输出，+存入栈内，b输出，操作符进栈讲究一个够强才进，-和+是平级的，只能让+先输出出来，-再进去，这时候栈内的存的个数任然是1个。

接下来是a，输出a，然后是*,*够强存入栈中，接着是((够强，存入栈中，输出c，接下来是+，此时栈里面最上层是(，所以+也存入栈内，此时栈内存的操作符个数是5个了。

接着输出d，然后是)，)仍爱着(，它俩要私奔，所以栈内+输出，(输出，接着是/，/直接进入栈内，接下来直接输出字母e，接着是-，因为此时栈内是/号，/号更强，-不能直接进，让/直接输出，-进入，然后是f，输出f，接着是),因为要私奔，栈内输出-和(,然后是+,此时栈顶是*，需要先将*输出，再让+进入，此时栈内存过的最大的个数是5个，选A。

30.[2012统考真题]若一棵二叉树的前序遍历序列为 a,e,b,d.c.后序遍历序列为 b.c.d,e,a，则根结点的孩子结点()。

A.只有e        B.有 e、b        C.有e、c        D.无法确定

解析：

前序遍历序列：根左右。

后序遍历序列：左右根。

前序遍历序列第一个是a，a是根结点,但是在后序遍历序列中a是最后一个。

以下面这个例子来看，作为根结点A的两个孩子，结点B和C在前序遍历中是ABC，

在后序遍历中是BCA，不管是前序还是后序他们的相对位置是不变的。

带着这样一个结论来看这道题：

因为前序遍历第二个结点e，

假设如果有左孩子，那左孩子的根结点一定是e。

假设如果没有左孩子，那右子树的根结点一定也是e。

也就是说根结点的孩子结点必有e。

假设根结点的孩子结点有两个，则这两个孩子结点在前序遍历序列和后序遍历序列中的相对位置是不变的。

看B选项，e和b在前序遍历序列中是e在前b在后，在后序遍历序列中是b在前e在后。

相对位置变了，b不是根结点的叶子结点。B错

同理可以证明B错，C错。

20.[2012统考真题]若平衡二叉树的高度为 6，且所有非叶子结点的平衡因子均为1,则该平衡二叉树的结点总数为(B)。

A.12        B.20        C.32        D.33

解析：

平衡因子：左右子树的高度之差。

我们不难得出这样一个结论：对于一个所有非叶子结点的平衡因子都为1，且高度为h的平衡二叉树，它的结点总数为高度为h-1和h-2的同类树的结点总数再+1；

如何h=3的结点个数是树高为1+树高为2的同类树的结点个数再+1；

我们接着算出h=4，h=5，h=6时的结点个数。

h=4 ： 2+4+1=7

h=5 ： 4+7+1=12

h=6  :   7+12+1=20 

算出答案：20选B

14.对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是）。

A.O(n)        B. O(e)        C.O(n+e)        D. O(ne)

解析：

对有n个顶点、e条边的有向图,不管是BFS广度优先遍历还是DFS深度优先遍历，它的时间复杂度都和使用的存储方式有关。

使用邻接表存储方式的，时间复杂度是O(n+e)

使用邻接矩阵存储的，时间复杂度是O()

21.【2012统考真题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是()。

A.存在，且唯一

B.存在，且不唯一

C.存在，可能不唯一

D.无法确定是否存在

解析：

,由图可知，只有当i<j时存在边。

且只存在0-1，0-2,0-3，1-2，1-3的边，不存在回路，也就没有环。

那这就是一个无环图。

有向无环图是存在拓扑序列的，所以D错

拓扑序列在图1：是不唯一的。

在图二：是唯一的。

答案选C。

19.【2012统考真题】对下图所示的有向带权图，若采用Dijkstra算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是(）。

A.d,e,f        B.e,d,f        C.f,d,e        D.f,e,d

解析：

18.【2012统考真题】下列关于最小生成树的叙述中，正确的是(A）。

I.最小生成树的代价唯一。

II.所有权值最小的边一定会出现在所有的最小生成树中。

III.使用Prim算法从不同顶点开始得到的最小生成树一一定相同。

Ⅳ.使用Prim算法和Kruskal算法得到的最小生成树总不相同。

A.仅I        B.仅Ⅱ        C.仅I、Ⅲ        D.仅Ⅱ、Ⅳ

解析：

生成树的代价最小才能称为最小生成树，因此代价一定是唯一的。I对。

II不一定，以下图为例：

使用prim算法得到的结果不唯一，因为一个点如果几条边的权值都是一样的话，那它就有几条路线选择的可能性，因此不唯一，生成的最小生成树肯定不是唯一相同的。III错。

如果连通图的最小生成树是唯一的，那么不管用什么算法都是唯一的一种。Ⅳ错。

12.【2012统考真题】已知一棵3阶B树，如下图所示。删除关键字78得到一棵新B树，其最右叶结点中的关键字是(D）。

A.60        B.60, 62        C.62, 65        D.65

解析：78去掉后，需要找一个新的元素添上，这里直接找它的前驱65，然后62填补上65的空缺。所以最右边叶子结点中的关键字是65。

10.【2012统考真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每趟排序结束都至少能够确定一个元素最终位置的方法是(）。

 I.简单选择排序

Ⅱ.希尔排序

Ⅲ.快速排序

Ⅳ.2路归并排序

V.堆排序

A.仅I、Ⅲ、Ⅳ

B.仅I、Ⅲ、V

C.仅II、Ⅲ、Ⅳ

D.仅Ⅲ、Ⅳ、V

解析：

 I.简单选择排序：每次都能在待排的队列中选出一个最小或者最大的出现在头或尾。I是对的。

Ⅱ.希尔排序：举一个反例：

Ⅲ.快速排序，每趟排序过后，这个数左边的全小于它，右边的数全大于它，能确定位置。
Ⅳ.堆排序：前面的能确定比这个数小，后面的能确定比这个数大。堆排序能确定位置。

V.2路归并排序：

举一个反例：

4321

3412

1234

2路归并排序不能确定最终位置。

16.【2012统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是(）。

A.排序的总趟数

B.元素的移动次数

C.使用辅助空间的数量

D.元素之间的比较次数

解析：

折半插入排序是在直接插入排序的基础上，在将数插入到已排序的过程中，使用了折半查找的思想，折半查找显然能大幅度减少元素的比较次数。