Free考研资料

标题: 中国科学院2004年计算机软件基础参考答案 [打印本页]
作者: 范老师    时间: 08-1-28 17:22
标题: 中国科学院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。
作者: 王义炎    时间: 11-5-26 12:47
提示: 作者被禁止或删除 内容自动屏蔽
作者: 冉闵    时间: 12-3-7 11:34
提示: 作者被禁止或删除 内容自动屏蔽
作者: lijianhui1511    时间: 13-11-29 21:33
楼主辛苦啦，非常感谢



欢迎光临 Free考研资料 (http://bbs.freekaoyan.com/) Powered by Discuz! X3.2