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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2018 年安徽师范大学计算机理论基础考研真题第一部分数据结构（80 分）一、简答题（每小题 4 分，共 20 分） 1.在数据结构中，数据元素之间的关系在计算机中有几种表示方法?各有什么特点? 2.简述线性表、栈和队列的异同。 3.简述二叉树的定义。 4.简述拓扑排序的过程。 5.简述快速排序的基本思想。二、应用题（每小题 8 分，共 40 分） 1.设 n 为 3 的倍数，分析以下算法的时间复杂度（要求必须给出推导过程）。 2.对如下图所示的带权有向图∶ 求∶ （1）每个顶点的入度和出度; （2）给出其邻接矩阵; （3）给出其邻接表。 3.如果一棵哈夫曼树 T 有 no 个叶子结点，那么树 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.考虑系统瞬时状态为∶ Available=1520，利用银行家算法回答下列问题∶ （1）计算数组 need。（2）该系统处于安全状态吗? （3）若进程 P1 提出请求（0420），能否立即满足? 2.某请求分页存储管理系统中，设页面走向为∶1，2，3.1，2，3，2，1，2.5，4，2，5，主存容量为 3 页。试求∶分别采用 LRU（最近最久未使用）、FIFO（先进先出）、Optimal （最优）3 种页面置换算法时的缺页次数。

请回答∶ （1）两个进程并发执行时，能否保证互斥使用资源?为什么? （2）如果要使两个进程交替使用资源，若仍使用 PV 操作进行管理，写出应定义的信号量及其初值。（3）修改上述程序，使两个进程能交替使用资源 r。 4.在 Unix 操作系统中，i 节点定义了 13 个指针，用来存放 13 个物理块号，把文件分成小型、中型、大型和巨型四种，分别采用直接、一次间接、二次间接、三次间接索引方法。试问∶ （1）这种结构有何优缺点? （2）若每块大小为 1KB，每个块号占 4B，问每类文件可能的大小范围是多少?

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料