资源描述
第 1 页 共 8 页 电子科技大学 2015年攻读硕士学位研究生入学考试试题 考试科目：820计算机专业基础 注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 计算机操作系统 一、填空题（5分，每空1分） 1. 在生产者消费者问题中，若 10个生产者、5个消费者共享容量为8的缓冲区，则互斥使用缓冲区的信号量的初值为 。 2. 某简单段式存储管理系统中，地址长度为32位，若允许的最大段长为64KB，则段号占 位。 3. 设文件F1的当前引用计数值为1，先建立文件F1的符号链接（软链接）文件F2，再建立文件F1的硬链接文件F3，然后删除文件F1。此时，文件F2和文件F3的引用计数值分别为 、 。 4. 某文件占 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为200s，将缓冲区的数据传送到用户区的时间为 100s，CPU 分析一块数据的时间为 100s，则在双缓冲区结构下，读入并分析完该文件的时间为 s。 二、选择题（10分，每题1分） 1. 提高单机资源利用率的关键技术是（ ）。 A 脱机技术 B多道程序设计技术 C虚拟技术 D缓冲技术 2. 进程的基本状态（ ）可以由其它两种基本状态转变而来。 A就绪状态 B执行状态 C阻塞状态 D新建状态 3. 在高响应比进程调度算法中，其主要影响因素是（ ）。 A 等待时间 B剩余运行时间 C已运行时间 D静态优先级 4. 系统中资源R的数量为12，进程P1、P2、P3对资源R的最大需求分别为10、4、9。若当前已分配给P1、P2、P3的资源R的数量分别为5、2、2，则系统（ ）。 A 处于不安全状态 B处于安全状态，且安全序列为P1-P2-P3 C处于安全状态，且安全序列为P2-P3-P1 D处于安全状态，且安全序列为P2-P1-P3 5. 分页系统中的页面为（ ）。 A 用户所感知 B操作系统所感知 第 2 页 共 8 页 C编译程序所感知 D链接、装载程序所感知 6. 虚拟存储管理系统的基础是程序的（ ）理论。 A动态性 B虚拟性 C局部性 D共享性 7. DMA是在（ ）建立一条直接数据通路。 AI/O设备和主存之间 BI/O设备之间 CI/O设备和CPU之间 DCPU和主存之间 8. 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。 A 主设备号 B次设备号 C物理设备名 D逻辑设备名 9. 虚拟设备是指（ ） A允许用户以统一的接口使用物理设备 B允许用户使用比系统具有的物理设备更多的设备 C把一个物理设备变换为多个对应的逻辑设备 D允许用户程序部分装入内存即可使用系统中的设备 10. 对目录和文件的描述正确的是（ ）。 A 文件大小只受磁盘容量的限制 B多级目录结构形成一颗严格的多叉树 C目录也是文件 D目录中可容纳的文件数量只受磁盘容量的限制 三简答题（20分，每题10分） 1. 什么是临界资源、死锁？若采用以下算法解决哲学家就餐问题，是否会导致死锁？为什么？ semaphore fork5 = 1, 1, 1, 1, 1; void main() cobegin philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4); coend void philosopher(int i) while(1) thinking; if (i = 0) P(forki); P(fork(i+1)%5); else 第 3 页 共 8 页 P(fork(i+1)%5); P(forki); eating; V(forki); V(fork(i+1)%5); 2. 文件物理结构是指一个文件在外存上的存储组织形式，主要有连续结构、链接结构和索引结构三种，请分别简述它们的优缺点。 四、分析计算题（40分，每题20分） 1. 某 32 位计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 4KB，页表项大小为4B。某进程的页表内容如下图所示（图中数字为十进制）， 请回答以下问题： （1） 给出逻辑地址结构示意图，请说明理由； （2） 计算逻辑地址4206501（十进制）对应的物理地址。 第 4 页 共 8 页 2. 某双车道公路中一小段因发生塌方事故，变成了单车道（对向行驶的车辆无法同时通行），如 下图所 示。为保证车辆顺利通行，必须对经过塌方路段的车辆予以控制。请用信号量描述此控制过程，并说明信号量含义。 428 367 496 506 607 709 812 942 321 242 372 485 0 1 2 n 0 1 2 n 0 1 2 n 0 1 2 n 一级页表： 页表项序号 二级页表： 101 242 372 485 物理块号 第 5 页 共 8 页 塌方路段 单车道 正常路段 双车道 正常路段 双车道 第 6 页 共 8 页 数据结构 一、填空题（共10分，每空1分） 1 数据的逻辑结构是对数据之间关系的描述，主要有 和 两大类。 2 程序for(int i=0;in;i+=5)；的时间复杂度为 。 3 在单链表L中的p结点之后插入q结点的操作是 和 。 4 循环队列的容量为MAXSIZE，采用牺牲一个存储空间进行构造，队头指针是front，队尾指针是rear，则队空的条件是 。 5 具有512个结点的完全二叉树的深度为 。 6 若以5,6,7,8,9作为叶结点的权值构造哈夫曼树，则其带权路径长度是 。 7 G是一个非连通无向图，共有15条边，则该图至少有 个顶点。 8 设有一组初始关键字序列（46,79,56,38,40,84），执行第一趟快速排序后所得序列是 。 二、单选题（共20分，每题2分） 1 具有n个元素的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（ ）（ 1 i n+1）。 A O （ 1 ） BO（i） CO（n） DO（n2） 2 一个栈的输入序列为1,2,3，n，若输出序列的第一个元素是n，输出第i（1in）个元素是（ ）。 A n-i Bn-i-1 Cn-i Di 3 广义表（ a,（b,c） ,d,e）的表头是（ ）。 A a B（a,（b，c） C（a） D（b，c） 4 以下哪些遍历序列的组合可以还原二叉树（ ）。 A 先序遍历序列和后序遍历序列 B后序遍历序列和中序遍历序列 C先序遍历序列和层序遍历序列 D中序遍历序列和层序遍历序列 5 与克鲁斯卡尔（Kruskal）相比，普里姆（Prim）算法更适于求哪种网的最小生成树（ ）。 A 边稠密的网 B边稀疏的网 C顶点稠密的网 D以上都不是 6 关键路径是事件结点网络中（ ）。 A 从 源点 到汇 点的最短路径 B从源点到汇点边数最多的路径 C从源点到汇点结点数最多的路径 D从源点到汇点的最长路径 7 若用邻接矩阵存储有向图，矩阵中主对角线以下元素均为零，则关于该图拓扑序列的结论是（ ）。 A 存在，且唯一 B存在，但不唯一 C存在，可能不唯一 D无法确定是否存在 8 在下列排序算法中，占用辅助空间最多的是（ ） A归并排序 B快速排序 C希尔排序 D堆排序 9 设哈希表长m=9,哈希函数 H（key）=key%7。表中已填关键字：13,25,68，其余地址为空，如用二次探测再散列处理冲突，关键字为75的地址是（ ）。 A 1 B3 C7 D9 10. 已知关键字序列5,8,12,19,28,20,15,22是小根堆（堆顶元素为最小值）， 插 入关键字3，调整后得到的小根堆是（ ）。 A 3,5,12,8,28,20,15,22,19 B3,5,12,19,20,15,22,8,28 第 7 页 共 8 页 C3,8,12,5,20,15,22,28,19 D3,12,5,8,28,20,15,22,19 三、简答题（共20分，每题5分） 1. 对任何一颗二叉树T，如果其终端结点数为 n0，度为 2的结点数为 n2，推导 n0 与n2的关系。 2. 图1所示的平衡二叉树中，插入节点48，请画出插入位置及插入后每个节点的平衡因子，并调整为新的平衡二叉树。 3. 给定下图AOV网，如图2所示，写出5个拓扑排序序列。 4. 设G=（V，E）以邻接表存储，如图3所示，以顶点v1为根画出图的深度优先和广度优先生成树。 图2 AOV网 图1 平衡二叉树 图3 G的邻接表 第 8 页 共 8 页 四、算法题（共25分） 1. （10 分）给定两个升序线性表 L1 和 L2，设计一个函数，将两个升序线性表合并为一个升序线性表L，新线性表L中无重复数据。 2. （15分）采用二叉链表的存储结构，用非递归算法（pop(s,t)，push(s,t)）交换二叉树的左右子树，要求： （1） 给出算法的基本设计思想。 （2） 根据设计思想，设计一个算法。 （3） 说明你所设计算法的时间复杂度。
展开阅读全文