山东大学851计算机基础综合历年考研真题汇编.docx

《山东大学851计算机基础综合历年考研真题汇编.docx》由会员分享，可在线阅读，更多相关《山东大学851计算机基础综合历年考研真题汇编.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录2014年山东大学851计算机基础综合考研真题2015年山东大学851计算机基础综合考研真题2016年山东大学851计算机基础综合考研真题2017年山东大学851计算机基础综合考研真题 2018年山东大学851计算机基础综合考研真题五、分析设计题（共2题，每题10分，共20分）1、某8位微型机地址码为18位,控制信号为R/万（读/写），MREQ （存储器访问信号）用2K x 8的ROM芯片（片选信号为外）形成16K x 8的ROM模块板, 使用4KX4位的RAM芯片组成32Kx8位RAM模块板，现在系统配置为ROM模块板 1个，起始地址为00000H； RAM模块板4个,占用连续高端地址空

2、间，问：（1）共有多少片RAM?多少片ROM?（2）求每块ROM板和最后一块RAM板的地址范用（16进制表示）.（3）画出连线根图，其它器件自选。RAM模块板不需要画出板内结构。2、设单总线结构主机框图如下，ALU可以完成加、减等运算功能，存储器按字 编址。写出单字转子指令CALL AD （AD为转移地址）和返回指令RET的执行时的指 令流程（从取指令开始）.Z2016年山东大学851计算机基础综合考研真题山东大学二。一六年招收攻读硕士学位研究生入学考试试题科目代码 851科目名称计算机基础综合（请将所有试题答案写在答题纸上，写在试题上无效）一、填空题（共5题，每空1分，共10分）1、设16位

3、浮点数格式为：1位数符、10位尾数、1位阶符、4位阶码（尾数在前、 阶码在后）;阶码为移码,尾数为补码,那么浮点数53/128对应的规格化的机器数 表示为（用十六进制表示）02、无条件转移指令属/类指令，地址码表示的是 43、是指CPU回应各中断源请求的优先顺序， 是指CPU 实际对各中断源请求处理的优先顺序，可以通过修改 来改变。4、寄存器A中的值为A7H （补码表示），那么对A进行两次算术行移后A中的值是3、碳盘存储器主要技术指标有存储密度、二、名词解析（共4题，每题2. 5分，共10分）1、线程（Thread）2、保护域（Protection Domain）3、设备驱动程序（Device

4、 driver）h 虚拟地址（Vitrual Adress）三、简答题（共”题，共90分）1、（5分）什么是总线？系统总线上传送的信息通常分为哪儿类？2.（5分）在某机器中浮点数包括1位阶码符号、2位阶码数值位、1位尾数符号位、4位尾数数值位。：两浮点数x =0.1101X210, y =0.1011X201, 求：x + y3、（5分）中断方式和DMA方式有何异同点？各应用于哪些场合？4、（5分）试比拟组合逻辑控制方式和微程序控制方式的优缺点。5、（10分）描述外存空间分配的三种不同方法，并分析比拟各自的优缺点。6、（10分）进程有哪些基本状态？画出进程状态转换图,同时给出转换的原因，当 系

5、统中出现死锁时，用户进程可能处于什么状态？说明一个进程处死锁状态和 处了阻塞状态之间的区别7、（10分）什么是顺簸？颠簸产生的原因是什么?列举出可以处理颇簸问题的两种 方式，并说明其工作原理。8、（10分）设有一个可以装A、B两种物品的仓库,其容景无限大,但要求仓库中A、 B两种物品的数量满足下述不等式:-M WA物品数量一B物品数量WN,其中M和 N为正整数。请用信号量模拟A、B两种物品的入库过程，写出伪代码,并说明每 个信号量的作用。9、（10分）完全一叉树的第7层有6个叶f结点，那么整个一义树的站点数最多是多少？10、（10分）某加权连通无向图边的个数远远小于顶点的个数，假设求其最小 生

6、成树用哪种算法最好？简述该算法的基本思想.下而是某图的邻接矩阵。使用在（】）中选择的算法构造该图的最小生成树，给出其构造过程。012oo50000120X8108X80X0035XX06XaO100C60IIXX3X11011、（10分）表达式由数字、力口、减、乘、除和括号组成，如何计算表达式的运算 结果？四、算法题（共2题，每题10分，共20分）I、某一叉树中每个节点的值都大于或等于其子节点（如果有的话）的值。二叉树使用 一叉盖表方式存储，根节点指针为rool ,左右/节点指针分别为left和righi。 请设计算法，找到该二义树中最小值的节点，分析算法攵杂性。2、采用邻接表存储结构，编写个

