首都师范大学信息工程学院908计算机学科综合历年考研真题汇编 (1)

《首都师范大学信息工程学院908计算机学科综合历年考研真题汇编 (1)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目　录第一部分　首都师范大学信息工程学院908计算机学科综合历年考研真题汇编52014年首都师范大学信息工程学院908计算机学科综合考研真题52013年首都师范大学信息工程学院908计算机学科综合考研真题14第二部分　全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解222012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题222012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解322011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题502011年全国硕

2、士研究生入学统一考试408计算机学科专业基础综合真题及详解602010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题782010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解882009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题1042009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解113说明：首都师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为908计算机学科综合。为帮助考生全面复习，特提供2009

3、～2012年408计算机学科专业基础综合真题及详解。第一部分　首都师范大学信息工程学院908计算机学科综合历年考研真题汇编2014年首都师范大学信息工程学院908计算机学科综合考研真题2013年首都师范大学信息工程学院908计算机学科综合考研真题第二部分　全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题一、单项选择题：l～40小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1．求整数n（n≥0）阶乘

4、的算法如下，其时间复杂度是（）。A．O（log2n）B．0（n）C．O（nlog2n）D．O（n2）2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。将中缀表达式a+b-a*（（c+d）／e-f）+g转换为等价的后缀表达式ab+acd+e／f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。A．5B．7C．8D．113．若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有e

5、B．有e、bC．有e、cD．无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（）。A．12B．20C．32D．335．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。A．0（n）B．0（e）C．O（n+e）D．O（n×e）6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。A．存在，且唯一B．存在，且不唯一不唯一C．存在，可能不唯一D．无法确定是否存在7．有向带权图如题7图所示，若采用迪杰斯特拉（Dij

6、kstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。题7图有向带权图A．d,e,fB．e，d，fC．f，d，eD．f，e，d8．下列关于最小生成树的叙述中，正确的是（）。Ⅰ．最小生成树的代价唯一Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A．仅ⅠB．仅ⅡC．仅Ⅰ、Ⅲ

7、D．仅Ⅱ、Ⅳ9．设有一棵3阶B树，如题9图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（）。题9图3二叉树图A．60B．60，62C．62，65D．6510．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序　Ⅱ．希尔排序　Ⅲ．快速排序　Ⅳ．堆排　V．二路归并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同

8、之处是（）。A．排序的总趟数B．元素的移动次数C．使用辅助空间的数量D．元素之间的比较次数12．假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50％，I/O速度不变，则运行基准程序A所耗费的时间是（）。A．55秒B．60秒C．65秒D．70秒1