2019年山东大学计算机基础综合考研真题.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.13M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2019 年山东大学计算机基础综合考研真题数据结构一、简答题（共 3 题，共 26 分） 1.（8 分）散列表长度为 13，散列函数为 Hash（k）=k%13。请分别写出序列（12，8， 16，27，21，17，3，28，47）的线性开型寻址散列存储结构和链表散列结构。 2.（10 分）假设用于通信的电文由字符集{a，b，c，d，e，f，g 中的字母构成，它们在电文中出现的频率分别为{31，16，10，8，11，20，4）。（1）画出霍夫曼树（霍夫曼树构造中，左子树权值小于等于右子树），并求 WPL; （2）为这 7 个字母设计霍夫曼编码（分支编码左 0 右 1）; （3）对这 7 个字母进行等长编码，至少需要几位二进制数?霍夫曼编码比等长编码使电文总长压缩多少? 3.（8 分）如何判别以邻接表方式存储的无向图中是否存在由顶点 u 到顶点 v 的路径（u≠v），请描述出实现思路。二、算法题（共 2 题，每小题 12 分，共 24 分） 1.（12 分）在包含 n 个元素的单向链表中，找到链表中倒数第 k 个元素，k

2.（12 分）设二叉树采用链表描述，t 为指向根节点的指针，节点结构为（leftchild，data， rightchild，其中 data 为元素的值，，leftchild 和 rightchild 分别表示指向左孩子结点和右孩子结点的指针。设计算法，判断二叉树是否为最小堆。（1）描述算法的设计思想（2）根据设计思想，给出算法实现，关键之处请给出注释. （3）说明你所设计算法的时间复杂度。操作系统一、概念解释（每小题 4 分，共 20 分） 1.对等模式（Peer to Peer） 2.应用程序（Application Program） 3.操作系统的分层设计方法 4.虚拟机 5.上下文切换

二、简答题（每题 10 分，共 30 分） 1.有一个停车场，有两个入口，三个出口。车辆进入时需要登记，出来时要缴费。每个入口或出口同时只能为一辆车服务。车库内的停车位有 52 个。请用信号量机制描述每辆车进出停车场时，车辆之间的同步行为。 2.什么是线程池（Thread Pool）?在服务器中采用线程池有什么好处? 3.在调页式虚拟内存管理中，假设当前进程可分配页面数为 3，以下是页面访问的次序∶ 0,1,2,1,3,4,1,3,0,3,2 请分别计算采用 FIFO 和 LRU 方法需要置换页的次数。计算机组成一、简答题（第 1、3 小题各 5 分，第 2 小题 7 分，第 4 小题 8 分，共 25 分） 1.以全相联映射技术为例，说明在带有 Cache 的存储系统中，"读"操作是怎样完成的。 2.设用原码一位乘法计算 x·y，（写出计算步骤）。 3.设指令字长为 16 位，采用扩展操作码技术，每个操作数的地址为 6 位。如果定义了 13 条二地址指令，试问还可安排多少条一地址指令? 4. 在程序查询方式的输入输出系统中，假设不考虑处理时间，每一个查询操作需要 100 个时钟周期，CPU 的时钟频率为 40MHz。现有鼠标和硬盘两个设备，而且 CPU 必须每秒对鼠标进行 30 次查询，硬盘以 32 位字长为单位传输数据，即每 32 位被 CPU 查询一次，传输率为

2.5MBps。求 CPU 对这两个设备查询所花费的时间比率，由此可得出什么结论? 二、分析设计题（第 1 小题 12 分，第 2 小题 13 分，共 25 分） 1.设某微型计算机的寻址范围为 64K，接有 8 片 8K 的存储芯片，存储芯片的片选信号为 CS，要求∶ （1）画出选片译码逻辑电路（可选用 74138 译码器）（2）写出每片 RAM 的地址范围（3）如果运行时发现只有以 0000H 为起始地址的一片存储芯片不能读写，分析故障原因，如何解决? 2.某主机数据通路如下图所示。指令格式为∶ADD @B;其中，B 是通用寄存器，@为间接寻址符号，指令含义为∶（AC）加（（B））—>AC;即将 B 的内容所指主存单元的数据与 AC 中的数据相加，并将结果送入 AC 中保存。该指令字长为存储字长，存储器按字编址。写出完成该指令所需要的全部微操作流程和节拍安排（从取指令开始）。

分享到：

赞收藏

资料库

2019年山东大学计算机基础综合考研真题.doc

相关推荐

考研

热门标签

最新资料