安徽师范大学2020年硕士研究生招生考试自命题试卷真题896计算机理论基础.docx
荽黴岬格大象通J年硕士研究生招生考试初试试题科目代码:896科目名称: 计算机理论基础第一部分数据结构(80分)一、简答题(每小题4分,共20分)1. 简述数据结构的逻辑结构与存储结构的含义及其相互关系。2. 线性表有两种存储结构,在什么情况下选用顺序表比链表更好。3. 栈底元素是不能删除的元素,此说法是否正确?请给出理由。4. 任意一个具有n个结点的二叉树,已知它有m个叶子结点,试证明它有n-2m+l个度数为1的结点。5. 具有n个顶点的有向完全图中有多少条边?二、应用题(每小题8分,共40分)1. 给出下列算法被调用后得到的输出结果。char x=e; initqueue(q): 初始化队列qchar y=c;enqueue (q, 将关键字序列13, 5, 20,19,15, 8散列存储到一个散列表中,该散列表的地址范围为0-7,散列函 数为:H(key)=key MOD7,釆用线性探测再散列法处理冲突。请构造该散列表,并给出每个关键字 的探测次数。h设待排序的关键字序列为15, 5,16, 2, 25, 8, 20, 9,18,12),试给岀釆用快速排序算法对该序列进行 升序排序时的每一趟排序结果。) ; enqueue (q,; enqueue (q, y); dequeue (q, x);enqueue (q, x) ; dequeue (q, x); enqueue (q,,a);whi le (! queue empty (q) dequeue (q, y); printf (y) : printf (x);注意:enqueue(q, h)是将h入队,dequeue(q, x)是出队,并将出队元素赋给x, queueempty(q) 用于判断队列是否为空,为空时,其值为真。2. 设一棵二叉树的先序序列为ABDEGCF,中序序列为DBGEACF。请画出这棵二叉树,并给出其后序序 列。3. 请釆用Prim算法为下图构造最小生成树,并给出构造过程。三、算法设计题(每小题10分,共20分)1-设计一个算法,用头插法创建包含n个数据元素的带头结点的单链表Lo2. 假设二叉树采用二叉链表存储结构存储,设计算法输出其先序遍历序列中第k个结点的值,假设 k不大于二叉树的总结点数(结点数据域类型为字符型)。第二部分操作系统(70分)一、简答题(每小题5分,共30分)1. 什么是操作系统?2. 说明进程的三种基本状态。3. 产生死锁的四个必要条件是什么?4. 某分页系统的逻辑地址为16位,其中高6位为页号,低10位为页内偏移量,则每页的字节数是 多少?最多可有多少页?5. 按资源分配方式可将外部设备分为哪几类?6. 分析文件的外存分配中连续分配方式的优缺点。二、应用题(每小题10分,共40分)1. 现有某类资源12个,供3个进程共享。假定进程A已占1个资源,其最大需求4个,进程B已占 4个资源,其最大需求6个,进程C已占5个资源,其最大需求8个。当3个进程同时请求尚需的 资源时,系统应按怎样的次序为它们分配资源以保证不发生死锁,并解释之。2. 在釆用请求分页存储管理的计算机系统中,运行一个共有8页的作业,且该作业在主存中分配到 4块主存空间,作业执行时访问页面顺序为7, 0, 1, 2, 3, 0, 4, 3, 2, 3, 6, 7, 3, 1, 5, 7, 6,2, 6, 7O请问用LRU页面调度算法时的缺页率是多少?并给出分析过程。99501#S.free0123. 在UNIX文件系统中,盘块的分配与释放是借助于成组链接法中的空闲盘块栈进行的。假定某时刻 空闲盘块栈如右图所示,此时要为某文件分配3个盘块。请说明分配过程,并图示分配完毕后有关 数据及表目的更改情况。4.某博物馆最多可容纳500人同时参观,只有一个出入口,该出入口一次仅允许一个人通过。当博 物馆内少于500人时,参观者可进入,否则需在入口外等待。若把一个参观者看作一个进程,用P、 V操作管理这些并发进程时,请回答如下问题:(1)定义信号量,写出信号量的初值及其含义。(2) 插入应执行的P、V操作一以保证进程能够正确地并发执行。cobegin参观者进程i:进门; 参观; 出门;coend考生请注意:答案必须写在答题纸上,写在本试题纸上的无效!第1页,共2页