1、第 1 页 共 4 页 电子科技大学电子科技大学 2016 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题 考试科目：考试科目：820 计算机专业基础计算机专业基础 注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 计算机操作系统计算机操作系统 一、填空题（一、填空题（10 分，每空分，每空 2 分）分） 1. 若信号量S的初值为4， 当前有6个进程在等待信号量S， 则当前信号量S的值为 。 2. 某系统中共有 11 台打印机，X 个进程共享此打印机，每个进程最多请求使用 3 台打印机，则该系统中不会发生死锁的最
2、大 X 值是 。 3. 虚拟存储管理系统的基础是程序的 理论。 4. 为满足 264地址空间的作业运行，采用多级分页存储管理方式，假设页面大小为 4KB，在页表中的每个页表项需要占 8 字节。那么，为了满足系统的分页存储管理，至少应采用 级页表。 5. 某文件系统的文件控制块占 64B，单个盘块大小为 1KB，采用一级目录结构。假设文件目录中有 3200 个目录项，则查找一个文件平均需要访问 次磁盘。 二、选择题（二、选择题（14 分，每题分，每题 2 分）分） 1. 若下列指令已装入指令寄存器， 执行时不可能导致CPU从用户态变为内核态的是 （ ） 。 ADIV R0，R1； (R0)/(R
3、1)R0 BINT n； 产生软中断 CNOT R0； 寄存器 R0 的内容取非 DMOV R0,addr； 把地址处的内存数据放入寄存器 R0 中 2. 在下列进程调度算法中，不存在进程饥饿现象的调度算法是（ ） 。 A先来先服务 B反馈调度算法 C短进程优先 D基于静态优先级调度算法 3. 资源的有序分配策略是为了破坏死锁产生的（ ）条件。 A互斥 B请求和保持 C非剥夺 D循环等待 4. 在段式存储管理系统中，若不考虑快表，为获得一条指令或数据，至少需要访问（ ）次内存。 A1 B2 C3 D4 5. 在设备管理中，不属于 I/O 控制方式的是（ ） 。 A程序查询方式 B中断驱动方式
4、CDMA 方式 D重定位方式 第 2 页 共 4 页 6. 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ） 。 A哈希文件 B索引文件 C链式结构文件 D连续结构文件 7. 设置当前工作目录的主要作用是（ ） 。 A加快文件的读/写速度 B加快文件的检索速度 C节省外存空间 D节省内存空间 三、简答题（三、简答题（4 题，共题，共 21 分）分） 1. PCB 的主要存储内容是什么？为什么说 PCB 是进程存在的唯一标志？（6 分） 2. 什么是虚拟存储器？如何实现页式虚拟存储器？（5 分） 3. 什么是设备的独立性，应如何实现？（5 分） 4. 文件物理结构是指一个文件在外存上的存
5、储组织形式，那么何谓文件的混合索引结构？其主要优点是什么？（5 分） 四、分析计算题（四、分析计算题（2 题，共题，共 30 分）分） 1. 某计算机采用段页式虚拟存储器，已知虚拟地址为 32 位，按字节编址，每个段最多可以有 2K 页，页大小为 16KB，物理主存容量为 512MB。请回答以下问题： （10 分） （1） 虚拟存储器的容量是多少？ （2） 给出逻辑地址结构并说明理由。 （3） 计算逻辑地址 0X4EB9FDE3 的段号，段内页号及页内偏移值（最后计算结果须用十六进制表示） 。 2. N 个生产者进程和 M 个消费者进程共享大小为 K 的缓冲区，遵循规则如下： （1） 进程之间
6、必须以互斥方式访问缓冲区； （2） 对每 1 条放入缓冲区的数据，所有消费者都必须接收 1 次； （3） 缓冲区满时，生产者必须阻塞； （4） 缓冲区空时，消费者必须阻塞。 请用 P、V 操作实现其同步过程，须说明信号量含义。 （20 分） 第 3 页 共 4 页 数据结构数据结构 一、填空题一、填空题(共共 10 空，每空空，每空 1 分，共分，共 10 分分) 1. 顺序表采用的是_存取方式，线性链表采用的是_存取方式。 2. 深度为,(1)d d 的完全二叉树至少含有_个节点， 至多含有_个节点。 3. 3 个节点构成的二叉树有_种不同形状。 3 个元素依次入栈可能的出栈序列有_种。 4
7、. 无向连通图 G 含有n个节点e条边。求 G 的最小生成树，采用 Prim 算法的时间复杂度是_，采用 Kruskal 算法的时间复杂度是_。 5. 快速排序算法平均情况下的时间复杂度是_，空间复杂度是_。 二、单选题二、单选题(共共 10 题，每题题，每题 2 分，共分，共 20 分分) 1. 循环队列为了防止假上溢采用取模运算折叠空间，解决队头队尾指针同指一个单元时候空满判定问题，下列( )选项不是常见的方案。 A. 牺牲一个存储空间 B. 设置一个计数器 C. 设置一个布尔变量 D. 再配置一个指针 2. 下列选项中不属于规则矩阵的是( )。 A. 三角矩阵 B. 对称矩阵 C. 对角
8、矩阵 D. 稀疏矩阵 3. 下列选项中符合前缀码要求的是( )。 A. 0, 1 B. 0, 01, 001, 0001 C. 10, 010, 110, 101 D. 01, 10, 1001, 0110 4. 下列关于哈夫曼树的论述不正确的是( )。 A. 哈夫曼树又被称为最优二叉树 B. 哈夫曼树是带权路径最短的二叉树 C. 一棵哈夫曼树任意交换左右子树仍然是一棵哈弗曼树 D. 对给定的输入数值集合所生成的哈夫曼树深度是确定的 5. 无向图做深度优先搜索和广度优先搜索共有的特点是( ) A. 都是递归类算法 B. 都必须用到栈 C. 都是遍历类算法 D. 搜索结果都是唯一的 6. 对于
9、AOE 网络，若它的关键路径存在，那么该路径一定是( )。 A. 最长路径 B. 最短路径 C. 拓扑排序序列 D. 唯一的一条路径 7. 拓扑排序解决的问题是( )。 A. 对一个有向图进行遍历操作 B. 计算一个有向图的回路个数 C. 判断一个有向图是否有回路 D. 对一个有向图进行线索化 8. 已知广义表 GL=(a, b), (c, d, e), (f, g)，定义取表头函数为 H( )，取表尾函数为 T( )，那么从 GL 中取出数据元素 d 的操作是( )。 A. H(T(T(H(GL) B. H(T(H(GL) C. H(T(H(T(GL) D. H(T(H(H(GL) 9. 对
10、序列(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)进行折半查找元素 14，需要依次比较( )。 A. 10, 18, 14 B. 10, 16, 14 C. 10, 18, 12, 14 D. 10, 16, 12, 14 第 4 页 共 4 页 10. 下列哪种排序算法在一趟过后不能保证至少有一个元素落在最终位置上的是( )。 A. 冒泡排序 B. 希尔排序 C. 快速排序 D. 简单选择排序 三、简答题三、简答题(共共 6 题，每题题，每题 5 分，共分，共 30 分分) 1. 设计一种尽可能高效的策略使得单循环链表成为队列，给出入队和出队的时间复杂度。 2. 输
11、入数据序列为(5, 1, 9, 3, 7)，请按输入序构造排序二叉树，并绘制出它的中序线索。 3. 输入数据序列为(10, 30, 40, 20, 15, 25)，请按输入序构造平衡二叉树。给出每添加一个节点后平衡二叉树的调整结果。 4. 已知输入关键字序列为(13, 14, 15, 16, 17, 5, 4, 3, 2, 1)，根据哈希函数建立哈希表，采用公共溢出区法解决冲突。已知哈希函数为 Hash(key) = key MOD 11，哈希表长为 11，溢出表长为 5。请画出哈希表和溢出表，并计算查找成功时(等概率情况下)的平均查找长度 ASL。 5. 已知 7 项数据记录为(7, 6,
12、5, 4, 3, 2, 1)。将它调整成为小顶堆，给出筛选过程。 6. 全源最短路径问题采用 Floyd 算法进行求解。下面给出了一个由 4 个顶点构成的有向图邻接矩阵 Dist44和路径矩阵 Path44。约定 Dist 中用表示不能到达，Path 中用-1 表示没有前驱的情况。请计算并给出每一次迭代的结果。(请将答案誊写在答题纸上) Dist(-1) Dist(0) Dist(1) Dist(2) Dist(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 1 0 2 5 2 0 1 3 2 0 Path(-1) Path(0) Path
13、(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 -1 0 0 -1 1 -1 -1 1 1 2 -1 -1 -1 2 3 3 -1 -1 -1 四、算法题四、算法题(共共 2 题，共题，共 15 分分) 1. 设规模3 ,1nm m的顺序表存储在一维数组 int arrayn中，它含有的元素为121212( ,)mmma aab bbc cc。 请 编 写 算 法 将 上 述 顺 序 表 改 造 成 为122112( ,)mmmc ccbb b a aa，要求时间复杂度和空间复杂度尽可能低。程序设计语言可以选用 C、C+、Java。(8 分) 2. 二叉树用二叉链表结构进行存储。请编写算法求二叉树根节点左右子树相隔最远的叶子节点之间距离。程序设计语言可以选用 C、C+、Java。(7 分)