7、判别无向图中任意给定的两个顶点之间是否存在 ,条长度为k的简单路径的算法。（注：条路径为简单路径指的是其顶点序列中 不含有重现的顶点。）五 分析设计题（共2题，每题10分，共20分）I、地址总线A15A0,数据总线1）7D0,读/写线励，片选低电平有效。存储器 地址空间为4000H6FFFH,按字节编址。其中4000H5FFFH为ROM区，选用EPROM 芯片（4KX8位/片）;6000H6FFFH为RAM区,选用SRAM芯片（2KX4位/片）。根据存储器容量，EPROM芯片和SRAM芯片各需多少片?（2）各芯片应分别连入哪儿根地址线？（3）写出每个片选信号的逻辑表达式。（4）画出存储器框图，

8、图中应包括存储芯片，片选逻辑电路，以及地址线、数据线、 片选线和读/写线的连接，2、假设某CPL采用微程序控制器设计。请从取指开始，按序写出完成一条加法指令 ADD （为主存地址，该加法指令实现ACC寄。器内容加上该内存地址的数 据，结果保存到ACC寄存器）的微操作命令及节拍安排。（提示：需要从控制存储 器读取微指令）2017年山东大学851计算机基础综合考研真题山东大学二。一七年招收攻读硕士学位研究生入学考试试题科目代码 851科目名称 计算机基础综合(请将所有试题答案写在答题纸上，写在试题上无效)一、填空题(共7题，每空1分，共1()分)1、计算机最主要的三大性能指标是、82、设变址寄存器

9、为X,形式地址为A,那么先间址再变址寻址的有效地址为: 3、院补4X1X2X3X4,假设要XW-8成立,X1X2X3X4应满足的条件是:I、设16位浮点数格式为：I位数符、1()位尾数、】位阶符、1位阶码(尾数在前、 阶码在后)；阶码、尾数为补码，那么A987II的真值为(十进制)05、计算机中，非法指令属于 产生的中断。6、将一个8位一进制数X中的最高位酒0,其它位保持不变，其方法是.7、RISC指令系统的最大特点是少、冏定。二、名词解析(共4题，每题2.5分，共10分)1、临界区(Critical Scclion)2、死锁(Deadlock)3、筋簸(Thrashing)4、口陷(Trap

10、)三、简答题(共11题，共90分)1（5分）、上在用来存储程序和数据，CPU如何区分从内存中读取出的内容是程序还 是数据？2 （5分）、假设定点小数具有1位符号位、4位数据位。11 r_2： 16-16求：LA+B补并判断足否溢出。3 （5分）、什么是禁止中断？它是怎样实现的？4 （5分）、计算定点原码一位乘法XXYJ原=?其中X=（M01LY=-0.1010,写出计 算步躲.5（10分）、操作系统中和程序执行有关的调度有作业调度、内存调度和进程调度。 请说明这三者的联系与区别。这三种调度程序中执行频率最高和最低的各是哪 个？6 （10分）、一个理发师有n张椅子,当顾客到来时，如有空椅子，就坐

11、在椅子上, 否那么站着等待.当有顾客时，理发师就理发，否那么他就睡觉。当顾客到来时，如 果理发师正在睡觉，就唤醒他.理发师给顾客理完发后打发顾客走入，空相椅子, 如行站着的顾客,就让其坐Ko试用p、v操作描述理发师和顾客之间的同步关系。7 （10分）、设右泗个进程，它们到达就绪队列的时间及执行时间如下表，假设采用剥 夺式短作业优先，非剥夺式短作业优先及时间片轮转法（时间片=2）,分别给出各进 程的关广各算法的调度次序及平均等待时间。进程到达时间执行时间pl06P215.5P323p434.58（10分）、某进程有F面的页面引用序列：7,0,1,2,030,4,23032.假定系统分配 给该进程

12、3个页框，并且开始时这三个页框都是空的。该系统采用LRU页而置换 算法，请给出缺页次数（给出求解步骤）。9 （8分）、什么是间接寻址？利用它来存储线性表与链式存储相比有何优缺点？ 10 （12分）、己知一个无向图的邻接表如下图，要求：012345画出此无向图；根据邻接表分别写出用深度优先遍历和广度优先遍历从顶点a开始遍历该图所 得到的序列;画出从顶点a出发的深度优先生成树和广度优先生成树；假设以顶点a为根求得高度最小和高度最大的生成树，各应采用什么方法？11（10分）、有n个杂乱无常的正整数，请设计尽可能快的算法，从中找到第n/2 大的整数。表达思想，并说明算法复杂性。四、算法题（共2题，每题

