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

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

科目代码: 830

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

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

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

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

1、数据结构中逻辑结构和存储结构的关系是什么?

2、设计一个“好”的算法应考虑达到哪些目标?

3、顺序表和链表分别适用于什么场合?

4、队列、栈和线性表的区别与联系是什么?

5、顺序队列“假上溢”产生的原因是什么?解决办法有哪些?

6、树有哪几种表示法?树的存储结构有哪几种?

7、-棵有 n个结点的满二叉树有多少个度为1的结点?有多少个分支(非终端)结点和叶子结点?该满二叉树的高度为多少?

8、哈希表处理冲突的方法有哪些?请列举其中4种。

9、二叉树的遍历方法有哪些?

10、什么是关键路径?举例说明它的实际应用。

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

1、假设A_nxn为稀疏矩阵，请从时间和空间角度比较采用二维数组和三元组完成求对角线元素之和,运算的优缺点。

2、简述二叉树、二叉排序树和平衡二叉树的关系，并判断一棵完全二叉树是否一定是一 棵平衡二叉树。

3、简述“拓扑排序”解决问题的方法，并例举实际问题说明。

4、已知字符A,B,C,D,E,F,G在报文中出现的次数分别是3,127,.,2,8,11， 请画出相应的Huffian树并给出一个Huffman编码方案。

5、评述快速排序和堆排序算法的原理，并讨论其时间复杂度。

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

1、已知有一 个单链表L,其中可能出现值域重复的结点，请设计一个算法删除值域重复的结点，并分析算法的时间复杂度。要求: (1) 描述算法基本设计思想; (2) 采用程序设计语言(C、 C++或Java)描述算法并给出关键注释。

2、假设一 颗非空树t采用孩子链存储结构，每个结点值均为单个字符。设计递归算法求树t中度为k的结点个数。要求: 

(1)描述算法基本设计思想: 

(2)采用程序设计语言(C、 C++或Java)描述算法并给出关键注释。

3、设G是一个无权有向无环图，试采用合适的存储结构设计一个算法，求图G中从源点S出发到图中其它所有顶点的最长距离。要求: 

(1) 描述算法基本设计思想; 

(2) 采用程序设计语言(C、C++或Java)描述算法并给出关键注释。

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

四、简答题(共36分，每题6分)

1、简述分时系统中的时间片轮转，以及分时系统的四个特点:同时性，独立性，及时性和交互性。

2、简述进程三状态模型中的三种状态，并列出它们之间可能的转换关系。

3、简述死锁和死锁产生的原因。简述进程资源图中出现环路与死锁的关系。

4、简述页面替换中的抖动现象。写出 FIFO和LRU页面替换算法的中文名字。简述最佳页面替换算法(OPT)的思想。

5、简述系统调用与一般过程调用的区别。

6、文件目录所对应的文件中存储的是什么内容?与文件目录有关的“.”和."分别表示什么?

五、解答题(14分)

假设有5位哲学家，他们的生活只是思考和吃饭。这些哲学家共用一个圆桌，每位都有一“把椅子， 在桌子中央有一碗米饭，相邻的两哲学家之间放有1根筷子，如图所示。当哲学家想要吃饭时，他只有拿到与他相近的两根筷子才能吃饭。如下为试图采用信号量和P、v操作解决同步问题的示意代码。请回答下列问题。

1、上述方法存在什么问题? (2分)

2、请给出两种解决上述问题的方案，要求简述方案并重写示意代码。(10 分)

3、用信号量表示某种资源，信号量当前的值为正数和负数分别表示什么含义?(2分)