重庆理工大学计算机学科基础综合历年考研真题（2015-2019年）

W京理工人考

计算机学科专业基础综合

历年考研真题集(2015〜2019)

本真题集由考途学者倾情汇编，仅供研友学习！

真题集内容：

2019年重庆理工大学计算机学科基础综合考研真题

2018年重庆理工大学计算机学科基础综合考研真题

2017年重庆理工大学计算机学科基础综合考研真题

2016年重庆理工大学计算机学科专业基础综合考研真题

2015年重庆理工大学计算机学科专业基础综合考研真题

2019年重庆理工大学计算机学科基础综合考研真题

一、选择题（50分，25小题，每小题2分）

1.数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间

的（）和运算的学科。

A.结构B.关系C.数值D,算法

2.线性表是一个可在（）位置对数据元素进行插入、删除操作的序列容器。

A.仅表头B.仅表尾C.任意D.都是

3.将长度为〃的单链表连接在长度为m的仅带头指针的单链表后面，其算法的

时间复杂度为（）。

A.0（1）B.0（z?）C.0（血D.0（加+n）

4.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空

的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾

元素的下一个存储单元，队列的最大存储容量为maxSize,则队列的判空条件是

（）。

A.front==rearB.front!=rear

C.front==rear+1D.front==（rear+l）%maxSize

5.下面关于串的叙述中，不正确的是（）..

A.串是字符的有限序列B.空串是空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

6.对特殊矩阵采用压缩存储的目的主要是为了（）。

A.表达变得简单B.对矩阵元素的存取变得简单

C.去掉矩阵中的多于元素D.减少不必要的存储空间

7.对一棵满二叉树，有A个叶结点、B个结点、深度为C,则()0

A.B=C+1B.C+A=2BC.A=CTD.B=错误！未找到引用源。-1

8.任意一棵二叉树，其叶结点在先根遍历、中根遍历和后根遍历序列中的相对

次序()。

A.保持不变

B.先根遍历和中根遍历有变化，后根遍历无变化

C.先根遍历和后根遍历有编号，中根遍历无变化

D.中根遍历和后根遍历有变化，先根遍历无变化

9.一个有n个顶点的无向图最多有()条边。

A.nB.n(n-1)C.n(n-1)/2D.2n

10.对某个无向图的邻接矩阵来说，下列叙述正确的是()o

A.第i行上的非零元素个数和第i列上的非零元素个数一定相等

B.矩阵中的非零元素个数等于图中的边数

C.第i行与第i列上的非零元素的总数等于顶点v,的度数

D.矩阵中非零行的行数等于图中的顶点数

11.对于含有n个顶点的带权连通图，它的最小生成树是指图中的任意一个由

()子图。

A.n-1条权值最小的边构成的B.n-1条权值之和最小的边构成的

C.n-1条权值之和最小的边构成的连通

D.n个顶点构成的边的权值最小的边构成的极小连通

12.在用邻接表表示图时，拓扑排序算法的时间复杂度为()0

A.0(n)B.0(n+e)C.0(n)D.0(n)

13.内部排序算法的稳定性是指（）。

A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变

B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变

C.排序算法的性能与被排序元素个数关系不大

D.排序算法的性能与被排序元素个数关系密切

14.下列排序算法中，（）排序算法可能会出现下面的情况，初始数据有序

时，花费的时间反而更多。

A.快速B.堆C.希尔D.冒泡

15.在下列的排序中，序列（）是堆。

A.1,2,8,4,3,9,10,5B.1,5,10,6,7,8,9,2

C.9,8,7,6,4,8,2,1D.9,8,7,6,5,4,3,7

16.操作系统提供给应用程序的接口是（）。

A.P、V操作B.中断C.库函数D.系统调用

17.现代操作系统基本都采用缓冲技术，目的是为了（）0

A.提高编程效率B.提高CPU的处理速度

C.实现设备无关性D.提高设备和CPU之间的并行程度

18.下列哪个程序可以在用户态执行？（）

A.时钟中断处理程序B.游戏程序C.缺页处理程序D.进程调度程序

19.外存上存放的数据（）。

