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

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

科目代码: 830

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

适用专业:计算机软件与理论、计算机应用技术、计算机技术(专业学位)

第一部分数据结构(100分)

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

1、简述数据结构之于程序的重要性。

2、通常都会在什么层面讨论数据结构?

3、栈、队列、树、图各属于什么结构。

4、数据的存储结构有哪些?

5、如何利用树得到高效的排序及查找?

6、对于稀疏图、稠密图如何选择存贮结构。

7、简述图的“关键路径”解决的问题。

8、简述静态查找和动态查找的区别。例举静态查找和动态查找的算法

9、排序的目的是什么?简述选择排序类的思想及属于选择排序类的最快算法。

10、简述构建哈希表的步骤。

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

1、需计算稀疏矩阵A+B并存于A中，请定义节省内存的存贮结构?

2、对于树如何选择如孩子表示法、双亲表示法、孩子兄弟表示法的存贮，能够是的操作效率更高?

3、给出用最小生成树解决50个城市合理部署高速轨道交通的方案，请详述。

4、给出设计不等长编码的合理方案，请详述。

5、指出冒泡排序、快速排序、堆排序和基数排序等算法的平均时间复杂度、平均空间复杂度及其稳定性?

三、写算法(共30分，每题10分) (注意加写设计思想及注释)

1、在不带头节点的双循环链表上插入和删除的算法;

2、已知树的存贮结构为孩子兄弟链表，写递归算法计算树的所有内部节点。

3、利用堆排序完成用克鲁斯卡尔(Kruskal) 算法求最小代价生成树。

第二部分操作系统(50分)

一、填空题(共15分，每空1分)

1、进程调度算法有很多，如: ，，。

2、文件的物理结构有三种类型:

3、临界区的同步准则应遵循下列准则:，，。

4、系统运行时，处理机的状态处于目态或管态之中，从 目态到管态的途径是:。系统处于态时不执行特权指令。

5、缺页中断率与几个方面有关，分别是:，和。

6、若进程在执行时间中时间片已用完，而计算还未完成，则进程也转为状态。

二、解答题(共20分)

1、 快表的作用是什么? 简述加进快表之后的地址转换过程。 (6分)

2、简述死锁产生的原因、预防和解除死锁的方法? (6分)

3. 读者写者问题: 有两组并发进程:读者和写者，共享一个文件F, 要求: 

(1)允许多个读者同时执行读操作; 

(2)只允许一个写者执行写操作;

(3) 任一写者在完成写操作前不允许其它读者或写者工作; 

(4) 写者执行写操作前，应让已有写者和读者全部退出。以下是采用信号量解决读者-写者问题的一 种实现: 

请完成下列题目:

(1)补充①和②处的代码。(2 分)

(2)信号量mutex的作用? (2 分)

(3)假设有个写者正在写文件，此时相继来了两个读者试图读文件，请问这两个读者将分别阻塞在何处? (2 分) .

(4)分析 该实现可能出现的写者饥饿现象。(2分)

三、论述题: (共15分)

1、从各种存储方法的存储思想与优缺点出发，试论述操作系统内存管理从初步的固定分区、可变分区、分页存储、分段存储等至虚拟存储方法的发展历程?(8分)

2、试叙述一个程序文件被调入运行到运行完成,所涉及到的操作系统全部可能功能管理环节及其过程。(7分)