哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　姜徵呼览火岑 2016年招收硕士研究生考题 科目名称： 计算机理论基础 科目代码: 896 考生请注意：答案必须写在答题纸上,写在本考题纸上的无效! 第一部分 搡作系统（第1-11小题，共70分） 一、 简答题（第1-5小题，每小题4分，共20分） 1、 简述处理机管理的主 功能和它们的主 任务。 2、 简 说明用户程序如何执行操作系统调用，以及操作系统在执行系统调用时的工作过程。 3、 什么是作业和作业步？ 4、 以打印机为例简要说明SPOOLing的工作原理。 5、 简述死锁发生的必 条件。 二、 计算题（第6-9小题，第6小题6分，第7-9每小题8分，共30分） 6、 设有三个进程A，B, C,进程A和进程B各需要运行6亳秒的处理器时间，而进程C却 24毫秒的处理器时间，分别考虑当三个进程到达顺序为A, B, C时及C，B, A时，用先来先服 务算法进行调度时计算各自的平均等待时间。 7、 在一个请求页式存储管理中，一个进程的页面走向为4、3^ 2、1、4、3、5、4、3^ 2、1、5, 设分配给该进程的存储块数M为4。若釆用最近最久未使用LRU置换算法，请计算在该访问中 发生的缺页次数F。 8、 假定磁盘的移动臂现在正处在筹8柱面，有如下6个请求者等待访问磁盘，请你列出最省时间 的响应次序并给出合适的理由。 序号 柱面号 磁头号 扇区号 (1) 9 6 3 (2) 7 5 6 (3) 15 20 6 (4) 9 4 4 (5) 20 9 5 (6) 7 15 2 安徽师范大学招收硕士学位研宄生考试考题纸 第丄页，共3页 考生请注意：答案必须写在答题纸上，写在本考题纸上的无效! 9、请用最高响应比优先调度算法完成下表: 作业 提交时刻 (时) 运行时间(小时) 开始时刻 完成时刻 周转时间 1 8： 00 2. 0 8： 00 2 8： 50 0. 5 3 9： 00 0. 1 4 9： 50 0. 2 三、综合题(第10-11小题，每小题10分，共20分) 10、有一个具有两道作业的批处理系统(最多可有两道作业同时装入内存执行)，作业调度采用计 算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业 序列，作业优先数即为递程优先数，优先数越小优先级越高： 作业名 到达时间 估计运行时间 优先数 A 9 :00 40分钟 5 B 9 :20 30分钟 3 C 9 :30 50分钟 4 D 9 :50 20分钟 6 (1) 列出所有作业进入内存时间及结束时间。 (2) 计算平均周转时间。 11、某B超室提供1个超声波设备和10个患者等待座位。患者到达时，若有空座位，则到取号 机领取一个号，等待叫号。取号机每次仅允许一位患者使用。当设备空闲时，医生通过叫号选取 一位患者。患者和医生的活动过程描述如下： cobegin { process 患者i {从取号机获得一个号码； 等待叫号； 获得服务; process 医生 {while (TRUE) {叫号； 为患者做B超;}■ } } coend 请添加必 的信号量和P、V (或wait ()、signal ())操作实现上述过程的互斥和同步。 求写出 完整的过程，说明信号量的含义并赋初值。 安徽师范大学招收硕士学位研究生考试考题纸 第丄页，共3页 考生请注意：答案必须写在答题纸上，写在本考题纸上的无效! 第二部分 数据结构(第12-24小题，共80分) 一、简答题(第12-16小题，每小题4分，共20分) 12、 简述下列术语：数据，数据元素、数据结构、存储结构。 13、 简述线性表的两种存储结构各有哪些优缺点？ 14、简述队列和堆栈这两种数据类型的相同点和差异处。 15、给出数据结构中树的定义。 16、 简述数据结构中平衡二叉树的性质 二、计算题(第17“21小题，每小题6分，共30分) 17、 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。己知A的基地 址为2000,计算： (1) 数组A共占用多少字节； (2) 数组A的最后一个元素的地址； (3) 定义数组的下标从1开始，按行存储时，元素A [3] [6]的地址； 18、 两侧铁道均为单向行驶道，进行车厢调度， (1) 如果进站的车厢序列为123,给出所有可能的出站车厢序列 (2) 判断如进站的车厢序列为123456,能否得到345612出站序列，说明原因。 19、 假定一个待哈希存储的线,-若采用 除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和 最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 20、 己知一棵二叉树的前序遍历的结果为：ABCDEF,中序遍历的结果为：BCAEDF 请给出二叉树的后序序列。 求：(1)画出这棵二叉树； (2)写出这棵二叉树的后序遍历序列。 21、 对给定的一组权值W= (5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带 权路径长度。 三、设计题(第22-24小题，每小题10分，共30分) 22、 若矩阵Araxn 中的某个元素afj是第i行中的最小值，同时又是第j列中的最大值，则称此元素 为该矩阵中的一个鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有鞍点。 23、 一个仅由小写字母和数字两类字符构成的单链表， 求设计算法利用原单链表中结点空间 生成两个单链表，使每个单链表只包含同类字符。 24、 一个以链式结构存储的二叉树，设计算法交换其所有结点左右子树。 安徽师范大学招收硕士学位研究生考试考题纸 第丄页，共3页 考生请注意：答案必须写在答题纸上,写在本考题纸上的无效! 姜徵4？ 年硕士研究生招生考试初试试题 科目代码：896 科目名称：计算机理论基础 第一部分 数据结构(80分) 简答题(共24分，每小题6分) 1. 在顺序存储和链式存储中，数据元素之间的逻辑关系分别是如何表示的？并比较这两 种存储结构的优缺点。 2. 什么是循环队列？并给出其队空、队满的条件。 3. 什么是串相等？并列出串的常见存储方式。 4. 简述树和二叉树的区别。 二、 应用题(共36分，第1、4小题各8分，第2、3小题各10分) 1. 设一数列的输入顺序为123456,若采用栈结构，并以A和D分别表示入栈和出栈操 作，试问通过入、出栈操作的合法序列，能否得到： (1) 输出顺序为325641的序列; (2) 输出顺序为154623的序列。 若能得到，请给出入、出栈操作的序列，若不能，请说明原因。 2. 设给定一个权值集合W= (3, 5, 4, 9, 6, 12, 17), 求根据给定的权值集合构造 一棵哈夫壘树，并计算其带权路径长度和每个叶子结点的哈夫曼编码。 求：左孩子的 权值不大于右孩子的权值。 3. 已知有一个含 7 个顶点(vl, v2, v3, v4, v5, v6, v7) 0 1 1 1 0 0 0 的有向图，其邻接矩阵如右表所示。请回答如下问题： 0 0 ] 0 0 1 0 0 0 0 1 1 1 0 (1) 画出该有向图的邻接表； 0 0 0 0 1 0 0 (2) 写出从vl出发的深度优先遍历序列和广度优先遍历 0 0 0 0 0 1 1 序列。 0 0 0 0 0 0 1 4. 己知待排序的关键字序列(12, 2, 16, 30, 28, 10, 16*， 0 0 0 0 0 0 0 20, 6, 18)，完成下列排序 ( 求排序结果非递减有序)。 (1) 给出进行一趟希尔排序 (增量序列为5)的排序结果； (2) 给出以第一个元素为枢轴的一趟快速排序的排序结果。 三、 算法设计题(共20分，每小题10分) 1.设计一个高效算法，将顺序表中的所有元素逆置， 求算法的时间复杂度为O (n)。 考生请注意:答案必须写在答题纸上，写在本试题纸上的无效! 第 i页，共 1页 安徽师范大学2017年硕士研究生招生考试初试试题 2.假设某二叉树采用二叉链表存储结构，试设计递归算法，求该二叉树的高度。 第二部分 操作系统（70分） 一、 名词解释（共15分，每小题3分r 1. 多道程序设计 2. 饥饿 3. 地址重定位 4. 临界区 \ 5. 文件的物理结构 二、 简答题（共30分，每小题6分 ）• 1. 说明操作系统四个基本特征的含义。 2. 进程和程序的主 区别有哪些？ 3. 按序分配资源是预防死锁的、 一种策略。什么是按序分配？为什么可以预防死锁？ 4. 用实例说明Spooling技术的工作原理。 5. 简述在操作系统的设备管理中引入缓冲的好处。 三、 应用题（共25分，第1小题7分，第2小题8分，第3小题10分） 1. 有10台打印机，三个进程Pl，P2, P3分别需 7台、8台和3台，若Pl, P2, P3 己申请到3台，3台和2台。现在这三个进程又分别申请1台、2台、1台，请问： （1） 能否先满足进程P2的 求？为什么？ （2） 如何为这三个进程分配打印机才比较合适？ 2. 若干个等待访问磁盘者依次耍访问的磁道为20, 44, 40, 4, 80, 12, 76,假设每移 动一个磁道需 3毫秒时间，移动臂当前位于40号磁道，请按下列算法分别计算为完 成上述各次访问总共花费的寻道时间，并给出磁道访问次序和每次移动的磁道数。 （1） 先来先服务算法； （2） 最短寻道时间优先算法。 f 3. 有一个仓库，可以存放两类产品：x和么 求： （1） 每次只能存入其中的一种产品（x或y）; （2） 4 ＜产品x数量-产品y数量＜a。 试用PV操作描述两类产品的入库过程。 考生请注意:答案必须写在答题纸上，写在本试题纸上的无效! 第2页，共2页 2018年硕士研究生招生考试初试试题 科目代码：896 科目名称： 计算机理论基础 第一部分数据结掏（80分） 一、 简答题（每小题4分，共20分） 1. 在数据结构中，数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 2. 简述线性表、栈和队列的异同。 3. 简述二叉树的定义。 4. 简述拓扑排序的过程。 5. 简述快速排序的基本思想。 二、 应用题（每小题8分，共40分） 1. 设n为3的倍数，分析以下算法的时间复杂度 （ 求必须给出推导过程）。 void fun（int n） { int i j,x，y ; fbr（ i=l ;i=n ;i+1-） for（j=3*i ;j=n ;j++） {x-H- ; y=3*x+2 ;} } 2. 对如下图所示的带权有向图： 求：（1）每个顶点的入度和出度；（2）给出其邻接矩阵；（3）给出其邻接表。 考生请注意:答案必须写在答题纸上，写在本试题纸上的无效! 第1页，共 i页 安徽师范大学2018年硕士研究生招生考试初试试题 3. 如果一棵哈夫曼树T有nG个叶子结点，那么树T有多少个结点？（ 求给出求解过程） 4. 设有关键字序列（2, 4, 6, 9, 14, 16, 13, 7｝。设哈希表的长度为8 （地址为0...7）， 哈希函数采用除留余数法，用线性探测法解决冲突。试设计哈希函数和哈希表，并给出 查找成功的平均查找长度。 5. 判断关键字序列｛12, 7, 18, 13, 17, 29, 34, 6, 8｝是否为堆？若不是，请将其调整 为堆 （小根堆），给出建堆过程，并统计建堆过程中的交换次数。 三、算法设计题（每小题10分，共20分） 1. 设计一个算法，删除顺序表L中所有值为x的数据元素， 求时间和空间两方面都尽 可能高效（ 求给出顺序表的类型定义）。 2. 假设一棵二叉树采用二叉链表存储结构，设计一个递归算法计算该二叉树的结点数 （ 求给出二叉链表的类型定义）。 第二部分搡作系统（70分） 一、 简答题（每小题6分，共30分） 1. 什么是多道程序设计？它的主 特点是什么？ 2. 分页和分段存储管理有何区别？ 3. 什么是重定位？有哪几种实现方式？如何实现？ 4. 为什么 引入SPOOLing系统？ SPOOLing系统能带来哪些好处？ 5. 什么是文件的访‘向控制？试列举出三种实现文件访问控制的方法？ 二、 应用题（每小题10分，共40分） 1.考虑系统瞬时状态为： 进程 A llocation Max P0 0012 0012 P 1 1000 1750 P2 1354 2356 P3 0632 0652 P4 0014 0656 Available1520，利用银行家算法回答下列问题： （1） 计算数组need。 （2） 该系统处于安全状态吗？ （3） 若进程P 1提出请求（0420）,能否立即满足？ Z某请求分页存储管理系统中，设页面走向为：1,2,3,1，2,3,2,1，2,5,4,2,5，主存容量为3 页。试求：分别采用LRU （最近最久未使用）、FIFO（先进先出）、Optimal（最优）3种页面 置换算法时的缺页次数。 考生请注意:答案必须写在答题纸上，写在本试题纸上的无效! 第1页，共 i页 安徽师范大学2018年硕士研究生招生考试初试试题 3. 当进程X和进程Y共享某个资源r，进程并发执行时的程序如下： begin Sisemaphore :=1 cobegin Process X begin LI : P (S) ; 使用资源r ; V (S) ; Goto LI ; end ; Process Y begin L2 : P (S) ; 使用资源r ; V (S) ; Goto L2 ; end ; eoend ;-- end ; 请回答： (1) 两个进程并发执行时，能否保证互斥使用资源？为什么？ (2) 如果 使两个进程交替使用资源，若仍使用P,V操作进行管理，写出应定 义的信号量及其初值。 (3) 修改上述程序，使两个进程能交替使用资源r。 4. 在Unix操作系统中，i节点定义了 13个指针，用来存放13个物理块号，把文件分成 小型、中型、大型和巨型四种，分别采用直接、一次间接、二次间接、三次间接索引方 法。试问： (1) 这种结构有何优缺点？ (2) 若每块大小为1KB ，每个块号占4B ，问每类文件可能的大小范围是多少？ 考生请注意:答案必须写在答题缴上，写在本试题纸上的无效! 第.1_页，共 i页 姜徵岬龙头岑 2019年硕士研究生招生考试初试试题 科目代码：896 科目名称： 计算机理论基础 第一部分数据结构（80分） 一、 简答题（每小题4分，共20分） 1. 根据数据元素之间关系的不同特性，可将逻辑结构分为哪几种？并简述各结构的特性。 2. 试比较顺序表和链表的优缺点。 3. 简述队列的“假溢出”现象。 4. 度为2的树是二叉树，此说法是否正确？请给出理由。 5. 有n个顶点的有向强连通图中最多有多少条边？最少有多少条边？ 二、 应用题（每小题8分，共40分） 1. 以数据集｛4, 5, 6, 7, 10, 12, 18｝为结点权值，画出构造Huffman树的