A.先要调入虚拟存储器中才能有CPU访问

B.CPU可直接访问

C.必须在访问前先装入主存

D.可以直接调入高速缓冲存储器中

20.下面哪个不属于I/O控制方式？（）

A.通道技术B.DMA方式C.覆盖方式D.中断方式

21.进程在系统中是否存在的唯一标志是（）。

A.数据集合B.目标程序C.源程序D.进程控制块

22.存储管理技术中通常采用对换技术，目的是（）0

A.提高内存利用率B.实现主存共享C.物理上扩充D.节省存储空间

23.在文件系统中，文件的属性可以集中存放在（）中以便查找。

A.索引B.作业控制块C.目录D.字典

24.下列哪种方式不能提高磁盘设备的I/O速度？（）

A.重排I/O请求次序B.优化文件的物理分布

C.预读和滞后写D.在一个磁盘上设置多个分区

25.操作系统需要解决的问题不包括（）。

A.提供程序保护和安全机制B.提供高级语言的编译器

C.提供应用程序接口D.管理目录，提供文件访问方式

二、综合题（100分，12小题）

26.（5分）假设一棵二叉树包含的结点数据值为1,4,9,3,20,请画出两棵高

度最大的二叉树。

27.（5分）一棵二叉树，其先根遍历序列为ABDCEGHF,中根遍历序列为DBAGEHCF,

请写出其后根遍历序列。

