资源描述
汕头大学2021年攻读硕士学位研究生入学考试试题考生须知答案一律写在答题纸上，答在 试题纸上的不得分！请用黑色字迹 签字笔作答，答题要写清题号，不 必抄原题。科目代码：830科目名称：计算机基础综合适用专业：计算机软件与理论、计算机应用技术、电子信息第一部分数据结构（100分）一、简答题（共40分，每题4分）1、数据结构中逻辑结构和存储结构的关系是什么？2、设计一个“好”的算法应考虑达到哪些目标？3、顺序表和链表分别适用于什么场合？4、队列、栈和线性表的区别与联系是什么？5、顺序队列“假上溢”产生的原因是什么？解决办法有哪些？6、树有哪几种表示法？树的存储结构有哪几种？7、一棵有个结点的满二叉树有多少个度为1的结点?有多少个分支（非终端）结点和叶子结点?该满二叉树的高度为多少？8、哈希表处理冲突的方法有哪些？请列举其中4种。9、二叉树的遍历方法有哪些？10、什么是关键路径？举例说明它的实际应用。二、综合题（共30分，每题6分）1、假设4的为稀疏矩阵，请从时间和空间角度比较釆用二维数组和三元组完成 求对角线元素之和f%运算的优缺点。/=02、简述二叉树、二叉排序树和平衡二叉树的关系，并判断一棵完全二叉树是否一定是一棵平衡二叉树。3、简述“拓扑排序”解决问题的方法，并例举实际问题说明。4、已知字符A,B,C,D,E,F,G在报文中出现的次数分别是3,12,7,4,2,8,11,请画出 相应的Huffman树并给出一个Huffman编码方案。5、评述快速排序和堆排序算法的原理，并讨论其时间复杂度。三、算法设计（共30分，每题10分）1、己知有一个单链表L,其中可能出现值域重复的结点，请设计一个算法删除 值域重复的结点，并分析算法的时间复杂度。要求：（1）描述算法基本设计思 想；（2）采用程序设计语言（C、C+或Java）描述算法并给出关键注释。2、假设一颗非空树t釆用孩子链存储结构，每个结点值均为单个字符。设计递 归算法求树t中度为*的结点个数。要求：（1）描述算法基本设计思想；（2）釆 用程序设计语言（C、C+或Java）描述算法并给出关键注释。3、设G是一个无权有向无环图，试釆用合适的存储结构设计-一个算法，求图G 中从源点S出发到图中其它所有顶点的最长距离。要求：（1）描述算法基本设 计思想；（2）采用程序设计语言（C、C+或Java）描述算法并给出关键注释。第二部分操作系统（50分）四、简答题（共36分，每题6分）1、简述分时系统中的时间片轮转，以及分时系统的四个特点：同时性，独立性, 及时性和交互性。2、简述进程三状态模型中的三种状态，并列出它们之间可能的转换关系。3、简述死锁和死锁产生的原因。简述进程资源图中出现环路与死锁的关系。cC第3页共4页汕头大学2021年攻读硕士学位研究生入学考试试题*! 4、简述页面替换中的抖动现象。写出FIFO和LRU页面替换算法的中文名字。 简述最佳页面替换算員(OPT)的思想。5、简述系统调用与一般过程调用的区别。6、文件目录所对应的文件中存储的是什么内容？与文件目录有关的“.”和分* 别表示什么？一五、解答题(14分)假设有5位哲学家，他们的生活只是思考和吃饭。这些哲学家共用一个圆桌，每位都有一把椅子，在桌子中央有一碗米饭，相邻的两哲学家之间放有1根筷 子，如图所示。当哲学家想要吃饭时，他只有拿到与他相近的两根筷子才能吃 饭。如下为试图釆用信号量和P、V操作解决同步问题的示意代码。请回答下列 问题。门semaphore chopstick5 = 1,1,1,1,1;cobeginphilosopher(i) do P(chopsticki);/拿左边的筷子第5页共4页汕头大学2021年攻读硕士学位研究生入学考试试题P(chopstick(i+1)%5); 拿右边的筷子eat();V(chopstick(i+1) % 5);V(chopsticki);think(); while (true);coend1、上述方法存在什么问题？(2分)2、请给出两种解决上述问题的方案，要求简述方案并重写示意代码。(10分)3、用信号量表示某种资源，信号量当前的值为正数和负数分别表示什么含义?(2分)第6页共4页
展开阅读全文