沈阳农业大学信息与电气工程学院805计算机专业基础历年考研真题汇编附答案 1.docx
《沈阳农业大学信息与电气工程学院805计算机专业基础历年考研真题汇编附答案 1.docx》由会员分享，可在线阅读，更多相关《沈阳农业大学信息与电气工程学院805计算机专业基础历年考研真题汇编附答案 1.docx（146页珍藏版）》请在冰点文库上搜索。
沈阳农业大学信息与电气工程学院805计算机专业基础历年考研真题汇编附答案1
目 录
说明：
沈阳师范大学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．（+1）%MaxSize==+1）%MaxSize
B．+1）%MaxSize==+1
C．+1）%MaxSize==
D．==
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时间
作业19小时
作业22小时
作业310小时
作业45小时
假设系统中没有其他作业，试给出对它们实施FCFS调度算法的计算结果，并计算其平均周转时间和平均带权周转时间。
25．几个并行进程共享一个数据集（如文件或表格）时，有些进程可能只是要求读这数据集的内容，而另一些进程则可能要求修改这数据集的内容。
这种情况在操作系统中是很普遍的。
通常我们称读数据的进程为读者，而把要求修改数据的进程称为写者。
用P、V操作来描述读者—写者问题。
2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题
代码：
868
科目名称：
计算机学科专业基础综合
适用专业名称：
计算机应用技术
考生注意：
请将答案写在答题纸上，写在本题签及草纸上无效。
考试后本题签同答题纸一并交回。
一、单项选择题（共30题，每题2分，合计60分）
1．某算法的时间复杂度为O（n2），表明该算法的（）。
A．问题规模是n2
B．执行时间等于n2
C．执行时间与n2成正比
D．问题规模与n2成正比
2．设线性表中有2n个元素，以下操作中，（）在单链表上实现要比在顺序表上实现效率更高。
A．删除指定的元素
B．在最后一个元素的后面插入一个新元素
C．顺序输出前k个元素
D．交换第i个元素和第2n-i-1个元素的值（i=0,1…,n-1）
3．在一个单链表L中，指针p指向L的某个结点，在p之前插入一个指针s所指结点时的操作为（）。
A．s->next=p->next；p->next=s；t=p->data；p->data=s->data；s->data=t；
B．p->next=s；s->next=p->next；t=p->data；p->data=s->data；s->data=t；
C．s->next=p->next；p->next=s；p->data=s->data；t=p->data；s->data=t；
D．p->next=s；s->next=p->next；t=s->data；s->datap->data；p->data=t；
4．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,pn，若p1=n，则pi的值（）。
A．i
B．n-i
C．n-i+1
D．不确定
5．对稀疏矩阵进行压缩存储，常用的两种方法是（）。
A．二元组和散列表
B．三元组和十字链表
C．三角矩阵和对角矩阵
D．对角矩阵和十字链表
6．广义表（（a），a）的表头和表尾分别是（）。
A．（a）和（a）
B．a和（a）
C．（a）和a
D．（（a））和（a）
7．已知二叉树的先序序列为ABDEGCF，中序序列为DBGEACF，则后序序列为（）。
A．GEDBFCA
B．DGEBFCA
C．DGEBAFC
D．EBFDGCA
8．一棵完全二叉树上有1000个结点，其中叶子结点的个数是（）。
A．250
B．500
C．505
D．501
9．线索二叉树是一种（）结构。
A．逻辑
B．逻辑和存储
C．物理
D．线性
10．以数据集{2，5，7，9，13}为权值构造一棵哈夫曼树，则其带权路径长为（）。
A．78
B．80
C．81
D．79
11.一个有向图的邻接表存储如图1所示，现按深度优先搜索遍历，从顶点v1出发，所得到的顶点序列是（）。
图1图的邻接表
A．v1，v2，v3，v4，v5
B．v1，v2，v3，v5，v4
C．v1，v2，v4，v5，v3
D．v1，v2，v5，v3，v4
12．任意一个无向连通图（）最小生成树。
A．只有一棵
B．一定有多棵
C．有一棵或多棵
D．可能不存在
13．若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）。
A．是个有根有向图
B．是个强连通图
C．含有多个入度为0的顶点
D．含有顶点数目大于1的强连通分量
14．顺序查找法适合于存储结构为（）的线性表。
A．哈希存储
B．索引存储
C．压缩存储
D．顺序存储或链式存储
15．在含有27个结点的二叉树排序树上，查找关键字为35的结点，则依次比较的关键字有可能是（）。
A．28，36，18，46，35
B．18，36，28，46，35
C．46，28，18，36，35
D．46，36，18，28，35
16．在有序表a[1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过元素的次数为（）。
A．4
B．5
C．3
D．6
17．数据序列｛8，9，10，4，5，6，20，1，2｝只能是下列排序算法中的（）的两趟排序后的结果。
A．选择排序
B．冒泡排序
C．插入排序
D．堆排序
18．就平均性能而言，目前最好的内部排序方法是（）排序法。
A．冒泡排序
B．希尔排序
C．插入排序
D．快速排序
19．有一组数据｛15，9，7，8，20，-1，7，4｝，用堆排序的筛选方法建立的初始堆为（）。
A．-1，4，5，9，20，7，15，7
B．-1，7，15，7，4，8，20，9
C．-1，4，7，8，20，15，7，9
D．A，B，C都不对
20．下面说法不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，将使整个工程提前完成
C．所有关键活动都提前完成，则整个工程提前完成
D．某些关键活动若提前完成，将使整个工程提前完成
21．下列选项中，（）不是操作系统关心的主要问题。
A．管理计算机裸机
B．设计、提供用户程序与计算机硬件系统的界面
C．管理计算机系统资源
D．高级程序设计语言的编译器
22．系统功能调用是（）。
A．用户编写的一个子程序
B．高级语言中的库程序
C．操作系统中的一条命令
D．操作系统向用户程序提供的接口
23．在处理机管理中，当（）时，进程从阻塞状态变为就绪状态。
A．进程被调度程序选中
B．等待某一事件发生
C．等待的事件发生
D．时间片用完
24．高级调度是（）。
A．进程调度
B．作业调度
C．程序调度
D．设备调度
25．临界区是（）。
A．一个缓冲区
B．一段共享数据区
C．一段程序
D．一个互斥资源
26．产生死锁的根本原因是（）。
A．资源共享
B．并发执行的进程太多
C．进程推进顺序非法
D．以上3个因素全是
27．在下述存储管理方案中，（）管理方式要求作业占用连续的存储空间。
A．分区
B．分页
C．分段
D．段页式
28．操作系统中对数据进行管理的部分叫做（）。
A．数据库系统
B．文件系统
C．检索系统
D．数据存储系统
29．下列文件中属于逻辑结构的文件是（）。
A．连续文件
B．系统文件
C．散列文件
D．流式文件
30．在磁盘文件系统中，对于下列文件物理结构，（）不具有直接读写文件任意一个记录的能力。
A．顺序结构
B．链接结构
C．索引结构
D．散列结构
二、算法设计题（共2题，每题10分，合计20分）
31．设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得：
A={a1,a2,…,an},B={b1,b2,…,bn}
32．冒泡排序的算法是把大的元素向上移动（气泡的上升）也可以把最小的元素向下移动（气泡的下沉）。
请给出上浮和下沉过程交替的冒泡排序算法。
三、综合应用题（共6题，合计70分）
33．写出用Prim算法构造图2最小生成树的过程。
（10分）
图2无向网
34．关键字序列A=（36,27,68,33,97,40,81,24,23,90,32,14）共12个数据，哈希表长为13，采用的哈希函数为：
h（key）=key%13。
如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其查找成功时的平均查找长度。
（10分）
35．在如图3所示的AOE网，求：
（10分）
（1）完成此工程最少需要的多少天（设边上权值为天数）。
（2）是否存在某项活动，当其提高速度后能使整个工程缩短工期。
图3AOE网
36．若有以下四个作业同时到达系统并立即进入调度：
作业名所需CPU时间（分钟）
作业19
作业24
作业310
作业48
假设系统中没有其他作业，现对它们实施SJF调度算法。
给出作业调度顺序并求出平均作业周转时间T，平均带权作业周转时间W。
（15分）
37．在一个请求式页式管理系统中，某程序在内存中分配三个页面，初始为空.页面走向为:
4，3，2，1，4，3，5，4，3，2，1，5。
用学过的页面值换算法FIFO算出缺页次数。
给出执行过程中内存页面的变化情况。
（15分）
38．在4*100m接力赛中，4个运动员之间存在如下关系图4，运动员1跑到终点把接力棒交给运动员2，……，运动员4接到棒后跑完全程。
试用信号量机制进行描述。
试写出这四个并发进程能正确执行的程序。
（10分）
图4进程关系图
第二部分 全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题
一、单项选择题：
l～40小题。
每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1．求整数n（n≥0）阶乘的算法如下，其时间复杂度是（）。
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．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．12
B．20
C．32
D．33
5．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
A．0（n）
B．0（e）
C．O（n+e）
D．O（n×e）
6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。
A．存在，且唯一
B．存在，且不唯一不唯一
C．存在，可能不唯一
D．无法确定是否存在
7．有向带权图如题7图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。
题7图有向带权图
A．d,e,f
B．e，d，f
C．f，d，e
D．f，e，d
8．下列关于最小生成树的叙述中，正确的是（）。
Ⅰ．最小生成树的代价唯一Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅲ
D．仅Ⅱ、Ⅳ
9．设有一棵3阶B树，如题9图所示。
删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（）。
题9图3二叉树图
A．60
B．60，62
C．62，65
D．65
10．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序 Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 V．二路归并排序
A．仅Ⅰ、Ⅲ、Ⅳ
B．仅Ⅰ、Ⅱ、Ⅲ
C．仅Ⅱ、Ⅲ、Ⅳ
D．仅Ⅲ、Ⅳ、Ⅴ
11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。
A．排序的总趟数
B．元素的移动次数
C．使用辅助空间的数量
D．元素之间的比较次数
12．假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。
若CPU速度提高50％，I/O速度不变，则运行基准程序A所耗费的时间是（）。
A．55秒
B．60秒
C．65秒
D．70秒
13．假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：
unsignedshortX＝65530；unsignedinty＝X：
得到y的机器数为（）。
A．00007FFAH
B．0000FFFAH
C．FFFF7FFAH
D．FFFFFFFAH
14．float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（）。
A．2126-2103
B．2127-2104
C．2127-2103
D．2128-2104
15．某计算机存储器按字节编址，采用小端方式存放数据。
假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。
某C语言程序段如下：
若record变量的首地址为0xC008，则地址0xC008中内容及的地址分别为（）。
A．0x00、0xC00D
B．0x00、0xCOOE
C．0x11、0xC00D
D．0x11、0xC00E
16．下列关于闪存（FlashMemory）的叙述中，错误的是（）。
A．信息可读可写，并且读、写速度一样快
B．存储元由MOS管组成，是一种半导体存储器
C．掉电后信息不丢失，是一种非易失性存储器
D．采用随机访问方式，可替代计算机外部存储器
17．假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。
若Cache的内容初始为空，采用2路组相联映射方式和LRU替换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数是（）。
A．1
B．2
C．3
D．4
18．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（）。
A．5位
B．6位
C．15位
D．33位
19．某同步总线的时钟频率为l00MHz，宽度为32位，地址／数据线复用，每传输一个地址或数据占用一个时钟周期。
若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输l28位数据所需要的时间至少是（）。
）。
A．20ns
B．40ns
C．50ns
D．80ns
20．下列关于USB总线特性的描述中，错误的是（）。
A．可实现外设的即插即用和热插拔
B．可通过级联方式连接多台外设
C．是一种通信总线，可连接不同外设
D．同时可传输2位数据，数据传输率高
21．下列选项中，在I／O总线的数据线上传输的信息包括（）。
Ⅰ．I／O接口中的命令字 Ⅱ．I／0接口中的状态字 Ⅲ．中断类型号
A．仅Ⅰ、Ⅱ
B．仅Ⅰ、Ⅲ
C．仅Ⅱ、Ⅲ
D．Ⅰ、Ⅱ、Ⅲ
22．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（）。
Ⅰ．开关中断 Ⅱ．保存通用寄存器的内容 Ⅲ．形成中断服务程序入口地址并送PC
A．仅Ⅰ、Ⅱ
B．仅Ⅰ、Ⅲ
C．仅Ⅱ、Ⅲ
D．Ⅰ、Ⅱ、Ⅲ
23．下列选项中，不可能在用户态发生的事件是（）。
A．系统调用
B．外部中断
C．进程切换
D．缺页
24．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。
A．程序计数器
B．程序状态字寄存器
C．通用数据寄存器
D．通用地址寄存器
25．下列关于虚拟存储的叙述中，正确的是（）。
A．虚拟存储只能基于连续分配技术
B．虚拟存储只能基于非连续分配技术
C．虚拟存储容量只受外存容量的限制
D．虚拟存储容量只受内存容量的限制
26．操作系统的I／O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。
其合理的层次组织排列顺序是（）。
A．用户级I／O软件、设备无关软件、设备驱动程序、中断处理程序
B．用户级I／O软件、设备无关软件、中断处理程序、设备驱动程序
C．用户级I／O软件、设备驱动程序、设备无关软件、中断处理程序
D．用户级I／O软件、中断处理程序、设备无关软件、设备驱动程序
27．假设5个进程P0、Pl、P2、P3、P4共享三类资源Rl、R2、R3，这些资源总数分别为l8、6、22。
T0时刻的资源分配情况如题27表所示，此时存在的一个安全序列是（）。
题27表资源分配情况表
已分配资源
资源最大需求
进程
R1
R2
R3
R1
R2
R3
PO
3
2
3
5
5
10
P1
4
O
3
5
3
6
P2
4
O
5
4
O
11
P3
2
O
4
4
2
5
P4
3
1
4
4
2
4
A．P0，P2，P4，Pl，P3
B．Pl，P0，P3，P4，P2
C．P2，Pl，P0，P3，P4
D．P3，P4，P2，Pl，P0P0
28．若一个用户进程通过read系统调用读取一个磁盘文件中的数据
升级会员 