28.（5分）已知一无向图G=（V,E）,其中V={a,b,c,d,e）,E={（a,b）,（a,

d）,（d,c）,（b,e）},现用深度优先遍历方法从顶点a开始遍历图，写出所得

到的遍历序列。

29.（8分）假定某系统中有Zl、Z2、Z3三个资源，现有A,B,C三个进程并发工

作。如果各个进程运行需要的资源情况为：进程A需要资源Z3和Z1,进程B需

要资源Z1和Z2,进程C需要资源Z2和Z3。回答：

⑴若对资源分配不加限制，会发生什么情况，举例说明为什么。（3分）

（2）为保证各个进程正常推进，可能采取哪些资源分配策略，阐述原因？（5分）

30.（8分）进程运行过程中，可能引起进程状态变化的情况很多，简述什么是进

程调度，可能引起进程调度的情况有哪些？

31.（8分）在请求分页管理系统中，假定有5个作业，在某时刻作业要求访问的

页面顺序是4、1、2、3、1、2、4、1、3、2、1、3,若分配的物理块只有3块,

回答下列问题：

（1）解释什么情况下会发生缺页中断？（2分）

⑵分别采用FIFO、LRU和clock页面分配算法，写出内存块中页面的变化情况,

并求各种方式下缺页中断的次数和缺页率。（6分）

32.（7分）假设某通信的电文仅由4个字符组成，每个字符在电文中出现的频度

分别为｛32,7,24,2｝。

⑴请为这4个字符设计哈夫曼编码。（4分）

（2）该哈夫曼编码的平均码长是多少？与用2位二进制数（即00,01,10,11）

对这4个字符进行等长编码相比，哈夫曼编码使该电文的总长平均压缩了多少？

（3分）

33.（8分）请对如图所示的无向图:

写出它的邻接矩阵（4分），并按照克鲁斯卡尔算法求其最小生成树（4分）。

34.（10分）设哈希函数为H（key）=keymod13,试用关键字序列｛39,25,15,

54,26,24,14,21,37,38｝构造哈希表。使用链地址法处理冲突，画出该哈

希表的存储结构图（7分）；在等概率的情况下，计算查找成功时的平均查找长度

（3分）。

35.（10分）有一个带头结点的单链表L,设计一个算法，使其元素递增有序。

36.（12分）有一组进程Pl,P2,P3,P4,P5需要运行，它们需要的CPU时间和

优先级如下表。假定这五个进程在0时刻按P5,P4,P3,P2,P1的顺序到达，

在执行过程中不会发生等待，忽略进程调度所花费的时间，从0时刻开始进程

调度，请回答下面的问题：

进程要求的处理时优先级

间

P513

P444

P315

P231

P123

（1）画出采用先来先服务、短作业优先、时间片轮转的调度算法时，进程执行顺

序的甘特图。（4分）

⑵计算每个进程的周转时间和平均周转时间。(4分)

(3)计算每个进程的等待时间和平均等待时间。(4分)

37.(14分)某快递仓库的工作人员分为两类：快递姐和快递哥，快递姐的任务是

接收从外地送到本仓库的快件，快递哥的任务是将本仓库中的快件送到客户手

里。该仓库一共能存放2000个快件包裹，当仓库未装满时，快递姐可以接收快

件放入仓库，否则等待；当仓库不空时，快递哥可以从仓库中取走快件装车，

否则等待。要求每次每个快递哥从仓库连续取出30件产品后，其他快递哥才可

以从仓库中取快件，请用信号量和P,V操作实现快递姐和快递哥的操作互斥和

同步，要求写出完整的过程；并指出所用信号量的含义和初值。

2018年重庆理工大学计算机学科基础综合考研真题

一、单选题(每小题2分，共40分)

1.算法分析的目的是()。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和稳定性

2.设某算法完成对n个元素进行处理所需的时间是:T(n)=2001og2n+1000n(log2n

+100)+100000,则该算法的时间复杂度是()。

A.0(1)B.0(n)C.0(nlog2n)D.0(nlog2n+log2n)

3.若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个

元素，则采用()存储方式最节省运算时间。

A.单链表B.双链表C.单循环链表D.带头结点的双循环链表

4.在中缀表达式转化为后缀表达式与后缀表达式求值算法中，都需要用到哪种

特殊的数据结构()。

A.栈B.队列C.二叉树D.堆

5.一个队列的入队序列是1,2,3,4,则队列的出队序列只能是()。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1

6.将含有100个结点的完全二叉树从根结点开始编号，根为0号，后面按从上

到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为

()O

A.42B.40C.21D.20

7.如果在某二叉树的前序序列、中序序列和后序序列中，结点b都在结点a的后

面(即形如…a・“b…),则最有可能的情况是()o

A.a和b是兄弟B.a是b的双亲

C.a是b的左孩子D.a是b的右孩子

8.某二叉树的后序遍历序列是dabec,中序遍历序列是debac,其前序遍历序

列是()o

A.acbedB.decabC.deabcD.cedba

9.下述编码中，哪一个不是前缀码()。

A.(0,10,110,111)B.(11,10,001,101,000)

C.(00,010,011,1)D.(1,01,000,001)

10.一个有n个顶点的无向图最多有()条边。

A.nB.n(n-l)C.n(n-l)/2D.2n

11.在现代操作系统中，采用缓冲技术的主要目的是()

A.改善用户编程环境B.提高CPU的处理速度

C.实现与设备无关D.提高设备与CPU之间的并行程度

12.下列哪个事件不可能在用户态发生？（）

A.系统调用B.外部中断C.进程切换D.缺页

13.操作系统是对（）进行管理的软件。

A.软件B.硬件C.计算机资源D.应用程序

14.子程序调用和中断处理子程序都是以压入堆栈的方式来保护现场的，下面

哪个寄存器中的内容是中断处理一定会保存而子程序调用不用保存的？（）

A.程序计数器B.通用地址寄存器

C.通用数据寄存器D.程序状态寄存器

15.进程和程序的一个本质区别是（）

A.进程是动态的，程序是静态的B.进程存储在内存，程序存储在外存

C.进程在一个文件中，程序在多个文件中D.进程分时使用CPU,程序独占

CPU

16.下列不属于I/O控制方式的是（）

A.程序查询方式B.覆盖方式C.DMA方式D.中断方式

17.在内存采取分区管理方式时，分区的保护措施主要是（）

A.界限寄存器进行地址保护B.程序状态保护

C.用户权限保护D.存取控制保护

18.在一个文件被用户进程首次打开的过程中，操作系统需做的是（）

A.将文件内容读入内存B.将文件控制块读入内存

C.修改文件控制块的读写权限D.将文件的数据缓冲区首指针返回给用户进

程

19.计算机系统的二级存储包括（）

A.CPU寄存器和主存缓存B.超高速缓存和内存储器

C.主存储器和辅助存储器D.ROM和RAM

20.在不同速度的设备之间传送数据（）

A.必须采用同步控制方式B.必须采用异步控制方式

C.可用同步方式，也可以用异步方式D.必须采用应答方式

二、综合题（110分）

21.（本小题共5分）有如下递归函数fact（n）,分析其时间复杂度。

fact（intn）{

if（n<=l）return（1）；①

elsereturn（n*fact（n-1））；②

}

22.（本小题共5分）有一种数据结构Bl=（AR）,其中：加{48,25,64,57,

82,36,75},庐{<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,

82>},画出其逻辑结构表示（3分），指出是什么类型的逻辑结构？（2分）

23.（本小题共10分）有数据{43,54,90,46,31},列出冒泡排序每趟的结果

（6分）。编写冒泡排序算法BubbleSort（RecTypeR口,intn）的实现程序（4分）。

24.（本小题共10分）假设哈希表长度炉13,采用除留余数法哈希函数建立如下

关键字集合的哈希表：（16,74,60,43,54,90,46,31,29,88,77）。并

采用线性探查法解决冲突。

25.（本小题共5分）有一组关键字序列{66,89,8,123,9,44,55,37,200,

127,98},请将其调整成初始大根堆，画出初始大根堆的树型表示。

26.（本小题共9分）有一份电文中，使用了a、b、c、d这4个字符，各字符出

现频率如下表。

字符abcd

出现频率231135

试构造对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的

次序构造）（6分），并求出每个字符的哈夫曼编码（3分）。

27.（本小题共8分）对于如图所示的带权无向图，给出利用普里姆算法（从顶

点0开始构造）构造出的最小生成树的结果。（注意：按求解的顺序给出最小生

成树的所有边，每条边用（，，力表示，顺序错误不给分！）

28.（本小题共8分）有如下工程项目的AOE图，其中数字表示该项活动需要的

天数：

（1）列出图中各顶点（事件）的最早发生时间和最迟发生时间（4分）。

（2）计算完成该项目所需的时间，指出哪些是关键活动（2分）。

（3）缩短任一关键活动的时间，是否会缩短整个工程的时间？（2分）

29.（本小题共8分）现代操作系统采用分层设计，用户程序发出磁盘I/O请求

后需经过4个层次的调用才能进行实际的I/O操作，阐述系统进行I/O操作的4

个层次和具体的处理流程。

30.（本小题共8分）在多道系统中，由于有多个进程运行可能导致死锁，阐述

什么是死锁，有哪些情况可能会导致死锁，并简要说明阐述死锁的条件。

31.（本小题共10分）一个多道批处理系统中仅有A1和A2两个作业，A2比A1

晚10ms到达，它们的计算和I/O操作顺序如下：

A1：计算60ms,I/O80ms,计算20ms

A2：计算120ms,I/O40ms,计算40ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是多少？说明

计算依据？并用示意图表示进程的运行时间图。

32.（本小题共10分）解释什么是最佳适应分区分配算法和最坏适应分区分配算

法？各自的空闲分区是怎样组织的？各有什么缺点？设主存的分配情况如下图

所示。当有一个用户进程U需申请45KB的存储区时，若采用最佳适应和最坏适

应进行分配，U所分到的分区首地址分别为多少？

512KB-1

33.（本小题共14分）某企业有多个生产线和多个销售人员，他们共用可存放100

个产品的仓库，当仓库未装满时，生产线可以将生产的一件产品放入仓库，否

则等待；当仓库不空时，销售人员可以取走一件产品出售，否则等待。要求一

个销售人员从仓库连续取出5件产品后，其他销售人员才可以取产品，请用信

号量P,V（wait,signed）操作实现进程间的互斥和同步，要求写出完整的过

程；并指出所用信号量的含义和初值。

2017年重庆理工大学计算机学科基础综合考研真题

一.单选题（每题2分，共50分）

1.数据元素之间的存储结构，除了链式存储结构，另外一种存储结构是（）

A.线性存储结构B.树形存储结构C.顺序存储结构D.图形存储结

构

2.图形结构之间是（）

A.一对多关系B.一对一关系C.多对多关系D.一对二关系

3.算法有5个特性，下列哪项不是算法的特性（）

A.有穷性B.输入C.可行性D.队列

4.带头结点的单链表H为空的条件是（）

A.H==NULLB.H->next==NULLC.H!=NULLD.H->next!=NULL

5.完全二叉树，按层次序列对每个结点编号（根结点编号为1）,则编号为8的

结点的双亲编号为（）

A.3B.4C.5D.6

6.下列属于线性结构的是（）

A.栈B.树C.查找D.图

7.顺序表的第1个元素存储地址是700,每个元素占用3个存储单元，则该顺

序表的第4个元素地址是（）

A.703B.706C.709D.712

8.8个顶点连通图的最小生成树中边的数目是（）

A.4B.5C.6D.7

9.深度为5（根的层次号为1）的满二叉树结点个数为（）

A.15B.16C.31D.32

10.在一个无向图中，边的数目为6,则所有顶点的度数之和为（）

A.6B.12C.18D.24

11.有一个有序表为｛4,5,7,8,9）,当折半查找到4时，需要的比较次数为

)

