升研教育考研频道为23考研、24考研的同学们整理了“重庆理工大学2020年考研真题：812计算机学科基础综合”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

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

报考学科、专业名称：计算机科学与技术

考试科目(代码)：812计算机学科基础综合

一、单项选择题(每小题2分，共50分)

1、存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。

A、数据的操作方法

B、数据元素的类型

C、数据元素之间的关系

D、数据的存取方法:

2、顺序存储设计时，存储单元的地址()。

A、一定连续

B、一定不连续

C、不一定连续，

D、部分连续，部分不连续

3、下面关于算法说法正确的是()。

A、算法最终必须由计算机程序实现

B、为解决某问题的算法与为该问题编写的程序含义是相同的

C、算法的可行性是指指令不能有二义性

D、以上几个都是错误的

4、线性表是一个()位置对数据元素进行插入、删除操作的序列容器。

A、仅可在表头

B、仅可在表尾

C、可在任意

D、都是

5、用链接方式存储的队列，在进行删除运算时()。

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

6、对一棵具有30个结点的树，该树中所有结点的度之和为()。

A、28

B、29

C、30

D、31

7、一棵完全二叉树上有2001个节点，其中叶节点的个数为()。

A、500

B、1000

C、525

D、1001

8、以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中，编码最大的长度为()。

A、2

B、3

C、4

D、5

9、若邻接表中有奇数个边结点，则一定是()。

A、图中有奇数个结点

B、图中有偶数个结点

C、图为无向图

D、图为有向图

10、除了使用拓扑排序的方法，还可以利用()的方法来判断一个有向图是否有回路。

A、求关键路径

B、求最短路径

C、深度优先搜索

D、广度优先搜索

11、对AOE网(边活动图)的关键路径，下面的说法()是正确的。

A、提高关键路径上的一个关键活动的速度，必然使整个工程缩短工期

B、完成工程的最短时间是从始点到终点的最短路径的长度

C、一个AOE网(边活动图)的关键路径只有一条，但关键活动可有多个

D、任何一项活动持续时间的改变都可能影响关键路径的改变

12、一个排序算法的时间复杂度与()有关。

A、排序算法的稳定性

B、所需比较关键字的次数

C、所采用的存储结构

D、所需辅助存储空间的大小

13、每次直接比较两个相邻元素，若出现逆序排列时就交换它们的位置，此种排序方法称为()。

A、堆排序

B、选择排序

C、快速排序

D、冒泡排序

14、对于二分查找法，一般选择()作为其存储结构。

A、顺序表

B、循环表

C、双链表

D、单链表

15、已知一棵由关键字集合{18，43，27，77，44，36，39}所构造的二叉排序树，对该树进行中序遍历，得到的结点序列为()。

A、树形未定，无法确定

B、18，43，27，77，44，36，39

C、18，27，36，39，43，44，77

D、77，44，43，39，36，27，18

16、从用户来看，操作系统的作用是()。

A、由若干层次的程序按一定的结构组成的有机体

B、控制和管理计算机资源的软件

C、用户与计算机之间的接口

D、合理地组织计算机工作流程的软件

17、操作系统使用缓冲技术的目的是()。

A、提高编程效率

B、提高CPU的处理速度

C、实现设备无关性

D、提高设备和CPU之间的并行程度

18、进程是程序的运行，()是进程存在的唯一标志。

A、JCB

B、代码段

C、FCB

D、PCB

19、操作系统提供给程序员的接口是()。

A、进程

B、库函数

C、系统调用

D、库函数和系统调用

20、下面关于操作系统的叙述正确的是()。

A、分时系统都具有人机交互功能

B、从响应时间来看，实时系统与分时系统差不多

C、由于采用了分时技术，用户可以独占计算机的资源

D、批处理作业必须具有作业控制信息

21、虛拟存储器是()。

A、由CPU寄存器和主存构成

B、由高速缓存和内存储器组成

C、由主存储器和辅助存储器构成

D、由ROM和RAM构成

22、信箱通信是一种()通信方式。

A、直接

B、间接

