年中科院计算技术研究所计算机原理及系统结构试题 .pdfVIP

中国科学院－中国科学技术大学 2004 年招收攻读硕士学位研究生入学考试试题 第I 部分，40 分，请将所有答案写在答题纸上！！！ 一、本题20 分，每小题5 分： 1．请简述进程和线程之间的异同点。并至少分别给出两个以上的线程相对与进程的优点和 缺点。 2 ．请简述系统调用的过程，并指出在设计和实现系统调用时需要特别注意的问题。 3 ．请简述内部碎片和外部碎片的区别，并分别给出至少两种在操作系统中能遇到的实例情 况。 4 ．请以一种典型的操作系统为例，说明其中进程的动态优先级调度算法的设计方法。 二、本题10 分，每小题5 分： 1．请比较LRU 和LFU 之间的区别，在用于页面置换时各自需要哪些硬件和数据结构？； 2 ．假设在一个使用请求调页策略，包含三个空页框虚拟存储系统中，下列的页号依次被引 用：12132143112415621。请对于LRU 和CLOCK 置换算法，分别给出页框中的内容变 化以及出现的缺页次数。 三、本题10 分： 现有一个计算机存储系统需要涉及。下图给出了可选购的关键组件。 组件 延迟 最小大小 价格 TLB 10ns 16 个页表项 ￥20/项 内存 200ns 16MB ￥2/MB 磁盘 10ms 2GB ￥0.2/MB 经费预算为2000￥。假定：页大小固定为8KB；系统中需要同时运行4 －5 个应用程序，每 个程序最大大小为 64MB，工作集为 256KB ；TLB 中不包含进程标志符。请讨论以最高执 行性能为目标划分预算，如何选购组件。 第II 部分，30 分，请将所有答案写在答题纸上！！！ 四、简答题：（12 分） 1．如何区分存储于系统内存中的指令和数据？（2 分） 2 ．存储校验的功能是什么？常用的校验方法有哪些？它们各自的特点是什么？（2 分） 3 ．简要说明浮点数加减运算的步骤。（2 分） 4 ．描述利用中断和DMA 进行数据输入传输的过程，并比较二者的异同。（3 分） 5 ．分别描述立即寻址、寄存器寻址、寄存器间接寻址和寄存器相对寻址等4 种寻址方式从 形式地址到得操作数得寻址处理过程。（3 分） 五、综合题：（18 分） 1．解释内存储器容量扩展的基本原理，并画出示意图加以说明。（8 分） 2 ．CPU 结构如下图所示，其中包括累加器AC 、状态寄存器FR 、控制器以及其他4 个寄存 器（A 、B 、C 、D ）。各个部件之间的连线表示数据通路，箭头表示信息传输方向。（10 分） a ）指出A 、B 、C 、D 四个寄存器的名称和功能； b ）描述取指操作的数据通路； c ）描述完成指令LDA X 的数据通路（X 为内存地址，LDA 的功能为（X ）－ （AC ））； d ）描述完成指令ADD X 的数据通路（X 为内存地址，ADD 的功能为（AC ）＋（X ） － （AC ））。 第III 部分，共80 分，请将所有答案写在答题纸上！！！ 六、是非题，请在答题纸上回答“对”或“错”，共12 分： 1．用邻接矩阵作为图的存储结构时，所需存储空间的大小与图的结点数有关，而与边数无 关。 2 ．在一棵完全二叉树中，度为1 的结点数一定不超过1。 3 ．若某完全二叉树中，根的关键字为该树中各结点关键字的最大值，则该完全二叉树为一 个大根堆。 4 ．在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。 5 ．一棵树，若它的左、右子树都是AVL 树，则该树也是AVL 树。 6 ．所有时间复杂度为0 （n²）的简单排序算法（如简单插入排序、冒泡排序、简单选择排 序等）均是稳定的排序算法。 七、基本题，共48 分，6 小题，每题8 分： 1．在顺序表中插入或删除一个元素，所需的元素移动次数是否只与插入或删除的位置i 有 关？为什么？ （请回答，并用1 或2 句话简单叙述理由）。 2 ．若某个有向图的邻接矩阵为三角矩阵，该有向图是否一定具有拓扑有序序列？为什么？ （请回答，并用1 或2 句话简单叙述理由）。 3 ．含有12 个叶子结点的3 阶B-树中