A.1B.2C.3D.4

12.一个栈的入栈顺序是ABCDEF,则该栈不可能的输出序列是（）

A.ABCDEFB.FEDCBAC.DCBAEFD.CABFDE

13.完全二叉树共有22个结点，按层次序列对每个结点编号（根结点编号为1）,

则编号为4的结点的右孩子编号为（）

A.7B.8C.9D.10

14.设先序遍历某二叉树的序列为ABCDE,中序遍历该二叉树的序列为CBAED,

则后序遍历该二叉树的序列为（）

A.ABCDEB.CBAEDC.CBEDAD.CBDEA

15.深度为4（根结点的层次号为1）的满二叉树的叶子节点个数为（）

A.8B.10C.12D.16

16.在汽车电子系统中使用的操作系统属于（）

A.个人计算机操作系统B.分布式操作系统

C.嵌入式操作系统D.批处理操作系统

17.下列选项不属于操作系统的特征的是（)

A.并发性B.共享性C.虚拟性D.确定性

18.在操作系统中，一般不实现进程从（）状态的转换

A.就绪一等待B.执行一就绪C.就绪~执行D.等待一就绪

19.对进程的控制和管理使用（）

A.原语B.指令C.信号量D.通信

20.下列进程调度算法中，综合考虑等待时间和执行时间的是（）