C、低级

D、信号量

23、发生中断时，下面哪个寄存器必须保存后才能响应中断()。

A、通用数据寄存器

B、通用地址寄存器

C、指令寄存器

D、程序状态寄存器

24、把作业地址空间使用的逻辑地址变为内存的物理地址，称为()。

A、加载

B、物理化

C、重定位

D、逻辑化

25、文件系统采用多级目录结构后，对于不同用户的文件()。

A、应该相同

B、应该不同

C、可以相同也可以不同

D、受系统约束

二、综合题(共100分)

26、(本小题5分)简述顺序存储结构和链式存储结构的适用场合。

27、(本小题5分)编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。

28、(本小题5分)对序列F，B，W，A，E，H按字母表顺序从小到大进行排序。分别写出二路归并排序、直接插入排序、冒泡排序、简单选择排序、快速排序第一趟排序的结果。

29、(本小题6分)利用逐个数据插入的方法建立序列{36，46，26，56，51，11，16，31，41，21}对应的二叉排序树后

(1)在该树上查找21需要进行的比较次数为多少?

(2)查找成功平均的比较次数是多少?

(3)查找失败的平均比较次数又是多少?

30、(本小题8分)假设一颗二叉树包含的结点数据值为1，3，5，7，9，请画出(1)两棵不同的高度最小的二叉树;(2)两棵不同的完全二叉树，要求每个双亲节点的数据值均小于其孩子节点的数据值。

31、(本小题6分)请写出下图G的邻接矩阵和邻接表。

32、(本小题8分)用克鲁斯卡尔(Kruskal)算法构造下图G的一棵最小生成树，试画出构造过程，并写明每一步的状态。

33、(本小题7分)将一组关键字{8，3，17，11，22}依次插入到初值为空的哈希表中，已知哈希函数为H(key)=keymod7，用线性探查法处理冲突。

画出该哈希表的存储结构图。在等概率情况下，计算查找成功的平均查找长度和查找失败的平均查找长度。

34、(本小题6分)什么是操作系统，计算机系统中配置操作系统的主要目的是什么?操作系统有什么基本特征?

35、(本小题6分)多个进程并发运行时会发生死锁，简述什么是死锁，按序分配是防止死锁的一种策略，简述什么是按序分配，为什么说按序分配可以防止死锁?

36、(本小题8分)处理机对IO设备的控制是不断发展的，简述在I/O控制方式中，中断控制方式和DMA控制方式的异同。

37、(本小题8分)在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2，回答以下问题:

(1)简述什么是缺页中断，在情况下会发生缺页中断?(4分)

(2)试用FIFO和LRU两种页面分配算法，写出内存块的变化，并求各种方式下缺页中断的次数和缺页率。(4分)

38、(本小题10分)有一个两道的批处理操作系统，现有一组作业到达时间、要求处理的时间和优先级如下表，作业调度采用最短作业优先调度算法，进程调度采用基于优先数(优先数大的进程优先级高)的抢占式调度算法，求解如下问题:

(1)列出所有作业提交内存的时间、运行结束时间、周转时间、带权周转时间、等待时间;(7分)

(2)计算全部作业的平均周转时间、带权平均周转时间、平均等待时间。(3分)

39、(本小题12分)在微信后台，有对微信用户发送的信息进行内容审核的机制，该工作可能由人来完成，也可能由robot来完成，统称审核人员。

只有通过审核人员审核后的信息才能发送给对方用户。假定微信用户和审核人员共用一个可以存放1000条信息的缓冲区(初始为空)，当缓冲区未满时，微信用户可以发送一条信息到缓冲区，否则等待;当缓冲区不空时，审核人员可以取出信息进行审核，否则等待。要求一个审核人员一次从缓冲区中取出10条信息进行审核(除非缓冲区中的信息本来就少于10条，此时取完也可以开始审核)，然后其他审核人员才能取出信息或者用户才能放入信息。请用信号量、P、V(wait，signal)操作实现进程间的互斥和同步，要求写出完整的过程，并指出所用信号量的含义和初值。