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

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

适用专业：0812计算机科学与技术

一、单项选择题（每小题2分，共60分）

1、下列（  ）结构中的数据元素的关系是“多对多”的关系。

A、线性表

B、二叉树

C、栈与队列

D、图

2、存储设计时，存储单元的地址一定连续的是（  ）存储。

A、顺序

B、链式

C、索引

D、散列

3、算法的描述要做到便于阅读、利于理解和修改，该特性称为（  ）。

A、正确性

B、健壮性

C、可读性

D、可移植性

4、栈是一个（  ）位置对数据元素进行插入、删除操作的序列容器。

A、仅可在一端

B、可在两端

C、可在任意

D、以上都是

5、假设在顺序表{a₀，a₁，……，a_n-1}中，每一个数据元素所占的存储单元的数目为8，且第一个数据元素a₀的存储地址为100，则第4个数据元素a₃的存储地址是（  ）。

A、106

B、107

C、124

D、128

6、将有尾指针的长度为n的单链表连接在有尾指针的长度为m的单链表后面，其算法的时间复杂度为（  ）。

A、O(1)

B、O(n)

C、O(m)

D、O(m+n)

7、若进栈顺序为a，b，c，则可能得到（  ）种不同的出栈序列。

A、5

B、6

C、7

D、8

8、设长度为n的链队列采用单循环链表表示，若只设一个头指针指向队首元素，则出队操作的时间复杂度为（  ）。

A、O(1)

B、O(n)

C、O(log2n)

D、O(n2)

9、下面（  ）不是栈的基本操作。

A、删除栈顶元素

B、删除栈底元素

C、判断栈是否为空

D、将栈置为空栈

10、有一个二维数组A[1…9，1…8]，每个数组元素用相邻的4个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（  ）个字节。

A、48

B、96

C、252

D、288

11、假设树中度为1，2，3和4的结点个数分别是1，2，3，4，则该树中叶结点的个数为（  ）。

A、6

B、7

C、8

D、9

12、假设一棵二叉树的结点个数为1000，则它的最大深度是（  ）。

A、997

B、998

C、999

D、1000

13、一棵完全二叉树上有100个结点，其中叶结点的个数为（  ）。

A、48

B、49

C、50

D、51

14、若某棵二叉树的先序遍历序列为ABDCE，中序遍历序列为DBAEC，则后序遍历序列为（  ）。

A、CBEDA

B、DECBA

C、DEBCA

D、DBECA

15、一棵非空二叉树的后序遍历与中序遍历正好相同，则该二叉树满足（  ）。

A、所有结点无左孩子

B、所有结点无右孩子

C、只有一个根结点

D、任意一棵二叉树

16、在有n个非叶结点的哈弗曼树中，叶结点的总数为（  ）。

A、n-1

B、n

C、n+1

D、2n

17、一个有n个顶点的无向图最多有（  ）条边。

A、n

B、n(n-1)

C、n(n-1)/2

D、2n

18、n个顶点的有向图，若所有顶点的出度之和为s，则所有顶点的入度之和为（  ）。

A、s

B、s-1

C、s+1

D、n

19、若有向图的邻接矩阵，则该图共有（  ）条弧。

A、7

B、6

C、5

D、3

20、下面哪一方法可以判断出一个有向图是否有回路（  ）。

I、深度优先搜索；II、拓扑排序；III、求最短路径；IV、求关键路径

A、I、II

B、I、III、IV

C、I、II、III

D、全部可以

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

A、计算机软件

B、计算机硬件

C、计算机资源

D、应用程序

22、在物理计算机上配置了操作系统后，这台计算机的功能就增强了，这样的一台计算机只是一台逻辑上的计算机，称为（  ）计算机。

A、并行

B、真实

C、虚拟

D、共享

23、多道程序环境下，操作系统分配资源是以（  ）为基本单位。

A、程序

B、进程

C、指令

D、作业

24、下列哪个程序可以在用户态执行（  ）。

A、时钟中断处理程序

B、缺页中断处理程序

C、财务管理软件

D、进程调度程序

25、一个进程被唤醒表示（  ）。

A、该进程重新占有了CPU