A.时间片轮转调度算法B.短进程优先调度算法

C.先来先服务调度算法D.高响应比优先调度算法

21.死锁和安全状态的关系是（）

A.死锁状态有可能是安全状态B.死锁状态一定是不安全状态

C.安全状态也可能是死锁状态D.不安全状态必定产生死锁

22.为了保证CPU执行程序指令时，能够正确访问内存单元，需要将用户进程

中的逻辑地址转换为运行时可由CPU寻址的物理地址，这一过程称为（）

A.地址分配B.地址映射C.地址计算D.地址查询

23.下列关于虚拟存储的叙述中，正确的是（)

A.虚拟存储容量只受外存容量的限制

B.虚拟存储容量只受内存容量的限制

C.虚拟存储只能基于连续分配技术

D.虚拟存储只能基于非连续分配技术

24.在I/O数据传送控制中，CPU干预最少的是（）

A.中断控制方式B.DMA方式C.通道方式D.程序直接控制方式

25.文件系统采用多级目录结构后，对于不同用户的文件，其文件名（）

A.应该相同B.应该不同C.可以相同，也可以不同D.受系统约束

二.简答题（每题5分，共50分）

26.队列的定义是什么？队列的特点是什么？（5分）

27.计算程序段的时间复杂度（N为常量）和@语句的语句频度（5分）

m=0;

for（i=l;i<=N;i++）

for（j=l;j<=N;j++）

{@m++;}

28.设有一序列25,16,3,88,13,58,请按该序列构成一棵二叉排序树，并

求其查找成功时的平均查找长度ASL。（5分）

