1、第 1 页 共 8 页 电子科技大学电子科技大学 2015 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题 考试科目：考试科目：820 计算机专业基础计算机专业基础 注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 计算机操作系统计算机操作系统 一、填空题（一、填空题（5 分，每空分，每空 1 分）分） 1. 在生产者消费者问题中，若 10 个生产者、5 个消费者共享容量为 8 的缓冲区，则互斥使用缓冲区的信号量的初值为 。 2. 某简单段式存储管理系统中，地址长度为 32 位，若允许的最大段长为 64KB，则段
2、号占 位。 3. 设文件 F1 的当前引用计数值为 1，先建立文件 F1 的符号链接（软链接）文件 F2，再建立文件 F1 的硬链接文件 F3，然后删除文件 F1。此时，文件 F2 和文件 F3 的引用计数值分别为 、 。 4. 某文件占 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为 200s，将缓冲区的数据传送到用户区的时间为 100s，CPU 分析一块数据的时间为 100s，则在双缓冲区结构下，读入并分析完该文件的时间为 s。 二、选择题（二、选择题（10 分，每题分，每题 1 分）分） 1.
3、提高单机资源利用率的关键技术是（ ） 。 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处于安全状态，
4、且安全序列为 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. 虚拟设备是指
5、（ ） A允许用户以统一的接口使用物理设备 B允许用户使用比系统具有的物理设备更多的设备 C把一个物理设备变换为多个对应的逻辑设备 D允许用户程序部分装入内存即可使用系统中的设备 10. 对目录和文件的描述正确的是（ ） 。 A文件大小只受磁盘容量的限制 B多级目录结构形成一颗严格的多叉树 C目录也是文件 D目录中可容纳的文件数量只受磁盘容量的限制 三简答题（三简答题（20 分，每题分，每题 10 分）分） 1. 什么是临界资源、死锁？若采用以下算法解决哲学家就餐问题，是否会导致死锁？为什么？ semaphore fork5 = 1, 1, 1, 1, 1; void main() cobeg
6、in 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. 文件物理结构是指一个文件在外存上的存储组织形式，主要有连续结构、链接结构和索引结构三种，请分别简述它们
7、的优缺点。 四、分析计算题（四、分析计算题（40 分，每题分，每题 20 分）分） 1. 某 32 位计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 4KB，页表项大小为 4B。某进程的页表内容如下图所示（图中数字为十进制） ，请回答以下问题： （1） 给出逻辑地址结构示意图，请说明理由； （2） 计算逻辑地址 4206501（十进制）对应的物理地址。 第 4 页 共 8 页 2. 某双车道公路中一小段因发生塌方事故，变成了单车道（对向行驶的车辆无法同时通行） ，如下图所示。为保证车辆顺利通行，必须对经过塌方路段的车辆予以控制。请用信号量描述此控制过程，并说明信号量含义。 428
8、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
9、结点的操作是 和 。 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 个位置插入一个
10、新元素的算法时间复杂度为（ ） （1in+1） 。 AO（1） BO（i） CO（n） DO（n2） 2 一个栈的输入序列为 1,2,3，n，若输出序列的第一个元素是 n，输出第 i（1in）个元素是（ ） 。 An-i Bn-i-1 Cn-i Di 3 广义表（ （a,（b,c） ）,d,e）的表头是（ ） 。 Aa B （a,（b，c） ） C （a） D （b，c） 4 以下哪些遍历序列的组合可以还原二叉树（ ） 。 A先序遍历序列和后序遍历序列 B后序遍历序列和中序遍历序列 C先序遍历序列和层序遍历序列 D中序遍历序列和层序遍历序列 5 与克鲁斯卡尔 （Kruskal） 相比， 普里姆
11、 （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。表
12、中已填关键字：13,25,68，其余地址为空，如用二次探测再散列处理冲突，关键字为 75 的地址是（ ） 。 A1 B3 C7 D9 10. 已知关键字序列 5,8,12,19,28,20,15,22 是小根堆（堆顶元素为最小值） ，插入关键字3，调整后得到的小根堆是（ ） 。 A3,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，
13、如果其终端结点数为 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） 说明你所设计算法的时间复杂度。
