中国科学院2004年计算机软件基础参考答案

由免费考研论坛志愿者夏枯草独家提供

中国科学院&中国科学技术大学

2004年硕士学位研究生入学考试试题参考答案

试题名称：                                            计算机软件基础
第1部分，40分，请将所以答案写在答题纸上！！

一、本题20分，每小题5分：
1、线程和进程都可以是操作系统的基本调度单位，线程又被称做是轻量进程。一个进程能够包含多个线程，这些线程共享进程的系统资源，如文件，内存映射等。（1分）线程的有点包括：调度单位小，系统资源占用少，提高了处理器的利用率，提高了程序的响应度，线程间通讯更容易（2分；缺点：需要附加的数据结构进行管理；若干系统调用（fork等）和信号的处理比进程更复杂（2分）。
2、软中断，系统陷入内核态。系统调用的处理在核心栈内进行，参数传递可使用寄存器或内存buffer。（3分）设计系统调用时需要特别注意canshu 安全性检查，避免用户传入非法的参数。（2分）
3、外部碎片通常指再也无法分配出去的较小的存储块；内部碎片指已被分配出去，但永远不会被使用的存储块。（1分）外部碎片：内存管理中的动态分区分配；文件分配中的连续分配.(2分)内部碎片：分页，每个进程会有page size/2大小的内部碎片；文件的多个逻辑块保存在已个磁盘块中也会产生内部碎片。（2分）
4、如以Linux为例，首先为进程赋静态优先级；然后每隔一段时间，按照某种标准对进程计数；最后在满足特定条件时，动态调整进程优先级。

二、本题10分，每小题5分:
l、LRU为最近再久算法，LFU为最不常用算法，即从程序运行开始被访问次数最少页面被置换。（2分）使用时需要的数据结构和硬件支持等不同，如LRU需要一个特殊的栈以及为每个页面设立移动寄存器；而LFU只需要为每页设置访问计数器。（3分）
2、

LRU，共11次缺页。

	1	2	1	3	2	1	4	3	1	1	2	4	1	5	6	2	1
0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	2
1		2	2	2	2	2	2	3	3	3	3	4	4	4	6	6	6
2				3	3	3	3	3	3	3	2	2	2	5	5	5	1
	Y	Y		Y			Y	Y			Y	Y		Y	Y	Y	Y

CLOCK,共9次缺页。

	1	2	1	3	2	1	4	3	1	1	2	4	1	5	6	2	1
0	1	1	1	1	1	1	4	4	4	4	4	4	4	5	5	5	5
1		2	2	2	2	2	2	2	1	1	1	1	1	1	6	6	6
2				3	3	3	3	3	3	3	2	2	2	2	2	2	1
	Y	Y		Y			Y		Y		Y			Y	Y		Y

三、本题10分

5个程序需要5*64M=320M磁盘空间。一个磁盘足够保存这些程序，共计0.3*2048=409.6Mb.还剩余2000-409.6=1590.4mb。将所有5个进程都保存在内存中本构省略交换的时间。于是需要320M的内存。需要320*2=640MB，还剩下1590.4-640=950.4MB。每个进程的工作集大小为246K。共计32个页面。因此TLB必须要能至少容纳32个项。从而避免TLB miss。如此需要32*20=640MB。最后剩余950.4-640=310.4，全部来购买TLB，310.4/20=15。


第2部分  编译原理，这个可以在陈意云个人网站上可以找到，在此不多说明

第3部分。数据结构

八.TTFFFF（T对，F错）
九1.答：不仅与插入或删除的位置i有关，而且与顺序表的长度有关。
2.答：是
3.答：至少有7个非叶子结点。
4.这段文字的2进制编码至少103个编码
5.最小生成树的边为：（1，3），（2，3），（2，4），（4，5），（2，7），（7，8），（5，6）。
6.该数的中序遍历序列为：10.12.15.17.18.19.24，树的根结点为18，左子树的根为12.右子树的根为24，12的左儿子为10，右儿子为17，24的左儿子为19，17的左儿子为15.

十、写算法
1.
用按层次遍历的方法，可以借用图的BFS算法，稍加改动即可。
2.
思想：第1步，先将n个元素进行两两比较，得到n/2个小元素和n/2个打元素，最多需要n/2次比较；第2步，分别在[n/2]个小元素中找最小值，在[n/2]个打元素中找最大值，共需要2（[n/2]-2）次比较；总共的比较次数小于3n/2。

很好，不错，顶啦

好！！！！！！！！！！！！1

楼主辛苦啦，非常感谢