29.设给定权集W={3,4,5,8,9},试构造关于W的一棵赫夫曼树，并求其带

权路径长度WPL。（5分）

30.树的定义是什么？树的元素之间的关系是什么？（5分）

31.高级调度和低级调度的主要任务是什么？为何要引入中级调度？（5分）

32.请简要说明分页式和分段式内存管理的异同。（5分）

33.什么是SPOOLing技术？SPOOLing系统有哪几部分组成？（5分）

34.如果信号量的初值是5,现在信号量的值是-5,那么系统中的相关进程至少

执行了几个P（S）操作？与信号量S相关的处于阻塞状态的进程有几个？如果要

使信号量的值大于0,应该进行怎样的操作？（5分）

35.三个进程共享四个资源，这些资源的分配与释放只能一次一个。已知每一

进程最多需要两个资源，问该系统会发生死锁吗？请说明理由。（5分）

三.综合题（共50分）

36.假设二叉树采用如下的存储结构，其中Ichild和rchild为分别指向左右

孩子的指针。

typedefstructnode

{

intdata;

structnode*lchild,*rchild;

}TwoTree;

编写2个算法，分别用递归方法求二叉树的深度（Deeptree）和二叉树叶子结

点个数（Leafcount）o（10分）

intDeeptree（TwoTree*bt）/*bt为指向二叉树的根结点的指针*/

intLeafcount（TwoTree*bt）/*bt为指向二叉树的根结点的指针*/

37.编写2个算法，分别实现对数组a（元素个数为n）中元素进行简单选择排序

（selectsort）和快速排序（quicksort）算法，其中low为下界，high为上界。

（15分）

voidselectsort（inta[],intn）

voidquicksort（inta[],intlow,inthigh）

38.（10分）某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页

号占6位，页大小为1KB,请分析：

（1）该系统的内存空间大小为多少？每个内存块的大小为多少？（4分）

（2）逻辑地址共几位？每个作业最大长度为多少？（4分）

（3）若某作业的第0、1、2页分别放在内存的第3、7、9块中，则逻辑地址0420H

对应的物理地址是多少？（2分）

39.（15分）假设磁盘有200个磁道，磁盘请求到达次序为98,183,37,122,

14,125,60,66,当前磁头在53号磁道上，并向磁道号减小的方向移动。

（1）采用FCFS（先来先服务）进行磁盘调度时，请分析上述磁盘请求对应的磁

盘服务次序，并计算平均寻道长度。（5分）

（2）采用SSTF（最短寻道时间优先）进行磁盘调度时，请分析上述磁盘请求对

应的磁盘服务次序，并计算平均寻道长度。（5分）

（3）采用SCAN（扫描算法）进行磁盘调度时，请分析上述磁盘请求对应的磁盘

服务次序，并计算其平均寻道长度。（5分）

2016年重庆理工大学计算机学科专业基础综合考研真题

一.单选题（每题2分，共50分）

1.数据元素之间有4种逻辑结构，下列不属于数据元素的逻辑结构是（)

A.线性结构B.树形结构C.图形结构D.队列

2.数据结构的二元组结构8=（D,R）,其中D是数据元素的集合，口是（）

A.关系的集合B.线性的集合C.树形的集合D.图形的集合

3.算法有5个特性，下列不属于算法特性的是（）

A.输入B.输出C.可行性D.方法

4.单链表中每个结点的指针域的个数为（）

A.1B.2C.3D.4

5.完全二叉树，按层次序列对每个结点编号（根结点编号为1）,则编号为3的

结点的双亲编号为（）

A.1B.2C.3D.4

6.下列不属于线性结构的是（）

A.线性表B.栈C.队列D.图

7.顺序表的第1个元素存储地址是2000,每个元素占用2个存储单元，则该顺

序表的第3个元素地址是（）

A.2002B.2004C.2006D.2008

8.n个顶点连通图的生成树中边的数目是（)

A.nB.n+1C.n-lD.2n

9.深度为1（根的层次号为1）的满二叉树结点个数为（）

A.1B.3C.7D.8

