2012年408计算机学科专业基础考研真题答案及解析

本文提供2012年408计算机学科专业基础考研真题答案及解析，以下为具体内容

1、求整数n （n≥0）阶乘的算法如下，其时间复杂度是

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、已知操作符包括‘+’、‘-’、‘*’、 ‘/’、‘（’ 和‘）’。将中缀表达式a+b- a*（（c+d）/e-f）+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（  ）。

A、 5

B、 7

C、 8

D、 11

3、 若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（  ）。

A、 只有e

B、 有e、b

C、 有e、c

D、 无法确定

4、若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（  ）。

A、 10

B、 20

C、 32

D、 33

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

A、 O（n）

B、 O（e）

C、 O（n+e）

D、 O（ne）

6、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（  ）。

A、 存在，且唯一

B、 存在，且不唯一

C、 存在，可能不唯一

D、 无法确定是否存在

7、如图所示的有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（  ）。

A、 d，e，f

B、 e，d，f

C、 f，d，e

D、 f，e，d

8、下列关于最小生成树的叙述中，正确的是（  ）。I. 最小生成树的代价唯一II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV. 使用普里姆算法和克鲁斯卡尔（Kruskal） 算法得到的最小生成树总不相同

A、仅I

B、仅II

C、仅I、III

D、仅II、IV

1、试题答案：B

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】上述算法为递归算法。由程序段可以分析，当n<=1时，函数调用1次；当n>1时，函数的调用次数与n的大小有关，函数会调用n-1次，而乘法形式出现的n不影响调用次数，可以看做fact(n-1)的系数。根据上述程序该递归算法的时间复杂度分两部分讨论，当n<=1时，时间复杂度为O(1)；当n>1时，时间复杂度为T(n-1)+1。根据时间复杂度的运算规则，上述程序的时间复杂度为O(n)，故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查栈的应用。
【解析】本题求解的关键在于掌握中缀表达式转为后缀表达式的方法，中缀表达式转为后缀表达式的步骤如下：
（1）从中缀表达式的最左端开始取字符，若为操作符放入栈S1，若为操作数放入栈S2；
（2）继续读取，若为操作符，将其与S1栈顶元素比较，若运算符优先级高于栈顶元素，则将运算符入栈。若运算符优先级低于栈顶元素，将S1栈顶元素弹出，与S2的栈顶与次栈顶元素运算，将结果压入S2。弹出S1元素直至栈顶运算符优先级低于当前字符。
（3）若取出的字符为“（”，直接入栈；若为“）”，弹出左右括号之间的元素。重复（2）（3）步骤直至读取所有元素。
上述中缀表达式转为后缀表达式的各步骤如下表所示：

由上述步骤可知，栈中的操作符最大个数为5，故本题选A。

3、试题答案：A

试题解析：

【考点】本题考查二叉树的遍历。
【解析】后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。已知树的前序遍历和后序遍历并不能唯一的确定一棵树，因此本题需对各种情况进行分析。首先由前序遍历可以确定根结点必为a，且一定含有一个孩子结点e。假设孩子结点为e、b，且树的结构如下所示：

在前序序列中其相对位置应该为a、b、e，后序序列的相对位置应该为b、e、a，前序序列不符合。
上述树结构也可能如下所示：

在前序序列中其相对位置应该为a、e、b，后序序列的相对位置应该为e、b、a，后序序列不符合。
因此孩子结点不可能为e、b，排除B选项。假设孩子结点为e、c，且树的结构如下所示：

在前序序列中其相对位置应该为a、e、c，后序序列的相对位置应该为e、c、a，后序序列不符合。
上述树结构也可能如下所示：

在前序序列中其相对位置应该为a、c、e，后序序列的相对位置应该为c、e、a，前序序列不符合。
因此孩子结点不可能为e、c，排除C选项。根据前序序列，根结点必有一个孩子结点e，故本题选A。

4、试题答案：B

试题解析：

【考点】本题考查平衡二叉树。
【解析】一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：（1）左子树与右子树的高度之差的绝对值小于等于１；（2）左子树和右子树也是平衡二叉排序树。根据该性质，画出题干要求的平衡二叉树如下：

根据上图，结点总数为20，故本题选B。

5、试题答案：C

试题解析：

【考点】本题考查广度优先搜索。
【解析】广度优先搜索的方法为从某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若图中仍有未被访问的顶点，从该顶点出发重复上述过程。根据上述方法，广度优先搜索需遍历一次图的所有顶点及其相连的边，而邻接表存储顶点和边的信息，因此其时间复杂度为O（n+e）。故本题选C。

6、试题答案：C

试题解析：

【考点】本题考查图的拓扑序列。
【解析】有向图矩阵中主对角线以下的元素均为零证明该图中i到j可能有边，但j到i一定无边，即不存在一条双向的边，因此该有向图一定是无环图。无环图存在拓扑序列。但拓扑序列不唯一，反例如下：

上述图结构的矩阵满足题干要求，其拓扑序列有两个，因此拓扑序列可能不唯一，故本题选C。

7、试题答案：C

试题解析：

【考点】本题考查迪杰斯特拉算法求单源最短路径。
【解析】根据迪杰斯特拉算法给出从a出发求最短距离的各步骤如下：

得到的各最短路径的目标顶点依次为a,b,c,f,d,e，故本题选C。

8、试题答案：A

试题解析：

【考点】本题考查最小生成树算法。
【解析】当图中存在相同权值的边，由于选择不同，可能导致最小生成树结构不同，但最小生成树的代价一定是唯一的，因此I正确。最小生成树的边需要满足不能构成环，若多条相同的边选择构成了环，则应有边被舍弃，因此II错误。使用普里姆算法从不同顶点开始，当不同顶点在面对相同权值时做出不同的选择，那么最终生成的最小生成树不一定相同，因此III错误。若图中不存在相同权值的边，则生成的最小生成树唯一，此时不管选用普里姆算法还是克鲁斯卡尔算法得到的最小生成树总是相同的，因此IV错误。故本题选A。