13、10分，共20分）1、二叉树采用二叉链表存储结构，设计算法，判断一.叉树是否为AVL树。表达算法 思想并给出算法实现。2、设有n个村庄之间的铁路交通图，假设村庄I和J之间有道路那么有边相连，权为道 路长度。现要在n个村庄中选一处建医院，试编写算法确定医院应建在那个村庄 才能使离医院最远的村庄到医院的距离最近。给出算法使用数据的数据结构描述。五、分析设计题（共2题，每题10分，共20分）1、某计算机用2K x 8的ROM芯片（片选信号为口）形成2K x 8的ROM区域， 起始地址为0000H；用8K x8的RAM芯片（片选信号为读写信号为阮）形 成16Kx 8的RAM区域，起始地址为6000H。

14、CPU地址总线为A15-A0,数据总线 为dado,控制信号为R/7（读/写），“REQ （存储器访问信号）。画出连线框 图，其它器件自选。2、设单总线结构上机框图如下，ALU可以完成加、减等运算功能，存储器按字编 址。指令格式为：JMPC AD；其中C为运算器产生的进位，当时程序转移：该指令为两字指令，转移地址 AD在第二个字中。写出该指令执行的指令流程（从取指令开始）.Z2014年山东大学851计算机基础综合考研真题2018年山东大学851计算机基础综合考研真题山东大学二0一八年招收攻读硕士学位研究生入学考试试题科目代码 851科目名称 计算机基础综合（答案必须写在答题纸上，写在试题上无效

15、）数据结构一、简答题（共3题，共26分）1. （8分）如果只想在一个有n个元素的任意序列中得到其中由最小的k（k（=n）个元 素组成的局部排序序列，那么最好采用什么排序方法？为什么？例如有这样一个序列 57,40,38,11,13,34,48,75,6,19,9,7,要得到其中由最小的4个元素组成的局部有序 序列（6,7,9,11）,用所选择的算法实现排序过程，描述排序过程，并说明要进行多少次 比拟。2. （8分）一个归并段是一组元素的有序序列,假设两个归并段合并成一个归并段 的时间开销是0（r + s）,其中r与s分别为要合并的两个归并段的长度。通过不断地合 并两个归并段，可将n个不同长度的

16、归并段最终合并成一个归并段。设有n个归并段, 其长度分别为11,12，,加，要求将这n个归并段合并成一个归并段，描述一个时间开销最 小的实现方案，给出时间复杂性分析。3. （10分）下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的 深度优先搜索生成树和广度优先搜索生成树。二、算法题（共2题，每题12分，共24分）1 .（12分）令A和B都是带表头结点的单链表，假定A和B的元素都是按序（递增 次序）排列的，设计算法用以创立一个新的有序（递增次序）链表C, C表中包含了 A和 B的所有元素。要求使用A和B的物理结点来建立链表C,链表C建立后，A和B变为空。 描述算法的设计思想根据设计思想

17、，给出算法实现,关键之处请给出注释.说 明你所设计算法的时间复杂度。2 . （12分）有n个顶点的无向图，使用邻接矩阵作为存储结构。为减少存储空间， 只保存下三角矩阵。请给出映射关系，并编写算法计算给定顶点的度。描述算法的设 计思想根据设计思想,给出算法实现,关健之处请给出注释.（3）说明你所设计算法的 时间复杂度。操作系统一、概念解释（每题4分，共20分）1 .引导程序2 .稳定的存储器（Stable Storage）3 .分时系统4 . CPU的内核态5 .高速缓存（Cache）二、简答题（每题10分，共30分）1 .有一个电影院，有1个入口，2个出口。每个入口或出口一次只能进或出一个人。

18、 电影院内的座位数有38个。请用信号量机制描述观众进出电影院时，他们之间的同步行 为。2 .什么是线程池（Thread Pool） ?在服务器中采用线程池有什么好处？3 .什么是地址绑定(Address Binding) ?有哪几种类型的地址绑定？说明他们的应 用场景和作用.计算机组成一、简答题。(第1小题6分，第2小题4分，第3小题7分，第4小题8分，共25分)1 . DMA数据传输包括哪几个阶段？简述预处理阶段所做的工作。2 .简要说明采用层次结构存储系统的目的，以及采用层次结构存储器能到达预期目的的原理。二、分析设计题。（第1小题13分，第2小题12分，共25分）1 .设CPU有18根地