10.在一个无向图中，边的数目为4,则所有顶点的度数之和为（）

A.4B.8C.16D.32

11.有一个有序表为U，2,3},当折半查找到2时，需要的比较次数为（）

A.1B.2C.3D.4

12.一个栈的入栈顺序是BCD,则该栈的不可能的输出序列是（）

A.BCDB.DCBC.CBDD.DBC

13.完全二叉树共有15个结点，按层次序列对每个结点编号（根结点编号为1）,

则编号为3的结点的右孩子编号为（）

A.6B.7C.8D.9

14.设先序遍历某二叉树的序列为AB,中序遍历该二叉树的序列为BA,则后序

遍历该二叉树的序列为（）

A.ABB.BAC.ACD.CA

15.下列是图的存储结构的是（）

A.数组B.邻接表C.线性表D.栈

16.在普通用户看来，操作系统是（）

A.用户与计算机之间的接口B.控制和管理计算机的接口

C.合理地组织计算机工作流程的软件D.计算机资源的管理者

17.并发和下面哪个是操作系统的基本特征，两者之间互为存在条件？（）

A.虚拟B.异步C.共享D.可扩展性

18.通道是一种（）

A.I/O中断口B.共享文件C.I/O专用处理机D.数据通道

19.作业从进入后备队列到被调度程序选中的时间称为（）

A.周转时间B.响应时间C.触发时间D.等待时间

20.临界区是指（）

A.公共数据区B.临时工作区C.系统管理区D.与共享变量有关的程序

段

21.进程调度的关键问题是（)

A.时间片大小B.进程调度算法C.CPU速度D.内存空间的大小

22.下列哪种存储方式不能实现虚拟存储（）

A.分区B.页式C.段式D.段页式

23.操作系统处理缺页中断时，选择一种好的调度算法对内存和外存中的信息

进行高效调度，必须尽可能避免（）

A.碎片B.CPU空闲C.多重中断D.抖动

24.对随机存取的文件，在磁盘上必须组织成（）

A.有序文件B.索引文件C.连续文件D.链接文件

25.在多级文件结构中，要访问一个文件时，必须指出文件的（）

A.父目录B.当前目录C.路径名D.根目录

简答题（每题5分，共50分）

26.数据结构的定义是什么？（5分）