B、它的优先权变为最大

C、进程变为就绪状态

D、其PCB移至等待队列队首

26、计算机系统如何访问外存上的数据（  ）。

A、先调入虚拟存储器中才能由CPU访问

B、CPU可直接访问

C、可以直接调入高速缓冲存储器中

D、必须在访问前先装入主存

27、对于两个并发进程，设互斥信号量为mutex，若mutex=0，则（  ）。

A、表示没有进程进入临界区

B、表示有一个进程进入等待状态

C、表示有一个进程进入临界区

D、表示有两个进程进入临界区

28、通道又称为I/O处理机，它用于实现（  ）之间的信息传输。

A、内存与外存

B、CPU与外存

C、内存与外设

D、CPU与外存

29、（  ）是指从作业提交给系统到作业完成的时间间隔。

A、运行时间

B、响应时间

C、等待时间

D、周转时间

30、通常，文件系统使用（  ）来解决不同用户文件的“命名冲突”问题。

A、索引

B、约定的方法

C、多级目录

D、路径

二、综合题（共90分）

31、（本小题共8分）假设用循环单链表表示的队列长度为n，分析只设头指针和只设尾指针两种情况下，出队操作和入队操作的时间复杂度。

32、（本小题共10分）给出一组关键字K={54，45，36，63，27，72}，写出用冒泡排序和选择排序方法排序时，第一趟结束时关键字的排列状态。

33、（本小题共10分）

（1）利用逐个数据插入的方法建立序列{51，31，61，11，41，16}对应的二叉排序树。（4分）

（2）在该树上查找31需要进行的比较次数为多少？（2分）

（3）该树查找成功的平均查找长度是多少？（2分）

（4）该树查找不成功的平均查找长度又是多少？（2分）

34、（本小题共12分）用普利姆(Prim)算法构造如下连通图G的一棵最小生成树，试画出其构造过程。

35、（本小题共6分）通常将操作系统分为实时系统和分时系统，二者有何异同？

36、（本小题共6分）什么是中断，（2分）简述缺页中断与一般中断的主要区别。（4分）

37、（本小题共6分）进程的基本状态有哪些？（3分）说明进程在基本状态之间如何转换，阐述每一种转换发生的主要原因。（3分）

38、（本小题共8分）在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面：1、4、3、1、2、5、1、4、2、1、4、5，若分给该作业的主存块数为3，请写出分析过程，回答下列问题：

（1）什么是请求分页存储管理方式，基本思想是什么？（2分）

（2）分别采用OPT（最佳）、FIFO（先进先出）、LRU（最近最少使用）页面置换算法，写出内存块的变化，并求各种方式下缺页中断的次数和缺页率。（6分）

39、（本小题共12分）设在批处理系统中有四道作业，它们进入系统的时间及运行时间如下表：

设系统每次只选择一个作业装入主机，分别给出在下列算法中这组作业的运行顺序、每个作业的等待时间、周转时间和带权周转时间，平均周转时间和平均带权周转时间。

（1）SJF算法（最短优先）；（6分）

（2）HRN算法（最高响应比优先）。（6分）

40、（本小题共12分）平常使用QQ，用户每次发送的信息都需要进行安全审查，只有通过安全审查的信息才能发送到对方用户。假定QQ用户程序、安全审查程序之间的工作方式是：QQ用户将信息发送到一个缓冲区，缓冲区最多可以存放100条信息，初始时缓冲区为空，安全审查程序有多个，工作时从缓冲区中读入信息。

当缓冲区未满时，QQ用户可以发送一条信息到缓冲区，否则等待；当缓冲区不空时，安全审查程序可以从缓冲区取出一条信息进行审查，否则等待。安全审查程序每次从缓冲区连续读出10条信息后，必须让给其他程序读出或写入数据信息。请用P、V（wait、signal）操作实现进程之间的互斥和同步，要求写出完整的过程，并指出所用信号量的含义和初值。

【24考研辅导课程推荐】24考研集训营、周末辅导班、一对一辅导，相关课程都配有内部讲义及书籍资料，同时还有辅导老师进行学习规划及全程督学，详情可直接在线咨询。