19、址线（灯7A0）, 8根数据线（D7DO）,用碣做访存控制信号（低电平有效），而作读写控制信号（高电平为读，低电平为写）。现有以下芯片：4KX8位RAM； 2KX8位ROM及3-8译码器和各种门电路。主存地址空间为：28800H开始 为 2K ROM, 2E000H 开始为 8K RAM.要求:（1）合理选用上述存储芯片，说明各选几片.（2）画出CPU与存储器连接图，图中标明信号线的方向、种类和条数。2 .某主机数据通路如以下图所示。其中，M为主存，XR为变址寄存器,EAR：有效地址寄存器，LATCH为锁存器。指令格式为：ADD *D （*表示相对寻址，D为相对偏移社）;指令含义为：（ACC）

20、 + （相对寻址的操作数）一（ACC）；指令字长为存储字长。写出完 成该指令所需要的全部微操作流程及节拍安排（从取指令开始）0山东大学二。一四年招收攻读硕士学位研究生入学考试试题科目代码 851科目名称 计算机基础综合（答案必须写在答卷纸上，写在试题上无效）一、数据结构局部（共50分）1. （8分）铁路进行列车调度时,常把站台设计成栈式结构,如以下图所示。现有编号 为1,2,3,4,5,6的6辆列车,顺序开入栈式结构的站台，那么可能的出找序列有多少种? 假设进站的6辆列车顺序为123456,那么是否能够得到435612、325641、154623和135426 的出站序列?如果不能，说明为什么

21、.2. （10分）分析如以下图所示的AOE网络工程，回答以下问题：a）这个工程最早可能在什 么时间结束？ b）确定哪些活动是关键活动。c）画出由所有关键活动构成的图，指出加速 哪些活动可以使整个工程提前完成。3. （12分）分析比拟插入排序、简单项选择择排序、快速排序和归并排序四种排序算法 的时间复杂度.并说明针对已经有序的数据集情况，这些排序算法所需要进行的实际美 键字比拟次数的变化。!4.（10分）给定采用二叉集存储的二叉树，设计算法输出该二叉树从根节点到叶子节点的最长路径，并输出最长路径长度：5. （10分）给定采用邻接表存储的带权无向连通图G和图中的个顶点v,设计算法 求解图G中距离顶

22、点v最远的一个顶点。二、操作系统局部（共50分）1 .（10分）解释名词:高速缓存（Caching）、临界区（CriticalSection）2 .（10分）设有四个进程，到达就绪队列时间及执行时间如下表所示，假设分别采用剥 夺式最短作业优先调度和三级反应队列调度（其中一级和二级队列采用时间片调度,时 间片分别为2和4,三级队列采用FCFS调度），分别给出各进程的调度次序及平均等待时 间（给出计算过程）。进程到达就绪队列时间执行时间PI06P?18P323PJ3123. （10分）假设有个空盘子最多能存放10苹果或者梨，爸爸每次随机选择一个苹果或 者个梨削皮后放到盘子中。儿子喜欢吃苹果，每次从

23、盘子中取个苹果并吃掉，并用 i coumAppleO来统计吃的苹果个数.女儿宓欢吃梨,每次取个梨并吃掉，用couniPearO j来统计吃掉的梨个数.请用信号量机制来描述三者的同步关系。4. （10分）文件系统采用混合索引结构.设块长为512字节,块号占2个字节,文件 控制块中的直接索引块号行10个，另有分别指向、二级索引的两个指针。试问该文件 系统最多能存储多大的文件？混合索引有什么优点？5. （10分）请说明线程、进程和程序的区别与联系。三、计算机组成原理局部（共50分）1. （5分）DMA控制器的基本组成有哪些？2. （5分）证明:y补,通过连同符号位一起求反,最低位加1，可以得到卜yj

