2019年专业课考研真题：山东大学851计算机基础综合

认真研究历年真题，分析出题方向和特点，这是专业课备考的关键。今天小编就为大家整理了山东大学851计算机基础综合2019年考研真题，希望大家认真学习，通过真题的学习对考试内容和命题思路有大概的了解，预祝大家都能进 入理想的院校。

2019年专业课考研真题：山东大学851计算机基础综合

数据结构

一、简答题(共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求时间复杂性为0(n) 。(1) 描述算法的设计思想(2) 根据设计思想给出算法实现,关键之处请给出注释.

2. (12 分)设二叉树采用链表描述，t为指向根节点的指针，节点结构为(leftchi ld, data, ri ghtchild),其中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=-11/16，y=14/16，用原码-一位乘法计算x*y, (写出计算步骤)。

3.设指令字长为16位，采用扩展操作码技术，每个操作数的地址为6位。如果定义了13条二地址指令，试问还可安排多少条一地址指令?

4.在程序查询方式的输入输出系统中，假设不考虑处理时间，每一个查询操作需要100个时钟周期，CPU的时钟频率为40MHtz.现有鼠标和硬盘两个设备，而且CPU必须每秒对鼠标进行30次查询，硬盘以32位字长为单位传输数据即每32位被CPU查询一次，传输率为2. 5MBps.求CPU对这两个设备查询所花费的时间比率，由此可得出什么结论?

二、分析设计题(第1小题12分，第2小题13分，共25分)

1.设某微型计算机的寻址范围为64K，接有8片8K的存储芯片，存储芯片的片选信号为Cs .要求:

(1)画出选 片译码逻辑电路(可选用74138译码器)

(2)5写 出每片RAM的地址范围

(3)如果运行时 发现只有以000H为起始地址的一片存储芯片不能读写，分析故障原因，如何解决?

2.某主机数据通路如下图所示。指令格式为: ADD @B; 其中，B是通用寄存器，e.为间接导址符号，指令含义为: (AC)加(B)- -> AC:即将B的内容所指主存单元的数据与AC中的数据相加，并将结果送入AC 中保存。该指令字长为存储字长，存储器按字编址。写出完成该指令所需要的全部微操作流程和节拍安排(从取指令开始)。

点击查看： 关注：启航教育考研课程618大促活动攻略

点击获取：2023年考研备考干货及助考工具>