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