24、补。3. （10分）CRC码中的生成多项式应当满足什么要求？4. （10分）什么是中断屏蔽？它是怎样实现的?5. （10分）设计一个基本时序系统，该系统具有4个节拍电平，画出时序图,一出实 现此系统的逻辑结构图。6、（10分）单总线结构上机框图如下，存储器按字编址，指令格式为：SUB （RS）, RD ；源操作数RS为寄存器间接寻址，目的操作数RD为寄存器直接 寻址。操作形式为：口的操作数减 源操作数，写出该指令的执行流程（从取指令开始）。2015年山东大学851计算机基础综合考研真题山东大学二0一五年招收攻读硕士学位研究生入学考试试题科目代码 851科目名称计算机基础综合(请将所有试题答案写

25、在答题纸上，写在试题上无效)一、填空题(共6题，每空1分，共10分)1、X原4X1X2X3X4,假设耍XA1/2成立，X1X2X3X4应满足的条件是：,“ 2、流水线性能主要由、三项指标来衡量.3、浮点数的精度主要取决于 的位数，浮点数的表示范围主要取决于的位虬4、寄存器一次间接寻址方式中，操作数在.5、设机器数字长为32位，欲表示10万的卜进制数，在保证数的最大精度的前 提下，除阶符、数符各取1位外，尾数取 位.6、某机器指令字长16位，每个操作数的地址码长5位，设操作码长度固定，指令 分等地址、单地址和二地址格式。假设零地址指令有T种，二地址指令有M种，那么 单地址指令有 种；假设按变长操

26、作码考虑，那么单地址指令有 种。二、名词解析(共4题，每题2.5分，共10分)】、进程(Process)2、死锁(DcadLock)3、虚拟存储器(Virtual Memory)4、设备驱动程序evice Driver)三、简答题（共11题，共90分）! （5分）、主存用来存储程序和数据，CPU如何区分从内存中读取出的内容是程序还 是数据？2 （5分）、设某计算机主存容量为1MB, Cache容量为16KB,每个字块有8个字，每 个字为32位，果用4路组相联映像，问：（1） Cache主存地址各字段如何划分（各需多少位）？（2）写出内存地址心986H可能映射成的Cache地址（用16进制表示）

27、。3 （5分）、假设定点小数具有1位符号位、4位数据位。117己知：A - -77 1 B -求：lA+Bi补并判断是否溢出。1610（5分）、计算定点原码一位乘法XXY：原:？其中X=0.1011, Y： 0.1010,写出计 算步骤.4 （10分）、简要描述进程调度中多级反做队列调度算法的基本思想，并且说明它是 如何降低系统开销、减小进程平均等待时间和维护调度的公平性的。5 （10分）、在某个采用页式存储管理系统中，某作业有4个页面，被分别装入到主 存的第3, 4, 6, 8块中。假定页面和页框的大小均为1024字节，主存容应为10K 字节c当该作业执行到地址为500的一条传送指令MOV

28、AX, 3100时，箱计算指 令中31001（卜进制）对应的物理地址，试说明地址变换的过程及得到的物理地址。6 （10分）、为防止某种病毒的传播，机场对每个到来航班中的所有乘客都要进行检 查，没有任何感染病症者才准予放行,机场设置一个容纳50人的休息室供乘客 休息并等候医生检资，开始的时候休息室是空的.当乘客下飞机提取自己的行李 后，假设休息空中有空座位，那么进入休息室等候构交，否那么需要在休息室门口等待。 医生每次呼叫一个在休息室中等待的乘客进入检查室对其进行检查，无乘客时医 生休息。试用信号量描述乘客及医生的活动。7 （10分）、在一个多线程的进程中，线程之间可以共享如下哪些资源：D寄存器

29、； 2）堆;3）校；4）全程变量:5） 1/0端口，并说明共享或不能共享的理由。9(10分)、设散列表长度为11,散列函数Hash(k)=咪11,假设输入序列为22, 41,53, 46, 30, 13, 01, 67),解决溢出的方法为线性开型寻址散列，(1)请构造该散列表。(2)搜索元素30和元素67所需要的比拟次数是多少？(3)给出删除元素0i以后的散列表结构。(4)在线性开型寻址散列表中实现删除时，如果只是把删除元素所在的桶置空， 会出现什么问题？给出一种你的解决方法.10 (10分)、以下森林，将其转换成二叉树,给出二叉树的中序、后序遍历序 列.11(10分)、有n个学生选课，(i,j)表示学生i和学生j选择了同一门课科对任 意给出的选课集合S=(1,3), (2,4), (5,7),(7,9), (1,6),), n个学生共选择了 多少门不同的课程？Ui、算法题(共2题，每题10分，共20分)1、在包含n个元素的单向链表中，找到捱表中倒数第k个元素，kn.耍求攵杂性 为0(n)。表达算法思想并给出算法实现.2、为最大堆MaxHeap类中设计一个共享成员函数ChangeMax(x),将当前最大兀索 改为元素x, x的值可以大于或小于当前坡大元素的值，表达算法思想并给出算法 实现。给出算法的时间复杂性。