2019年安徽师范大学计算机理论基础考研真题.doc

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2019 年安徽师范大学计算机理论基础考研真题第一部分数据结构（80 分）一、简答题（每小题 4 分，共 20 分） 1.根据数据元素之间关系的不同特性，可将逻辑结构分为哪几种?并简述各结构的特性。 2.试比较顺序表和链表的优缺点。 3.简述队列的"假渣出"现象。 4.度为 2 的树是二叉树，此说法是否正确?请给出理由。 5.有 n 个顶点的有向强连通图中最多有多少条边?最少有多少条边? 二、应用题（每小题 8 分，共 40 分） 1.以数据集 4，5，6，7，10，12，18}为结点权值，面出构造 Hurffman 树的过程，并计算该 Hffean 树的带权路径长度（约定∶权值最小的作为左孩子，权值次小的作为右孩子） 2.已知有 7 个顶点下面问题∶ 的有向图的邻接矩阵如右图所示。请回答（1）依据邻接矩阵表示，画出该有向图的邻接表。（2）写出从 w 出发的深度优先遍历序列和广度优先遍历序列。 3.请用克鲁斯卡尔算法为下图构造最小生成树，请画出构造过程。 4.已知待排序的关键字序列（54，38，96，23，15，90，72，60，45，83），完成下列各小题（要求结果非递减有序）。（1）写出进行一趟希尔排序（增量序列为 5）的排序结果; （2）写出以第一个元素为枢轴的一趟快速排序的排序结果。 5.设一组关键字为（7，4，1，14，100，30，5，9，20，134），Hash 函数 H（key）=key ， Hash 表表长 m=13，用线性探测法解决冲突，试构造 Hash 表。三、算法设计题（每小题 10 分，共 20 分） 1.有一个顺序表 L，其元素为整型，设计一个算法将 L 中所有小于 0 的整数放在前半部分，

大于等于 0 的整数放在后半部分，要求;时间复杂度为 0（n），空间复杂度为 0（1），给出顺序表的类型定义。 2.设计算法计算一棵二叉树 T 中的叶子结点数，要求给出二叉树的类型定义。第二部分操作系统（70 分）一、简答题（每小题 6 分。共 30 分） 1.简述操作系统的基本功能。 2.简述操作系统中引入线程的原因。 3.什么是进程间的互斥? 4.在抢占调度方式中，抢占的原则是什么? 5.有哪几种 I/0 设备的控制方式? 6.文件的物理结构与外存组织方式有关，目前常用的外存组织方式有哪些? 二、应用题（每小题 10 分，共 40 分） 1.设有数组 int a[100][100]，并按行存储。计算机采用虚拟存储系统，假定内存共有三个物理块，一块用于存放程序，另两块用于存放数据，每个物理块可存放 200 个整数。设访问数组 a 的程序已在内存，其余两块初始为空。试问若使用 LRU 页面置换算法，程序 1、2 在执行过程中各会产生多少次缺页? 2.请求分页管理系统中，假设某进程的页表内容如右表所示。存在位页号物理块号页面大小为 4KB，一次内存的访问时间是 100ns，一次快表（TLB）的访问时间是 10ns，处理一次缺页的平均时间为 100ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2，采用 LRU 置换算法和局部置换策略。假设∶ ①TLB 初始为空; ②地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）; ③存在位为 0 表示页面不在内存，产生缺页中斯，中断处理后，返疯到产生缺页中断的指令处重新执行。设有虚地址访问序列 2362H、1566H、25A5H，请问∶ （1）依次访问上述三个虚地址，各需多少时间?给出计算过程。（2）基于上述访问序列，虚地址 1565H 的物理地址是多少?请说明理由。 3.某计算机系统利用下图所示的位示图（行号、列号都从 0 开始编号）来管理空闲盘块。如果盘块从 1 开始编号，每个盘块大小是 1KB。（1）现要为某文件分配两个盘块，试具体说明分配过程。（2）若要释放磁盘的第 300 块，应如何处理?

4.某杂技团进行走钢丝表演。在钢丝的 A、B 两端各有 n 名演员（n>1）在等待表演。只要钢丝上无人时便允许一名演员从钢丝的一端走到另一端。现要求两端的演员交替地走钢丝，且从 A 端的一名演员先开始。请问∶把一名演员看作一个进程时，怎样用 PV 操作进行控制? 请写出正确的算法。

分享到：

赞收藏

资料库

2019年安徽师范大学计算机理论基础考研真题.doc

相关推荐

考研

热门标签

最新资料