27.设给定权集W={1,3,5,9）,试构造关于W的一棵赫夫曼树，并求其带权

路径长度WPL。（5分）

28.设有一序列25,18,6,44,请按该序列构成一棵二叉排序树，并求其查找成

功时的平均查找长度ASL。（5分）

29.写出下图所示二叉树的先序，中序和后序遍历序列。（5分）

30.已知待散列的线性表为（7,12,13,17,10）,散列用的一维地址空间为

[0..5],假定选用的散列函数是H（K）=Kmod6,若发生冲突采用线性探查

法处理，计算出每一个元素的散列地址并在下图中填写出散列表。（5分）

012345

31.什么是进程，进程和程序有哪些不同？（5分）

32.说明进程的三种基本状态以及各状态之间的转换。（5分）

33.什么是死锁，产生死锁有哪几个条件？（5分）

34.什么是虚拟存储器，虚拟存储器有什么特点，如何实现虚拟存储地址的转

换？（5分）

35.中断和DMA有什么异同？（5分）

三.综合题（共50分）

36.编写函数，实现对二叉树的后序遍历（postorder）的递归算法。（10分）

二叉树结点的结构体为

structBiTreeNode{

intdata;

structBiTreeNode*leftChild;

structBiTreeNode*rightChild;

}；

typedefstructBiTreeNodeNode;

voidpostorder（Node*t）/*t为指向二叉树的根结点的指针*/

37.编写两个函数，分别实现对数组a（元素个数为n）中元素进行冒泡排序和简

单选择排序的算法。（15分）

voidmaopaosort（inta[],intn）

voidxuanzhesort（inta[],intn）

38.在微信操作的程序中，假设有一个邮箱，有4个程序A、B、C、D对该邮箱

进行操作，A写入的数据X只能被C使用，B写入的数据Y只能被B使用，A、B

写入数据后C、D才能使用，C、D使用一次数据后不能再重复使用，只有等到A、

B再次写入后才能使用。规定邮箱中一次只能存放一个数据。请用信号量的方式

实现这几个进程之间的同步和互斥关系。（10分）

39.（本题共15分）在一个多道作业批处理系统中，作业调度采用短作业优先

的调度算法，设有下列作业序列：

作业名到达时间预估运行时间优先级

18:00308

28:20405

38:20207

48:30106

其中给出的作业优先级即为进程的优先级，其数值越小，优先级越高。要求：

（1）如果进程调度采用抢占式优先调度算法。列出所有作业进入内存的时间及

结束时间。并计算周转时间和平均周转时间。（5分）

（2）如果进程采用非抢占式调度，结果又如何？（5分）

（3）分析哪种调度方式更好？（5分）

2015年重庆理工大学计算机学科专业基础综合考研真题

一.单选题（每题2分，共50分）

1.一个栈的入栈顺序是a,b,c,d,e,则该栈的输出序列不可能是（）

A.abodeB.aecbdC.cbadeD.edcba

2.二叉树的二叉链表的指针域的个数为（）

A.0B.1C.2D.3

3.队列的删除操作在（）

A.队头B.队尾C.栈顶D.栈底

4.设一组初始记录关键字序列（4,2,3,7）,进行一趟简单选择排序的结果为

（）

A.4,2,3,7B.4,2,7,3C.2,7,4,3D.2,4,3,7

5.设先序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BCAD,则

后序遍历该二叉树的序列为（）

A.ABCDB.BCADC.CBDAD.CDBA

6.深度为5的二叉树（根结点层次为1）至多结点个数为（）

A.15B.31C.32D.63

7.有7个顶点的无向连通图最少边数为（）

A.5B.6C.7D.8

8.三元组表用于表示（）

A.线性表B.双向链表C.稀疏矩阵D.栈

9.设无向图G中有n个顶点，则该无向图的最小生成树上边的数目为（）

A.n-lB.nC.2n-lD.2n

10.有序表为{3,5,7,9,30},当折半查找到3时，需要的比较次数为（）

A.1B.2C.3D.4

11.设有一个10阶的下三角矩阵A（包括对角线），按照以行为序进行顺序存储

到连续的55个存储单元中，每个元素占1个字节的存储空间，如果A[0][0]存

储地址为100,则A[4][3]的存储地址为（）

A.IllB.112C.113D.114

12.与&a[i]等价的是（）

A.*（a+i）B.a+iC.*a+iD.&（a+i）

13.完全二叉树共有20个结点，按层次序列对每个结点编号（根结点编号为0）,

则编号为7的结点的右孩子编号为（）

A.13B.14C.15D.16

14.在一个无向图中，边的数目为8,则所有顶点的度数之和为（）

A.16B.8C.24D.32

15.下列不属于算法的五个重要特性的是（）

A.有穷性B.确定性C.输入D.描述性

16.操作系统的主要功能是（）。

A.提高系统的运行速度B.增强计算机系统的功能

C.合理组织系统的工作流程D.提高系统资源的利用率

17.关于程序的并发，下列叙述正确的是（）0

A.并发是指若干事件在同一时刻发生

B.并发是指若干事件在不同时刻发生

C.并发是指若干事件在同一时间间隔内发生

D.并发是指若干事件在不同时间间隔内发生

18.进程生存期中的状态不包括下列哪一种（）。

A.就绪B.执行

C.阻塞D.等待

19.分时系统的响应时间（及时性）主要是根据下面哪一个来确定的？

（）

A.时间片B.用户数目

C.用户所能接受的等待时间D.控制对象所能接受的时延

20.下面关于临界区的论述中，哪条是正确的？（)

A.临界区是指进程中用于访问临界资源的那段代码

B.临界区是指进程中用于实现进程互斥的那段代码

C.临界区是指进程中用于实现进程同步的那段代码

D.临界区是指进程中用于实现进程共享的那段代码

21.下列算法中，哪一个是只能采用非抢占调度方式？（）

A.高优先级优先法B.时间片轮转法

C.FCFS调度