重庆理工大学计算机科学与工程学院计算机学科专业基础综合历考研真题汇编附答案.docx
《重庆理工大学计算机科学与工程学院计算机学科专业基础综合历考研真题汇编附答案.docx》由会员分享，可在线阅读，更多相关《重庆理工大学计算机科学与工程学院计算机学科专业基础综合历考研真题汇编附答案.docx（193页珍藏版）》请在冰点文库上搜索。
重庆理工大学计算机科学与工程学院计算机学科专业基础综合历考研真题汇编附答案
目 录
第一部分 重庆理工大学计算机科学与工程学院810计算机学科专业基础综合历年考研真题汇编5
2014年重庆理工大学计算机科学与工程学院810计算机学科专业基础综合考研真题5
2013年重庆理工大学计算机科学与工程学院809计算机学科专业基础综合考研真题10
说明：
重庆理工大学计算机学科专业基础综合的科目代码每年都不同，2015年改为813。
第二部分 全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解16
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题16
2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解26
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题44
2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解54
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题72
2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解82
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题98
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解107
说明：
重庆理工大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为810计算机学科专业基础综合。
为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。
第一部分 重庆理工大学计算机科学与工程学院810计算机学科专业基础综合历年考研真题汇编
2014年重庆理工大学计算机科学与工程学院810计算机学科专业基础综合考研真题
学院名称：
计算机科学与工程学院
学科、专业名称：
计算机科学与技术
考试科目（代码）：
计算机学科专业基础综合（810）A卷
一、单选题（每题2分，共50分）
1．顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，则该顺序表的第4个元素地址是（）
A．110
B．108
C．112
D．106
2．一个具有n个顶点的无向完全图的边数为（ ）
A．n（n+1）/2
B．n（n-1）/2
C．n（n-1）
D．n（n+1）
3．深度为2（根结点的层次为1）的满二叉树的叶子节点个数为（）
A．2
B．4
C．6
D．8
4．双向链表中每个结点的指针域的个数为（）
A．0
B．1
C．2
D．3
5．完全二叉树，按层次序列对每个结点编号（根结点编号为1），则编号为7的结点的双亲编号为（）
A．1
B．2
C．3
D．4
6．下列属于线性结构的是（）
A．线性表
B．树
C．查找
D．图
7．在一个无向图中，所有顶点的度数之和等于所有边数的（）
A．1倍
B．2倍
C．4倍
D．8倍
8．栈的特点是（）
A．先进后出
B．先进先出
C．后进后出
D．前出前进
9．深度为3（根的层次号为1）的满二叉树结点个数为（）
A．4
B．6
C．7
D．8
10．不带头结点的单链表head为空的判定条件是（）
A．head==NULL
B．head->next==NULL
C．head!
=NULL
D．head->next!
=NULL
11．有一个有序表为{2，3，8，10，30}，当折半查找到8时，需要的比较次数为（）
A．1
B．2
C．3
D．4
12．栈的插入与删除操作在（）
A．栈顶
B．栈底
C．队头
D．队尾
13．一个栈的入栈顺序是a,b,c，则该栈的不可能的输出序列是（）
A．abc
B．cba
C．acb
D．cab
14．设先序遍历某二叉树的序列为ABC，中序遍历该二叉树的序列为BAC，则后序遍历该二叉树的序列为（）
A．ABC
B．CBA
C．ACB
D．BCA
15．设一组初始记录关键字序列（5，2，6，3），以第一个记录关键字5为基准进行一趟快速排序的结果为（）
A．2，3，5，6
B．5，2，3，6
C．3，2，5，6
D．2，3，6，5
16．在计算机中配置操作系统的主要目的是（）
A．增强计算机的功能
B．提高系统资源的利用率
C．提高系统的运行速度
D．合理组织系统的工作流程
17．从静态角度讲，进程由程序段、数据段和（）组成，它是进程存在的唯一标志。
A．JCB
B．PCB
C．FCB
D．代码段
18．临界区是指（）
A．进程中用于访问共享资源的那段代码。
B．进程中用于实现进程同步的那段代码。
C．进程中用于实现进程互斥的那段代码。
D．进程中用于访问临界资源的那段代码。
19．下面哪种情况不会引发进程调度？
（）
A．进程正常结束或异常中止。
B．正在执行的进程因I/O请求而被阻塞。
C．某等待打印机的进程发现其它使用打印机的进程已经打印完毕。
D．在引入时间片的系统中，时间片用完。
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．联机输出
二、简答题（每题5分，共60分）
26．计算程序段的时间复杂度。
（5分）
for（i=1;i<=n;i++）
x++;
27．设给定权集W={2，3，4，7}，试构造关于W的一棵赫夫曼树，并求其带权路径长度WPL。
（5分）
28．设有一序列30,19,3,61，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度ASL。
（5分）
29．写出下图所示二叉树的先序，中序和后序遍历序列。
（5分）
30．什么是线性表?
线性表的元素之间的关系是什么?
（5分）
31．已知待散列的线性表为（8，15，40，63），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。
（5分）
0
1
2
3
4
5
6
32．请画图说明进程的三种基本状态及各状态间的转换，并说明引发状态转换的典型事件。
（5分）
33．什么是操作系统，简述操作系统的主要功能。
（5分）
34．什么是死锁，分析死锁发生的主要原因。
（5分）
35．虚拟存储器的基本特征有哪些？
为什么说请求分页系统是实现虚拟存储器是一种方式？
（5分）
36.什么是中断，描述CPU访问中断的一般过程。
（5分）
37．在公共汽车上，司机与售票员的工作流程如下图所示。
为保证乘客安全，司机和售票员必须密切配合协调工作，售票员在关车门之后向司机发送开车信号，司机接到开车信号后启动车辆，汽车正常行驶时售票员可以售票，到站时司机停车，售票员在停车后开门让乘客下车，请用信号量来实现司机与售票员之间的同步。
（5分）
三、综合题（每题10分，共40分）
38．编写一个函数，实现对数组a（元素个数为n）中元素进行冒泡排序的算法。
（10分）
voidbubblesort（inta[]）
39．编写两个函数，分别实现对二叉树的先序遍历（preorder）和中序遍历（inorder）的递归算法。
（10分）
二叉树结点的结构体为
structBiTreeNode{
intdata;
structBiTreeNode*leftChild;
structBiTreeNode*rightChild;
};
typedefstructBiTreeNodeNode;
voidpreorder（Node*t）/*t为指向二叉树的根结点的指针*/
voidinorder（Node*t）/*t为指向二叉树的根结点的指针*/
40．（本题10分）有四个进程P1,P2,P3,P4，它们进入就绪队列的先后顺序为P1,P2,P3,P4，它们的优先级和需要的处理机时间如下表。
假定这四个进程在执行过程中不会发生等待事件，忽略进程调度所花费的时间，从某个时刻开始进程调度，请回答下面的问题：
进程
要求的处理时间
优先级
P1
8
3
P2
6
1
P3
22
5
P4
4
4
（1）采用“先来先服务”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（4分）
（2）采用“非抢占式的优先级”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（4分）
（3）说明采用“时间片轮转法”调度算法时，写出进程的执行顺序，计算各进程在系统中停留的时间以及平均停留的时间。
（2分）
41．（本题10分）某系统采用页式存储管理策略，请回答下面的问题：
（1）若逻辑空间为32页，每页2K，物理空间1M，写出逻辑地址的格式。
若不考虑访问权限等，进程的页表有多少项，每项至少多少位？
如果物理空间减少一半，页表结构应相应地怎样变化。
（6分）
（2）假定页表放在内存中，如果访问内存需要0.3s，计算有效访问时间；（2分）
（3）如果加一快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少？
（2分）
2013年重庆理工大学计算机科学与工程学院809计算机学科专业基础综合考研真题
学院名称：
计算机科学与工程学院
学科、专业名称：
计算机科学与技术
考试科目（代码）：
809计算机学科专业基础综合（A卷）
一、选择题
1．深度为2（根结点的层次号为1）的满二叉树的叶子结点个数为（）
A．2
B．3
C．4
D．6
2．栈的特点是（）
A．先进后出
B．先进先出
C．同进同出
D．同出同进
3．双向链表的指针域的个数为（）
A．0
B．1
C．2
D．3
4．完全二叉树，按层次序列编号（根结点编号为1），则编号为2的结点的左孩子的编号为（）
A．3
B．4
C．5
D．6
5．具有m个顶点的无向完全图的边的数目为（）
A．m（m+1）/2
B．m（m-1）/2
C．m（m-1）
D．m（m+1）
6．顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，则该顺序表的第3个元素地址是（）
A．102
B．104
C．106
D．108
7．数据的存储结构可分为链式存储结构和（）
A．顺序存储结构
B．哈希存储结构
C．索引存储结构
D．表存储结构
8．数据元素之间有四种基本逻辑结构，下列描述中是逻辑结构的是（）
A．圆形结构
B．树形结构
C．方形结构
D．菱形结构
9．下列不属于线性结构的是（）
A．线性表
B．栈
C．队列
D．图
10．满二叉树，按层次序列编号（根结点编号为1），则编号为3的结点的双亲编号为（）
A．1
B．2
C．3
D．4
11．第二代计算机是以（）为主要器件的。
A．电子管
B．晶体管
C．二极管
D．触发器
12．动态RAM基本电路单元是靠（）来寄存信息的。
A．电阻
B．电容
C．二极管
D．晶体管
13．主机、外设串行工作的方式是（）。
A．程序查询
B．程序中断
C．DMA
D．I/O处理机
14．以下有关运算器的叙述，正确的是（）。
A．只做加法运算
B．只做算术运算
C．既做算术运算又做逻辑运算
D．只做逻辑运算
15．指令周期是指（）。
A．CPU从主存取出一条指令的时间
B．CPU从主存取出一条指令加上执行指令的时间
C．节拍周期时间
D．时钟周期时间
16．某存储器芯片规格为8K×1位，则它的地址线和数据线共有（）根。
A．15
B．14
C．13
D．12
17．Cache是为解决CPU与（）之间速度不匹配而采用的一项技术。
A．硬盘
B．光盘
C．总线
D．内存
18．计算机系统I/O接口是（）之间的交接界面。
A．CPU与存储器
B．主机与外设
C．系统总线与CPU
D．CPU与Cache
19．DMA用于高速数据块的传送，直接在（）和外设之间进行数据传送。
A．内存
B．硬盘
C．CPU
D．Cache
20．在指令操作完成后，PC中存放的是（）。
A．下一条顺序执行的指令地址
B．当前指令的地址
C．转移指令的地址总线
D．停机指令的地址总线
21．微程序存放在（）中。
A．控制存储器
B．硬盘
C．指令寄存器
D．光盘
22．CPU响应中断的时间是（）。
A．任一机器周期结束时
B．外设提出中断时
C．取指周期结束时
D．一条指令执行结束时
23．能够改变程序执行顺序的（）。
A．数据传送指令
B．加法操作指令
C．跳转指令
D．输入输出指令
24．在主机中能对指令进行译码的器件是（）。
A．MAR
B．ALU
C．控制器
D．MDR
25．操作数在寄存器中的寻址方式称为（）寻址。
A．立即
B．直接
C．寄存器直接
D．基址
26．操作系统的主要功能是管理计算机系统中的资源，其中包括（）管理和存储器管理，以及设备管理和文件管理。
A．存储器
B．虚拟存储器
C．硬盘
D．处理机
27．从用户的观点看，操作系统是（）
A．用户与计算机之间的接口
B．控制和管理计算机资源的软件
C．合理地组织计算机工作流程的软件
D．由若干层次的程序按一定的结构组成的有机体
28．多道程序设计是指（）。
A．在实时系统中并发运行多个程序
B．在分布式系统中同一时刻运行多个程序
C．在一台处理器上同一时刻运行多个程序
D．在一台处理器上并发运行多个程序
29．下列选择中，当（）时，进程的状态从运行状态转为就绪状态。
A．进程被进程调度程序选中
B．进程时间片用完
C．进程等待I/O操作
D．进程I/O操作完成
30．进程控制块是描述进程状态的数据结构，一个进程（）。
A．可以有多个进程控制块
B．可以和其它进程共用一个进程控制块
C．可以没有进程控制块
D．只能有唯一的进程控制块
31．按照作业到达的先后顺序调度作业，排队等待时间最长的作业优先调度，这是指（）调度算法。
A．先来先服务
B．短作业优先
C．响应比高优先
D．时间片轮转
32．在下列存储管理方案中，不适应于多道程序设计的是（）。
A．单一连续区分配
B．固定式分区分配
C．可变式分区分配
D．段页式存储管理
33．访问磁盘的时间不包括（）。
A．寻道时间
B．CPU调度时间
C．读写时间
D．旋转等待时间
34．下面关于虚拟设备的论述中，正确的是（）
A．虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备
B．虚拟设备是指允许用户以标准化方式来使用物理设备
C．虚拟设备是把一个物理设备变换成多个对应的逻辑设备
D．虚拟设备是指允许用户程序不必全部装入内存便可使用设备系统中的设备。
35．文件系统的按名存取主要是通过（）来实现的。
A．存储空间管理
B．目录管理
C．文件安全性管理
D．文件读写管理
36．物理地址的长度是（）
A．16bit
B．32bit
C．48bit
D．128bit
37．下列传输介质中，传输光信号的是（）
A．双绞线
B．光纤
C．同轴电缆
D．电话线
38．下列描述中，属于多路复用技术的是（）
A．双分复用技术
B．频分复用技术
C．单分复用技术
D．角分复用技术
39．数据通信线路的工作模式分为单工通信、全双工通信和（）
A．多播通信
B．组播通信
C．半双工通信
D．P2P通信
40．下列协议中属于网络层协议的是（）
A．DNS
B．SMTP
C．IP
D．HTTP
二、综合题
41．计算程序段的时间复杂度（5分）
t=0;
for（i=1;i<=N;i++）
for（j=1;j<=N;j++）
for（k=1;k<=N;k++）
{t++;}
42．简答什么是栈？
什么是队列？
（10分）
43．假设二叉树采用如下的存储结构，其中lchild和rchild为分别指向左右孩子的指针。
typedefstructnode
{
intdata;
structnode*lchild,*rchild;
}TwoTree;
请编写一个算法，实现用递归方法求二叉树的深度。
（10分）
intdeeptree（TwoTree*bt）
44．什么是系统总线？
按照传输信息的不同，它又可分为几类？
是单向的还是双向的？
（7分）
45．简述CPU的基本组成与功能（8分）。
46．有三个进程P1,P2,P3并发工作。
进程P1需要资源S3和S1，进程P2需要资源S1和S2，进程P3需要资源S2和S3。
回答：
（1）若对资源分配不加限制，会发生什么情况，为什么，举例说明。
（4分）
（2）为保证进程正确工作，应采取怎样的资源分配策略，为什么？
（3分）
47．
（1）在请求系统中，什么时候会发生缺页中断？
（2分）
（2）设系统为某进程分配了3个物理块，该进程共有5个页面，考虑如下的页面引用顺序：
1,3,1,2,4,1,3，问：
A．按FIFO页面置换算法，访问第4号页面时，应淘汰第几号页面，共发生几次页面置换？
（3分）
B．按LRU页面置换算法，访问第4号页面时，应淘汰第几号页面，共发生几次页面置换？
（3分）
48．简答什么是数据？
什么是信号？
（7分）
49．简答OSI七层参考模型中物理层、网络层、传输层和应用层的主要功能是什么？
（8分）
第二部分 全国硕士研究生入学统一考试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语言程序
升级会员 