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

汕头大学2020年硕士研究生入学考试初试试题：830计算机基础综合

科目代码: 830

科目名称:计算机基础综合

适用专业:计算机软件与理论、计算机应用技术、电子信息

数据结构部分: 100 分

一、简答题(20题，每题2分，共40分)

1、程序-般主要分为哪几部分?

2、从逻辑层面有几类数据结构?如何判断?

3、数据的存储结构主要有哪些?

4、一般从几方面分析算法的效率?

5、栈和队列是何种数据结构?受什么限制?

6、请简述KMP算法为何有较高的效率。

7、稀疏矩阵如何选取节省空间的存储方案?

8、在数据结构中较多的研究了二叉树，一般树的问题是如何得到解决的?

9、 请简述线索 二叉树的目的。

10、请简述最小代价生成树的实际应用背景。

11、请简述静态查找与动态查找的区别。

12、请简述折半查找适合的关键字结构和存储结构。

13、基 于“比较”的查找，最好的平均时间复杂度为O (____ );基于“计算”的查找，时间复杂度是0 (____ )。

14、请简述 五类内部排序。

15、冒 泡排序对何种关键字结构效率较高?

16、堆排序选择何种存储结构?排序后是递增还是递减?

17、请 简述归并排序的空间开销。

18、请简述 算法的特性。

19、请 简述好算法的标准。

20、简述所知道 的数据的逻辑结构。

二、综合题(5题，每题6分，共30分)

1、请设计合理的多栈共享方案，说明存储方式，各栈的分配及操作方式。

2、请给出三对角N阶矩阵压缩存储的方案及计算公式。

3、图的邻接矩阵和十字链表的存储结构各自适合存什么图及做何种操作?

4、已知有长度为9的表: (33, 21, 18，25，28，23, 30，32，45)，请按表中数字顺序输入构建平衡二叉排序树，图示构造过程。(如有旋转请标明旋转类型)

5、请给出解决大型工程施工活动进度安排的解决方案。如需要提前工期时，如何寻找影响工期进度的主要活动。

三、算法题(3题，每题10分，共30分)

1、请设计在不带头结点的双循环静态链表上的插入算法。

2、请设计改进的快速排序算法以改变快排算法可能出现的最坏情况。

3、请设计完整的算法对输入的一篇英文文章可压缩字符的存储空间。

操作系统部分: 50 分

四、简答题(8小题，每题5分，共40分)

1、根据计算机系统软硬件层次结构，软件可分为哪三类?每类请给出一个实例。

2、按照功能、特点和使用方式，可把操作系统分为哪三种基本类型?常用的Windows系统和Linux系统可以分别归为哪种?

3、请写出如下英文缩写的中文含义: POSIX, API, MMU, LRU和DDL。

4、 请简述 内核级线程和用户 级线程的定义和缺点。

5、请列举5种进程间常用的同步或通信机制。

6、一个系统采用分页存储管理，并配有快表，请简述逻辑地址到物理地址的转换过程。

7、IO软件的总体设计目标是什么?为达到该目标，1/0 软件通常被组织成哪4层?

8、文件的属性，例如文件名，创建时间，读写权限等，是否和文件的内容存储在一起?如果是，请简述如何存储;如果不是，请简述存储在何处?在Linux系统中，为什么引入inode将文件名和其他属性分开存储?

五、解答题(10分)

一组生产者进程和一组消费者进程共享9个缓冲区，每个缓冲区可以放一个整数。生产者进程每次一次性地向三 个缓冲区写入整数，消费者进程每次从一个缓冲区取出整数。请用信号量( Semaphore)和PV操作写出能够正确执行的示意程序。