沈阳师范大学软件学院计算机学科专业基础综合历考研真题汇编.docx
《沈阳师范大学软件学院计算机学科专业基础综合历考研真题汇编.docx》由会员分享，可在线阅读，更多相关《沈阳师范大学软件学院计算机学科专业基础综合历考研真题汇编.docx（188页珍藏版）》请在冰点文库上搜索。
沈阳师范大学软件学院计算机学科专业基础综合历考研真题汇编
目 录
第一部分 沈阳师范大学软件学院863计算机学科专业基础综合历年考研真题汇编5
2014年沈阳师范大学软件学院868计算机学科专业基础综合考研真题5
2013年沈阳师范大学软件学院868计算机学科专业基础综合考研真题9
第二部分 全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解13
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题13
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解23
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题41
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解51
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题69
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解79
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题95
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解104
说明：
沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为868计算机学科专业基础综合，2015年科目代码改为863。
为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。
第一部分 沈阳师范大学软件学院863计算机学科专业基础综合历年考研真题汇编
2014年沈阳师范大学软件学院868计算机学科专业基础综合考研真题
科目代码：
868
科目名称：
计算机学科专业基础综合
专业名称：
计算机应用技术
考生注意：
请将答案写在答题纸上，写在本题签及草纸上无效．考试后本题签同答题纸一并交回．
一、单项选择题（1～17小题，每小题2分，共34分。
请将答案写在答题纸指定位置上）
1．用S表示进栈操作，用X表示出栈操作，若元素进栈的顺序是abcd，为了得到acdb的出栈顺序，相应的S和X的操作序列为（）。
A．SXSXSSXX
B．SSSXXSXX
C．SXSSXSXX
D．SXSSXXSX
2．8行6列的二维数组A[8][6]采用行优先存储，元素A[0][0]存储在起始地址为200的内存单元中，每个数组元素占4个存储单元，则元素A[5][5]的地址是（）。
A．340
B．140
C．312
D．112
3．机器字的字长为（）。
A．16位
B．8位
C．64位
D．不确定
4．计算机中，指令和数据都存储在内存中，计算机在（）所取的内容是指令。
A．指令周期
B．时钟周期
C．cpu周期
D．取指周期
5．一个具有513个结点的二叉树的高度为（）。
A．10
B．10~513
C．9~513
D．9
6．以下不属于网络协议三要素的是（）
A．语法
B．语义
C．时序
D．服务
7．以下关于Ethernet物理地址的描述中，错误的是（）
A．Ethernet物理地址长度为48
B．可分配的Ethernet物理地址应该有224个
C．IEEE注册管理委员会为每个网卡生产商分配Ethernet物理地址的前3个字节
D．标准的Ethernet网卡的物理地址写法00-60-08-00-A6-38
8．一棵二叉树B是由森林F转换得到的，若森林F中有10个非终端结点，则二叉树B中右指针域为空的结点个数是（）。
A．9
B．10
C．11
D．不能确定
9．设无向连通图的顶点个数为n，则该图最少有（）条边。
A．n（n-1）/2
B．0
C．n
D．n-1
10．缓冲技术中的缓冲池在（）中。
A．主存
B．外存
C．ROM
D．寄存器
11．控制器的功能不包括（）。
A．数据加工
B．操作控制
C．顺序控制
D．时间控制
12．操作系统的基本类型可以有如下的哪一种合适的分法？
（）。
A．批处理系统、分时系统及多任务系统
B．实时系统、批处理系统及分时操作系统
C．单用户系统、多用户系统及批处理系统
D．实时系统、分时系统和多用户系统
13．当（）时，进程从执行状态转变为就绪状态。
A．进程被调度程序选中
B．时间片到
C．等待某一事件
D．等待的事件发生
14．假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…，15。
设某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6块，则该作业的3号页的首地址是（）。
A．1KB
B．12KB
C．24KB
D．条件不足，不能确定
15．有一个长度为3000个字节的流式文件要存储在磁盘上，磁盘的每块可以存放512个字节，该文件至少用（）块。
A．5
B．6
C．7
D．3000
16．接收窗口为1的退后N帧协议中，当采用3bit进行帧序号编码时，发送窗口最大值为（）。
A．7
B．6
C．5
D．4
17．RIPV1路由协议的度量跳数最大是？
（）
A．17
B．16
C．15
D．14
……………………………答……………………………………………………题…………………………………………线………………………
……………………………密……………………………………………………封…………………………………………线………………………
二、判断题（18～32题，每小题2分，共30分.请将答案写在答题纸上。
正确写T，错误写F）
18．算法的时间复杂度属于一种事前分析估算的方法。
19．http协议默认端口为80。
20．ARP协议用来实现物理地址到IP地址的解析，DNS实现IP地址到域名的解析。
21．简单选择算法的时间复杂度与数据的初始顺序无关。
22．如果在一棵二叉树的先序、中序和后序遍历序列中，结点A都在结点B的前面，则A一定是B的双亲。
23．在虚拟存储系统中，若进程在内存中占3块（开始时为空），采用先进先出页面淘汰算法，当执行访问页号序列为1，2，3，4，1，2，5，1，2，3，4，5，6时，将产生10次缺页中断。
24．在SPOOLing系统中，进程执行输出的过程是：
将进程产生的数据送到磁盘的输出井，输出程序再将数据提出，通过内存的输出缓冲区送往输出设备。
25．通道是一种特殊的I/O设备，具有执行CPU指令集的能力。
26．程序控制的数据传输方式包括无条件数据传输、查询数据传输以及DMA方式。
2716，真值是（11．155）10
28．在拓扑排序算法中，暂存入度为零的顶点可以用栈也可以用队列。
29．循环队列存储在数组A[0..m-1]中，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，则该队列的长度为（rear-front）MODm。
30．操作系统提供的给应用程序的接口是中断。
31．预防死锁的发生，就是要破坏发生死锁的必要条件，即从实际出发，破坏请求保持、互斥、不剥夺以及环路等待。
32．UDP协议采用首部校验和的方式对报文首部8个字节进行校验。
三、简答题（33～35小题，共24分。
解答应写出文字说明、证明过程或详细步骤）
33．（6分）若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
（1）先来先服务算法；
（2）最短寻道时间优先算法。
（3）扫描算法（当前磁头移动的方向为磁道递增）
34．（8分）某计算机字长32位，现有的存储器模块为32M×32位，若将存储空间扩至256M×32位请提出一种提高访问速度的可能方案。
35．（10分）已知一组关键字为｛41，22，53，46，30，13，01，67，18，35，44，15｝，构造二叉排序树并计算等概率情况下查找成功时的平均查找长度ASL成功和等概率情况下查找失败时的平均查找长度ASL失败。
四、综合应用题（36～41小题，共62分.解答应写出文字说明、证明过程或详细步骤）
36．（5分）设某路由器建立了如下路由表：
目的网络子网掩码下一跳
2
3
*（默认）—R4
现收到5个分组，其目的地址如下，试分别计算下一跳：
37．（6分）假定1Km长的CSMA/CD网络的数据率为1Gb/s。
设信号在网络上的传播速率为200000km/s。
求能够使用此协议的最短帧长。
38．（9分）在测温系统中要完成采样、转换和显示任务。
采样过程把从传感器上得到的整型微电压值存入一个缓冲区；转换过程把微电压值从缓冲区中取出，通过计算转换成温度值再存入该缓冲区；显示过程把缓冲区中的温度值取出并显示。
这里，缓冲区同一时刻只能存储一个数值。
请编写程序，利用PV操作实现三个过程共享缓冲区，要求说明所设信号量的含义。
39．（12分）指令格式如下所示，OP为操作码字段，试分析指令格式特点。
3126252221181716150
OP
源寄存器
变址寄存器
偏移量
40．（15分）已知带头结点的单链表lc中各结点的元素值为非零的整数，试设计算法将其拆分为两个带头结点的单链表la和lb，使得la中只包含所有元素值大于零的结点，lb中只包含所有元素值小于零的结点。
（1）描述算法设计思想（3分）；
（2）算法的C语言描述（10分）；
（3）指出算法时间复杂度（2分）。
数据的存储结构定义如下：
typedefstructnode{
intdata;
structnode*next;
}node,*linklist;
41．（15分）用16K×1位的DRAM芯片构成64K×8位的存储器。
要求：
（1）画出该芯片组成的存储器逻辑框图。
（2）设存储器读/写周期均为0.5μs，两次刷新的最大时间间隔是2ms。
试问采用哪种刷新方式比较合理？
两次刷新的最大时间间隔是多少？
对全部存储单元刷新一遍，所需实际刷新时间是多少？
2013年沈阳师范大学软件学院868计算机学科专业基础综合考研真题
代码：
869
科目名称：
计算机学科专业基础综合
专业名称：
计算机应用技术
考生注意：
请将答案写在答题纸上，写在本题签及草纸上无效．考试后本题签同答题纸一并交回．
一、单项选择题（1～15小题，每小题3分，共45分）
1．某计算机字长32位，其存储容量为8MB，若按字编址，它的寻址范围是（）。
A．1M
B．4MB
C．4M
D．2MB
2．同步传输之所以比异步传输具有较高的传输频率是因为同步传输（）。
A．不需要应答信号
B．总线长度较短
C．用一个公共时钟信号进行同步
D．各部件存取时间较为接近
3．（）实现对等实体间的通信。
A．服务
B．协议
C．接口
D．服务访问点
4．当（）时，进程从执行状态转变为就绪状态。
A．进程被调度程序选中
B．时间片到
C．等待某一事件
D．等待的事件发生
5．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项中表述正确的是（）。
A．Max[i,j]=Available[i,j]+Need[i,j]
B．Need[i,j]=Max[i,j]-Allocation[i,j]
C．Max[i,j]=Allocation[i,j]-Need[i,j]
D．Need[i,j]=Max[i,j]+Allocation[i,j]
6．在文件系统中，要求物理块必须连续的物理文件是（）。
A．顺序文件
B．链接文件
C．索引文件
D．Hash文件
7．下列哪种说法是正确的？
（）
A．集线器可以对接收到的信号进行放大
B．集线器具有信息过滤功能
C．集线器具有路径检测功能
D．集线器具有交换功能
8．循环队列存储在数组A[0..m-1]中，则出队时移动队头指针的操作为（）。
A．front=front+1
B．front=（front+1）MOD（m-1）
C．front=（front+1）MOD（m+1）
D．front=（front+1）MODm
9．设一棵二叉树有n个结点，则其深度为（）。
A．不能确定
B．n
C．以2为底n的对数向下取整再加1
D．以2为底n+1的对数向上取整
10．8个顶点的强连通图至少有（）条有向边。
A．56
B．28
C．7
D．8
11．假定查找成功与不成功的概率相同，在查找成功的情况下每个记录的查找概率也相同，则顺序查找算法的平均查找长度为（）。
A．0.75n+0.25
B．0.5（n-1）
C．0.5（n+1）
D．0.25（n+1）
12．关于排序，下列说法中正确的是（）。
A．稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率高
B．各种排序方法都是在顺序表上实现的，在链表上无法实现排序
C．对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同
D．在顺序表上实现的排序方法，在链表上也都可以实现
13．假定MAC地址不在ARP表中，发送方如何找到目的地址的MAC地址？
（）
A．它发送广播信息到整个局域网
B．它发送广播信息到整个网络
C．以上都不是
D．A和B都是
14．对数据序列{26，85，22，48，16，28，69，36，21}进行排序，每一趟排序后元素序列的变化情况如下：
原始数据序列{26，85，22，48，16，28，69，36，21}
一趟排序结果{21，16，22，26，48，28，69，36，85}
二趟排序结果{16，21，22，26，36，28，48，69，85}
三趟排序结果{16，21，22，26，28，36，48，69，85}
则采用的排序方法是（）。
A．快速排序
B．希尔排序
C．堆排序
D．归并排序
15．一个进程是（）。
A．PCB由协处理机执行的一个程序
B．一个独立的程序+数据集
C．PCB结构与程序和数据的组合
D．一个独立的程序
二、填空题（16～20小题，每小题3分，共15分）
16．UDP用于生成校验和的伪首部长度为___字节。
17．在定点小数中，能表示-1的机器码是___。
18．HTTP协议提供服务的默认端口是_____。
19．具有5层的平衡二叉树至少有____个结点。
20．PPP协议同步传输时，采用_____技术实现透明传输。
三、问答题（21～25小题，共50分。
解答应写出文字说明、证明过程或演算步骤）
21．1～LAN4都连接到路由器R1上，R1通过LAN5与路由器R2相联。
R2和远地的三个部门的局域网LAN6～LAN8通过广域网连接。
每一个局域网旁边标明的数字是局域网上的主机数。
试给每一个局域网分配一个合适的网络前缀。
22．（本题满分10分）假定某请求页式存储管理系统中，为一进程分配了内存物理块3块，考虑以下的页面引用串：
1，2，3，4，2，1，4，5，2，1，2，3。
问：
（1）若按先进先出（FIFO）和最近最久未使用（LRU）页面置换算法，请问将发生缺页中断的次数和缺页率（开始3页不算缺页），并画图示意。
（2）若页面大小为1KB，假定该虚页对应的内存物理块号为7，试给出虚地址（12345）8对应的物理地址（仍用8进制表示）。
23．（本题满分10分）设存储器容量为2M字，字长64位，模块数M=8,分别用顺序方式和交叉方式进行组织，存储周期T=200ns,数据总线宽度64位，总线传送周期为τ=50ns.
问：
顺序存储器和交叉存储器带宽各是多少？
24．（本题满分10分）有人提出这样的一种从图G中顶点u开始构造最小生成树的方法：
假设G=（V，E）是一个具有n个顶点的带权连通无向图，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：
（1）初始化U={u}。
以u到其它顶点的所有边为候选边。
（2）重复以下操作步骤n-1次，使得其它n-1个顶点被加入到U中。
从候选边中挑选权值最小的边加入到TE，设该边在V-U中的顶点是v，将v加入U中。
考查顶点v，将v与V-U顶点集中所有顶点之间的边作为新的候选编边。
若此方法求得的T是最小生成树，请予以证明。
若不能求得最小生成树，请举出反例。
25．（本题满分10分）假定有一个足够大的池子，A、B两人分别向池子中扔球，A扔红球，B扔蓝球，两人均每次只能扔一个球。
开始时池子中红球、蓝球各有一个，现要求池中的球时刻满足如下条件：
1≦红球数/蓝球数≦2。
请用平P、V原语（或wait、signal）描述这两个进程。
四、综合题（26～27小题，共40分。
解答应写出文字说明、证明过程或演算步骤）
26．（本题满分20分）系统主存1MB，高速缓存16KB，块的大小为512B，采用直接方式地址映像
（1）写出高速缓存地址格式。
（2）写出主存地址格式。
（3）块表的容量为多大？
（4）画出直接方式地址映像及变换示意图。
（5）主存地址为CDE8FH的单元在高速缓存中的什么位置？
27．（本题满分20分）已知n个学生数据结构期中考试成绩存放在顺序表L中，试设计一个算法，使表中70分以上的排在前面，50分至69分的排在中间，49分以下的排在后面。
要求算法时间效率尽可能高，辅助存储空间占用尽可能少。
（1）描述算法设计思想；
（2）算法的C语言描述；
（3）指出算法时间复杂度和辅助存储空间占用数量。
顺序表存储结构定义如下：
#definemax400
typedefstruct{
intno;
intscore;
}student;
typedefstruct{
studentstudents[max];
intlength;
}sqlist;
第二部分 全国硕士研究生入学统一考试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中内容及record.c的地址分别为（）。
A．0x00、0xC00D
B．0x00、0xCOOE
C．0x11、0xC00D
D．0x11、0xC00E
16．下列关于闪存（FlashMemory）的叙述中，错误的是（）。
A．信息可读可写，并且读、写速度一样快
B．存储元由MOS管组成，是一种半导体存储器
C．掉电后信息不丢失，是一种非易失性存储器
D．采用随机访问方式，可替代计算机外部存储器
17．假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。
若Cac
升级会员 