目　录
第一部分　沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编    5
2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题    5
2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题    8
第二部分　全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解    14
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题    14
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解    24
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题    42
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解    52
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题    70
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解    80
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题    96
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解    105
说明：沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为867计算机学科专业基础综合（数据结构、操作系统），2015年科目代码
改为862。为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。

第一部分　沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编
2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题
科目代码：867             
科目名称：计算机学科专业基础综合（数据结构、操作系统）
适用专业名称：计算机应用技术
考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。考试后本题签同答题纸一并交回。
一、单项选择题（共10题，每题2分，合计20分）
1．某算法的时间复杂度为O(n2)，表明该算法（）。
A．问题规模是n2                 
B．执行时间等于n2
C．执行时间与n2成正比           
D．问题规模与n2成正比
2设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更高。
A．输出第i（1≤i≤n）个元素     
B．交换第1个元素与第2个元素的值
C．顺序输出这n个元素的值       
D．输出与给定值x相等的元素在线性表中的序号
3．给定一个空栈，若10、20、23、13依次进栈，然后有两个数出栈，又有3个数进栈，第一次进栈的23现在在（）。
A．已出栈 
B．从栈底算起第3个
C．栈顶 
D．从栈底算起第4个
4．循环队列qu（其队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置，队列中的单元个数为MaxSize）的队满足条件是（）。
A．（qu.rear+1）%MaxSize==(qu.front+1)%MaxSize
B．(qu.rear+1)%MaxSize==qu.front+1
C．(qu.rear+1)%MaxSize==qu.front
D．qu.rear==qu.front
5．一棵二叉树的中序序列为ABDCEFG，后序序列为BDCAFGE，则其左子树中的节点个数为（）。
A．3       
B．2       
C．4     
D．5
6．根据使用频率为5个字符设计的哈夫曼编码不可能是（）。
A．111,110,10,01,00           
B．000,001,010,011,1
C．100,11,10,1,0             
D．001,000,01,11,10
7．对所示的无向图，从顶点1开始进行深度优先遍历，可得到的顶点访问序列为（）。
A．1243576 
B．1243567   
C．1245637   
D．1234576
8．对于下图，以下（）是其拓扑序列。
A．1,3,4,6,2,5,7 
B．1,3,2,6,4,5,7 
C．1,3,4,5,2,6,7 
D．1,2,5,3,4,6,7
9．对数据序列{15,9,7,8,20,-1,4}进行排序,一趟排序后的结果为{9,15,7,8,20,-1,4},采用的是（）。
A．简单选择排序 
B．起泡排序 
C．直接插入排序 
D．堆排序
10．对一组数据(2,12,16,88,5,10)进行排序,若前三趟的结果如下:
第一趟：2,12,16,5,10,88
第二趟：2,12,5,10,16,88
第三趟：2,5,10,12,16,88
则采用的排序方法可能是()。
A．起泡排序 
B．希尔排序 
C．归并排序 
D．基数排序
二、应用题（共4题，每题10分，合计40分）
11．使用普里姆算法构造如图所示的图G中从顶点1开始的一棵最小生成树。
12．设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，其哈希函数如下：
H(key)=key%13
采用开放地址法的线性探测法解决冲突，试在0~18的哈希表中对该关键字序列构造哈希表。
13．已知有6个顶点（顶点编号为0-5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
4
6
∞
∞
∞
5
∞
∞
∞
4
3
∞
∞
3
3
数据结构与算法考研真题要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。
（3）求图G的关键路径，并计算该关键路径的长度。
14．将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，构造相应的平衡二叉树。
三、算法设计题（共3题，每题10分，合计30分）
15．设C={a1,b1, a2,b2,…,an,bn}为一线性表，采用带头节点的hc单链表存放，设计一个就
地算法，将其拆分为两个线性表（它们都用单链表存放），使得：
A={ a1,,a2,…,an }，B={b1, b2,…,bn }
16．假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有分支节点个数。
17．设计一个算法，判断一个数据序列是否构成一个小根堆。
四、简答题（共6题，每题5分，合计30分）
18．什么是操作系统的基本功能？
19．描述系统调用的含义。
20．说明什么是进程间的直接制约与间接制约。
21．说明什么是虚拟存储器。
22．请说明分区存储管理方式的主要优缺点。
23．说明什么是中断。
五、综合题（共2题，每题15分，合计30分）
24．若有以下四个作业以1、2、3、4的顺序，在0时刻几乎同时到达系统并立即进入调度：
作业名          所需CPU时间
作业1                9小时
作业2                2小时
作业3                10小时
作业4                5小时
假设系统中没有其他作业，试给出对它们实施FCFS调度算法的计算结果，并计算其平均周转时间和平均带权周转时间。
25．几个并行进程共享一个数据集（如文件或表格）时，有些进程可能只是要求读这数据集
的内容，而另一些进程则可能要求修改这数据集的内容。这种情况在操作系统中是很普遍的。通常我们称读数据的进程为读者，而把要求修改数据的进程称为写者。用P、V操作来描述读者—写者问题。

2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题
代码：868
科目名称：计算机学科专业基础综合
适用专业名称：计算机应用技术
考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。考试后本题签同答题纸一并交回。
一、单项选择题（共30题，每题2分，合计60分）
1．某算法的时间复杂度为O(n2)，表明该算法的（  ）。
A．问题规模是n2                   
B．执行时间等于n2

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。