1、 共 4 页页 第 1 页页 电子科技大学电子科技大学 2014 年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题 考试科目：考试科目：820 计算机专业基础计算机专业基础 注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。 计算机操作系统计算机操作系统 一、一、 填空题（填空题（10 分，每空分，每空 2 分）分） 1. 现有3个同时到达的作业J1、 J2和J3， 它们的执行时间分别为T1、 T2和T3， 且T1T3T2。若这三个作业在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是_。 2. 若一个信
2、号量的初值是 5，经过多次 P、V 操作以后，其值变为- 3，则此时等待进入临界区的进程数目是_。 3. 某基本分页存储管理系统具有快表，内存访问时间为 2s，检索快表的时间为 0.5s。若快表的命中率为 80%，且忽略快表更新时间，则有效访问时间是_s。 4. 在段页式存储管理系统中， 若不考虑快表， 为获得一条指令或数据， 至少需要访问_次内存。 5. 某虚拟存储器中的用户空间共有 32 个页面，每页 1KB，主存 16KB。假设某时刻系统为用户的第 0、1、2、3 页分别分配的物理块为 5、10、4、7，则虚拟地址 0A6F 对应的物理地址是_（请使用十六进制表示） 。 二、二、 选择题
3、（选择题（14 分，每题分，每题 2 分）分） 1. 现代操作系统中最基本的两个特征是（ ） 。 A. 共享和不确定 B. 并发和虚拟 C. 并发和共享 D. 虚拟和不确定 2. 引入多道程序技术的前提条件之一是系统具有（ ） 。 A. 分时功能 B. 中断功能 C. 多 CPU 技术 D. SPOOLing 技术 3. 操作系统是根据（ ）来对并发执行的进程进行控制和管理的。 A. 进程的基本状态 B. 进程调度算法 C. 进程的优先级 D. 进程控制块 4. 在段页式存储管理系统中，地址映射表是（ ） A. 每个进程一张段表，一张页表。 B. 每个进程一张段表，每个段一张页表。 C. 每个
4、进程的每个段一张段表，一张页表。 D. 每个进程的每个段一张段表，多张页表。 共 4 页页 第 2 页页 5. 为使虚拟存储管理系统具有良好的性能，应用程序应具备的特征是（ ） 。 A. 程序模块化程度高，由许多小模块组成 B. 程序应具备良好的局部性特征 C. 程序的 I/O 操作较少 D. 程序实际大小应小于实际物理内存容量 6. ( )的基本含义是指应用程序独立于具体使用的物理设备 A. 设备独立性 B. 设备共享性 C. 可扩展性 D. SPOOLing 技术 7. 从用户的角度看，文件系统主要是实现( ) A. 数据存储 B. 数据保护 C. 数据共享 D. 按名存取 三、三、 分析
5、计算题（分析计算题（30 分）分） 1. 某操作系统的文件系统采用混合索引分配方式，索引节点中包含文件的物理结构数组iaddr10。其中前 7 项 iaddr0iaddr6为直接地址，iaddr7iaddr8为一次间接地址，iaddr9为二次间接地址。系统盘块的大小为 4KB，磁盘的每个扇区大小也为 4KB。描述磁盘块的数据项需要 4 个字节，其中 1 个字节标示磁盘分区，3 个字节标示物理块。请回答一下问题： （1） 该文件系统支持的单个文件的最大程度是多少？（8 分） （2） 若某文件 A 的索引节点信息已位于内存， 但其它信息均在磁盘。 现在需要访问文件A 中第 i 个字节的数据，列举出
6、所有可能的磁盘访问次数，并说明原因。 （6 分） 2. 3 个进程 P0、P1、P2 互斥使用一个仅包含 1 个单元的缓冲区。P0 每次用 produce()生成 1个正整数，并用 put()送入缓冲区。对于缓冲区中的每个数据，P1 用 get1()取出一次并用compute1()计算其平方值，P2 用 get2()取出一次并用 compute2()计算其立方值。请用信号量机制实现进程 P0、P1、P2 之间的同步与互斥关系，并说明所定义信号量的含义，要求用伪代码描述。 （16 分） 四、四、 简答题（简答题（21 分）分） 1. 在存储器管理中，什么是重定位？为什么要引入重定位技术？(5 分
7、) 2. 在分页存储管理系统中，页表的主要作用是什么？现代大多数计算机系统都支持非常大的逻辑地址空间（232264） ，这给页表设计带来了什么样的新问题，应如何解决。 （5分） 3. 以从 I/O 设备读入数据为例，请用流程图方式说明程序 I/O、DMA 传输控制的处理过程。 （6 分） 4. 在哲学家就餐问题中，如果将先拿起左边筷子的哲学家成为左撇子，而将先拿起右边筷子的哲学家称为右撇子。在同时存在左撇子和右撇子的前提下，我们安排哲学家随意就座。请问是否可能产生死锁，为什么？（5 分） 共 4 页页 第 3 页页 数据结构数据结构 一、填空题（共一、填空题（共 10 分，每空分，每空 1 分
8、）分） 1. 一个“好”的算法应考虑达到以下目标：正确性、可读性、健壮性、 。 2. 广义表(),(a),(b,(c,d),f)的深度是 。 3. 遍历二叉树实质上是对一个非线性结构进行 操作。 4. 对有 n 个顶点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度是 。 5. 若一个具有 n 个顶点，e 条边的无向图是一个森林，则该森林中必有 棵树。 6. 求图的最小生成树有两种算法， 算法适合于求边稀疏的图的最小生成树。 7. 最短路径迪杰斯特拉（Dijkstra）算法的复杂度 。 8. 二叉树上有一个结点的平衡因子的绝对值大于 ，则该二叉树就是不平衡的。 9. 哈希表的地
9、址区间为 0-8，哈希函数为 H（K）=K mod 9。采用线性探测法处理冲突，并将关键字序列（12,21,43,5,39）依次存储到哈希表中，则元素 39 存放在哈希表中的地址是 。 10. 排序算法不需要进行记录关键字间的比较。 二、单选题（共二、单选题（共 20 分，每题分，每题 2 分）分） 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表 2. 下述哪一条是链式存储结构的优点？（ ） A存储密度大 B插入、删除运算方便 C存储单元连续 D随机存取第
10、 i 个元素方便 3. 一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 4. 最大容量为 n 的循环队列， 队尾指针是 rear， 队头是 front， 则队满的条件是 （ ） 。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front 5. 若一棵二叉树具有 20 个度为 2 的结点， 10 个度为 1 的结点， 则度为 0 的结点个数是 （ ） A10 B
11、11 C21 D30 6. 二叉树的第 i 层上最多有( )结点。 A2i B 2i-1-1 C 2i-1 D2i-1 7. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定是（ ） A完全二叉树 B只有一个节点 C高度等于其节点数 D二叉排序树 8. 对图进行广度优先搜索遍历类似于二叉树的( )算法。 A先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 共 4 页页 第 4 页页 9. 对下图进行拓扑排序，可以得到不同拓扑序列的个数是( ) A.6 B.5 C.4 D.3 10. 有一组数据（43,21,52,60,12,15）利用快速排序，以第一个元素为基准得到一次划
12、分结果为( )。 A（15,21,12,43,52,60） B.(15,12,21,43,52,60) C. （12,15,21,43,60,52） D.(15,21,12,43,60,52) 三、简答题（三、简答题（30 分，每题分，每题 6 分）分） 1. 画出算术表达式(a+b)*(c-d)-(e/f+g)转换的二叉树。 2. 若通信系统中只可能出现 5 种字符 A、B、C、D 和 E，其概率分别为 0.12、0.15、0.19、0.21 和 0.33，（1）试设计赫夫曼编码；（2）画出相应的赫夫曼树。 3. 给出下图 G 的（1）邻接表表示图；（2）并根据画出的邻接表，以顶点 1 为根，画出深度优先生成树。 4. 输入一个正整数序列(45,14,11,52,63,32,56,24),（1）按此次序构造一颗二叉排序树；（2）如果删除 52，画出删除后的二叉树结构。 5. 堆排序的基本思想是什么？其优点是什么？ 四、算法题（四、算法题（15 分，共分，共 2 题）题） 1. 设计一个算法，逆序单链表中的数据。（5 分） 2. 采用二叉链表的存储结构，分别写出统计二叉树的叶子结点个数和树高的函数，并分别分析时间复杂度。（10 分）
