计算机软件技术基础(第三版)沈被娜-课后习题答案较全

1、第一章 信息与计算机 1.1 什么是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。 信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。 与数据的区别和联系： 数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。 我们把这些数据收集起来，经过处理后，即得到人们需要的信息。信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。 2. 信息是经过加工（处理）后的数据。 3. 信息是对决策有价值的数据。 1.2 信息有哪些基本属性？信息的基本属性有： 1. 事实性。 2. 等级性。 3. 可

2、压缩性。 4. 可扩散性。 5. 可传输性。 6. 共享性。 7. 增值性和再生性。 8. 转换性。 1.3 计算机的主要特点是什么？ 计算机最主要的特点是： 1. 高速自动的操作功能。 2. 具有记忆的能力。 3. 可以进行各种逻辑判断。 4. 精确高速的计算能力。 1.5 完整的计算机系统应该包括哪几部分？ 目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程 1.6 什么是计算机硬件？什么是计算机软件？ 硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。 微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。

3、 推荐精选 软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。 计算机软件一般分为系统软件和应用软件。 1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？ 第一阶段：高级语言阶段 特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要 目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。 硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。 第二阶段：结构程序设计阶段 特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性 提高了。 程序设计方法论方面，提

4、出由顶向下法和自底向上法。使程序模块 化，使问题的复杂性和人的思维统一起来了。 出现了软件生产管理。 硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完 善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。 第三阶段：自动程序设计阶段 特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法 进一步改进。 硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发 展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。推荐精选1.9 什么是多媒体计算机？ 多媒体计算机包含那几项？什么是多媒体计算机？1. “媒体”的概

5、念分为两部分，其一是信息存储的实体，其二是表现信息形式的载体；2. 多媒体计算机是以计算机为核心，可以综合处理数值计算、文本文件、图形图像、声音视频等多种信息的计算机系统。3. 多媒体是20世纪90年代计算机发展的新领域，它是计算机技术与图形图像、动画、声音和视频等领域顶尖技术结合的产物，它将人机交互的信息从单纯的视觉（文字、图形）扩大到两个以上的媒体信息B： 多媒体的基本要素： 文本，图形，图像，动画，音频，视频， 可以看出，它是电脑，电视机，游戏机，录放机，传真机和电话机的综合体第二章 常用数据结构及其运算2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间

6、存在的关系。 数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。推荐精选2.2 何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法。所以算法是程序的一个要素。2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。频度：在某个算法中某个语句

7、被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。2.4试编写一个求多项式Pn =anxn +an-1 xn-1+a1x+a0的值Pn(x0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。A=(a0, a1 an)mul 1 / sum=a0for i=1 to n推荐精选mul mul * x / xsum = Ai*mul + sum /求和end(i)进行了n次时间复杂度为：2n2.5计算下列各片段程序中XX+1执行

8、次数(1)for i=1 to n for j=1 to ifor k=1 to j xx+1end(k) end(j)end(i)执行次数：n*n*n (2)i1while in doxx+1ii+1end(while)执行次数：n-1推荐精选(3)for i=1 to nj1for k=j+1 to nx x+1end(k)end(i)执行次数：n*（n-1）2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元，其数据元素可以分散

9、存放在存储空间中，其元素关系由指针来指向。推荐精选2.8已知线性表L(a1, a2, , an ) 元素按递增有序排列。用向量作为存储结构，试编写算法：删除表中值在c与d之间(c=c / 找到第1个大于等于c的元素 s = i if t = -1 and Li d / 找到第1个大于d的元素 t = i ; end (i)if s != -1 and t !=-1 i = s while i t and i + t s =n Li = L i + t s i+end(while)else return(错误 没有找到 元素在c和d之间)end(if) for j=c to n-d+cLj-Lj

10、+d-c/把j+d-c项给jEnd(j)N-n-d+c/所有项数减少Return推荐精选2.9 线性表A，B中的元素为字符串类型，用向量结构存储，试编写算法，判断B是否为A的子序列（例如A=ENGLISH ，B=LIS ，则B为A的子序列）Am Bna1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A：b1b2b3b4b5b6B：i=1 检查A中第1个元素开始的字符串是否与B匹配i=2 检查A中第2个元素开始的字符串是否与B匹配 i= m n + 1 检查 A中 第(m-n+1)个元素开始的字符串是否与B匹配AmBnif ( mn ) then return error

11、for ( i =1; i= m-n+1; i+) for (j = 1; jn then return( A字符串中第i个字符开始的子串与B匹配 ) end(i)renturn (找不到匹配的子串)设A，B两个线性表的元素个数为m，nIf (m=n)thenreturnFor i=0 to n-1a=Aifor j=0 to m-1if(a=Bj)thenb+end(j)end(i)if(b=m)thenB 为A的子集return推荐精选2.11写一个将向量L（a1 ，a2， an）倒置的算法。a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15对L(a1，a2, .

12、., an )如果是奇数个元素，则1, 15 交换 1, n 交换2，14 交换 2, n-1 交换3，13 交换 3，n-2 交换 4，12 交换 4，n-3 交换5，11 交换 5，n-4 交换6，10 交换 6，n-5 交换7，9 交换 7，n-6 交换8，8 交换 8，n-7 交换9，7 交换 9，n-8 交换？ 停止！a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15如果是偶数个元素，则1，14 交换 1, n 交换2，13 交换 2, n-1 交换3，12 交换 3，n-2 交换4，11 交换 4，n-3 交换5，10 交换 5，n-4 交换6，9 交换 6

13、，n-5 交换7，8 交换 7，n-6 交换8，7 交换？ 8，n-7 交换？ 停止！小结：n个元素倒置的算法是，i = 1while ( in-i+1)ai 与 an-i+1 交换i+end(while) 推荐精选2.12试编写算法求已知单链表长度，并考虑表空的情况。p = headi = 0While(p!=nil) /表不为空P- next(p)/移动到下一个元素i+End(while)Return i /返回数据的个数2.13试编写算法删除单链表中第k个结点。GETNODE(q)GETNODE(p)q-headFor i=1 to k-1q-next(q)End(i)P-next(q)

14、;next(q)-next(p)Ret(p)Return推荐精选2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列GETNODE(p)Data(p)=aWhile(data(p)data(n)n-next(n)End(while) q -nnext(p) -next(q)-preturn2.18 设在长度大于1 的循环链表中，即无头结点，也无头指正，p为指向链表中每个节点的指针，试编写算法删除该节点的前趋结点。q-Next(p)/找到该节点的前趋结点p-next(q);next(q)-next(p)RET(p)Return2.20试

15、用单链表表示两个多项式；A=4x12+5x8+6x3+4，B=3x12+6x7+2x4+5(1) 设计此两个多项式的数据结构。(2) 写出两个多项式相加的算法。(3) 分析算法的时间、空间复杂度。ADD-POLY(ha ,hb )1. pnext(ha); qnext(hb)2. preha;hcha推荐精选 /pre指向p的前趋，为c(x)头指针/3.while (pnil) AND (qnil) do4.case5.EXP(p)EXP(q):6.prep;pnext(p)7.EXP(p)=EXP(q):8.xCOEF(p)+COEF(q);9.if (x0) then COEF(p)x;p

16、rep10.else next(pre)next(p); RET(p)11.pnext(pre);uq;qnext(q);RET(u)12.EXP(p)EXP(q):13.unext(q);next(q)p; next(pre)q;preq;qu14.end(case)15.end(while)16.if(qnil) then next(pre)q17.RET(hb)/释放多项式B(x)的头结点/18.return2.22 CQ0:10为一循环队列，初态 front=rear=1，画出下列操作后队的头，尾指示器状态：(1)d,e,b,g,h入队；rear=6 front=1(2)d，e出队 r

17、ear=6 front=3(3)I,j,k,l,m入队 rear=0 front=3(4)b出队 rear=0 front=4(5)n,o,p,q,r入队 rear=5 front=42.22 CQ0：10为一循环队列，初态front=rear=1，画出下列操作后队的头、尾指示器状态：(1) d,e,b,g,h入队；(2) d,e出队；(3) i,j,k,l,m,入队；(4) b出队；(5) n,o,p,q,r入队。2.23试画出表达式A*(B-D)/C*(E*F)执行过程中NS，OS栈的变化情况。推荐精选2.24用一长度为m的数组存放一双向栈，两个栈顶分别为top1和top2,如图所示。上溢

18、条件为top1=top2,从键盘输入一串整数，奇数入stack1，偶数如stack2，直到上溢时停止输入。试编写一算法实现此过程。 O_E(R,m,top1,top2,x)1. top1m;top21 /top1,top2置初值2. if (top1=top2) then 上溢,return 3. while (top1top2) do 4. if (x mod 2=0) thenRtop2x;top2top2+15. else Rtop1x;top1top1+16.end(while)7.retun2.25 有一个二维数组A1:m ;1:n,假设A3,2地址为1110，A2，3地址为1115

19、，若每个单元占一个空间，问A1,4的地址是多少答案：11202.26用三元组和带行辅助向量形式表示下列的稀疏矩阵：推荐精选2.28将题图2.3的一般树化为二叉树。答案：2.29 设一颗完全二叉数有1000个结点，试问：(1)有多少个叶子结点 500(2)有多少个度为2的结点 499(3) 有多少个结点只有非空左子树 12.30 设一颗二叉树其中序和后序遍历为中序：BDCEAFHG后序：DECBHGFA答案：ABCDEFHG231.对二叉树写出如下算法：(1)复制一棵二叉树；(2)判断两棵二叉树是否相等；(3)计算二叉树的树叶；推荐精选(4)计算二叉树的深度；解：1）/复制一棵二叉树/*算法思想

20、 采用递规函数来实现 （1）如果树为空，则复制一棵空树； （2）如果树不为空，则依次递规复制已知二叉树的左子树和有子树； （3）生成一个新的根结点，使复制得到的左子树和右子树的根指针分别成为这个新生成结点的左指针域和右指针域的值。 算法编写：*/BiTree *CopyTree(BiTree *T)/if(!T) return NULL;if(T-lchild)newlchild=CopyTree(T-lchild);/else newlchild=NULL;/if(T-rchild)newrchild=CopyTree(T-rchild);/else newrchild=NULL;/newn

21、ode=GetTreeNode(T-data,newlchild,newrchild); /return newnode;/CopyTreeBiTNode *GetTreeNode(TelemType item,BiTNode *lptr,BiTNode *rptr)/T=new BiTNode;T-data=item;T-lchild=lptr;T-rchild=rptr;return T;/GetTreeNode(2)在这里要对一种情况进行说明当root1的左子树与root2的左子树相同，root1的右子树与root2的右子树相同时，这两颗二叉树相同。当root1的左子树与root2的右子

22、树相同，root1的右子树与root2的左子树相同时，这两颗二叉树同样相同。推荐精选以下是实现代码boolIsBSTEqual(BNode*root1,BNode*root2)if(root1=NULL&root2=NULL)returntrue;elseif(root1=NULL|root2=NULL)returnfalse;elseif(root1-data!=root2-data)returnfalse;boolis_left=IsBSTEqual(root1-left,root2-left);boolis_right=IsBSTEqual(root1-right,root2-right

23、);if(is_left&is_right)returntrue;elseis_right=IsBSTEqual(root1-right,root2-left);is_left=IsBSTEqual(root1-left,root2-right);if(is_left&is_right)returntrue;elsereturnfalse;3）4）计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加1，空树返回-1.推荐精选struct TreeElementType Element;Tree

24、 *left;Tree *right;int CountLeaf(Tree *T)static int count = 0;if (T != NULL)CountLeaf(T-left);CountLeaf(T-right);if (T-left = NULL & T-right = NULL)count+;return count;int Depth(Tree *T)int depthLeft, depthRight, depth;if (T = NULL)return -1;elsedepthLeft = Depth(T-left);depthRight = Depth(T-right);

25、depth = 1 + (depthLeft depthRight ? depthLeft:depthRight);return depth;2.32.给定一组元素17,28,36,54,30,27,94,15,21,83,40,画出由此生成的二叉排序树。83283040219454361517解：推荐精选272.33给定一组权值W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树。2.34.有一图如题图2.4所示：（1）写出此图的邻接表与邻接矩阵；（2）由给点V1作深度优先搜索和广度优先搜索；（3）试说明上述搜索的用途。2101820191716151314121197846531推荐精

26、选解：（1）0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 01 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 00 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 01 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 00 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 1 0 1 0 0

27、 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 00 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 00 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 10 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 00 0 0 0 0

28、 0 0 0 0 0 0 0 0 0 1 0 1 0 0 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 00 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 00 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 8521103121224314534641515756171867157118181089推荐精选119210191210111311312201412131513414161461520171516181671719179

29、182018111919161320（2）V1作深度优先搜索:V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15V16V17V18V19V20 V1作广度优先搜索:V1V2V5V8V3V10V4V6V7V9V12V11V14V15V17V18V13V19V16V20(3)为了避免同一顶点被多次访问。2.35.有一又向图如题图2.5所示：5643推荐精选（1）写出每一结点的入度和出度各为多少；（2）写出上图的邻接矩阵和邻接表。解：V1:入度=3 出度=0V2:入度=2 出度=2V3:入度=1 出度=2V4:入度=2 出度=2V5:入度=2 出度=1V6:入度=0 出度=40

30、 0 0 0 0 01 0 0 1 0 00 1 0 0 0 10 0 1 0 1 01 0 0 0 0 01 1 0 1 1 0153123456142 45 21 63.36 求题图2.6中结点a到各结点之间最短路径。hfgedcba 2 2 2 2 1 2 3推荐精选 3 1 4 1解：ab:2ac:3abd:4abde:6abdef:7abdeg:8abdefh:82.37 求题图2.7中所示AOV网所有可能的拓扑顺序结果。 解: 21738546V1V2V3V4V5V6 0000013 8 68 4 8 V7 0V8 0 0 8 4 推荐精选拓扑排序：V7-V5-V2-V4-V6-V

31、3-V1-V82.38 题图2.8所示AOE网，求:(1).每一事件最早开始时间和最晚开始时间;(2).该计划最早完成时间为多少。解: 活动最早最迟开始时间a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最迟开始时间V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL096121923202325272.39某校97级同学举办运动会，报名同学学号为97438，97102，97528，97136，97338

32、，97250，97407，97239，97227，97517，97321，97421，97451，97241，97118，97543，97309画出进行分块查找的数据组织形式。2.40 画一棵对20个记录进行对分查找的判定树,并求等概率情况下的平均查找长度。ASL=(1+2*2+3*4+4*8+5*5)/20=3.72.41设有10个记录的关键字为ICKES，BARBER，ELYOT，KERN，FRENCE，LOWES，BENSDN，FONK，ERVIN，KNOX。构造=10/13的哈希表，取关键字首字母表中的序号为哈希函数值，用随机探测解决冲突，推荐精选di=(d1+Rj) mod 13，R

33、j取自伪随机数列：3，7，1，12，10，。统计该表的平均查找长度ASL。2.42对于给定的一组关键字：41,62,13,84,35,96,57,39,79,61,15,83。分别写出：插入排序、简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对各排序方法进行分析。排序，简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对排序方法进行分析。插入13 41 62 84 35, 96,57,39, 79,61,15,8313 35 41 62 84 96 57 39 79 61 15 8313 35 41 57 62 84 96 39 79 61 15 8313

34、35 39 41 57 62 84 96 79 61 15 8313 35 39 41 57 62 79 84 96 61 15 8313 35 39 41 57 61 62 79 84 96 15 8313 15 35 39 41 57 61 62 79 84 96 8313 15 35 39 41 57 61 62 79 83 84 96 对于具有n个记录的文件，要进行n-1趟排序就地排序稳定的排序方法简单选择排序41，62，13，84，35，96，57，39，79，61，15，8341 62 13 84 35 96 57 39 79 61 15 8313 41 62 84 35 96 5

35、7 39 79 61 15 8313 15 41 62 84 35 96 57 39 79 61 8313 15 35 41 62 84 96 57 39 79 61 8313 15 35 39 41 62 84 96 57 79 61 8313 15 35 39 41 57 62 84 96 79 61 8313 15 35 39 41 57 61 62 84 96 79 8313 15 35 39 41 57 61 62 79 84 96 8313 15 35 39 41 57 61 62 79 83 84 96堆排序41 62 13 84 35 96 57 39 79 61 15 83

36、96, 84, 83, 79, 62, 61, 57, 41, 39, 35, 15, 13推荐精选冒泡排序41，62，13，84，35，96，57，39，79，61，15，83 41, 13, 62, 35, 84, 57, 39, 79, 61, 15, 83, 96 13, 41, 35, 62, 57, 39, 79, 61, 15, 83, 84, 96 13, 35, 41, 57, 39, 62, 61, 15, 79, 83, 84, 96 13, 35, 41, 39, 57, 61, 15, 62, 79, 83, 84, 96 13, 35, 39, 41, 57, 15

37、, 61, 62, 79, 83, 84, 96 13, 35, 39, 41, 15, 57, 61, 62, 79, 83, 84, 96 13, 35, 39, 15, 41, 57, 61, 62, 79, 83, 84, 96 13, 35, 15, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83,

38、84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96快速排序41，62，13，84，35，96，57，39，79，61，15，83 13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 84, 62 13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41,

39、 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 62, 57, 83, 79, 61, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 83, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 8

40、3, 84, 96 二叉树排序 二叉树建立过程 41 41, 62 13, 41, 62 13, 41, 62, 84 13, 35, 41, 62, 84 13, 35, 41, 62, 84, 96 13, 35, 41, 57, 62, 84, 96 13, 35, 39, 41, 57, 62, 84, 96 13, 35, 39, 41, 57, 62, 79, 84, 96 13, 35, 39, 41, 57, 61, 62, 79, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 84, 96 13, 15, 35, 39, 41, 57,

41、 61, 62, 79, 83, 84, 96推荐精选第三章 操作系统3.1 操作系统的基本功能是什么？它包括哪些部分？ 基本功能： 操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。 构成部分： （1）. 对CPU的使用进行管理的进程调度程序 。 （2）. 对内存分配进行管理的内存管理程序。 （3）. 对输入输出设备进行管理的设备驱动程序。（4） . 对外存中信息进行管理的文件系统。3.2 试说明虚拟机的概念以及实现的方法。在裸机外面每增加一个软件层后就会变成一台功能更强的机器，我们通常把这种计算机系统称为虚拟机。

42、虚拟机的实现方法：在裸机上装上操作系统对机器进行首次扩展，再在操作系统的基础上增加其他软件，这样就可以实现“虚拟机”。3.3通常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？三大类：（1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中。（2）分时系统：多个用户通过终端分享同一台计算机，并通过终端直接控制程序运行，进行人与机器之间的交互。此类系统适用于程序的开发。（3）实时系统：对外部发生的随机事件作出及时的响应，并对它进行处理。此类系统一般用于工业控制系统或事物处理系统。3.4试

43、说明你所使用过的操作系统的类型和特点。Windows系统：多用户多任务操作系统。特点：全新的、友善的用户界面。 提供了功能强大的应用程序。 具有多任务并行处理能力，各种应用程序之间可以方便地进行切换和交换信息。推荐精选 具有强大的内存管理能力，支持扩展内存功能，提高系统运行效率。3.5 解释名空间、作业地址空间和存储空间的关系以及逻辑地址和物理地址的区别。存放源程序的空间称为名空间。当汇编或编译程序将源程序转换成目标程序后，一个目标程序所占有的地址范围称为地址空间，这些地址的编号是相对于起始地址而定的，一般定起始位零，称为逻辑地址或相对地址。存储空间是指当目标程序装入主存后占用的一系列物理单元

44、的集合，这些单元编号称为物理地址或绝对地址。3.6 什么是重定位？静态重定位和动态重定位的区别是什么？各举一例说明。当用户程序要调入内存时，必须把相对地址转换为绝对地址，同时要包括对程序中与地址有关的指令进行修改，这一过程称为重定位。静态重定位是在程序装入时进行，一般通过处理机中一对界地址寄存器来实现。动态重定位是在程序执行过程中进行的，当处理器访问主存指令时由动态变换机构自动进行地址转换。3.7 存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用

45、户在编制程序时可以不必考虑存储空间的限制。虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。3.10 什么是作业、作业步和进程？作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的集合。一个作业是由一系列有序的作业步所组成。一个作业步运行的结果产生下一个作业步所需的文件。进程可以看成是程序的一次执行，即是在指定内存区域的一组指令序列的执行过程。3.11 处理器管理主要解决什么问题？在大型通用系统中，可能数百个批处理作业存放在磁盘中，又有数百个终端用户与主机联接，如何从这些作业中挑选一些作业进入主存运行，又如何在主存各进程间分配处理器，是操作系统资源管理的一个重要问

46、题，处理器管理就是用来解决此问题的。3.12 什么是进程的同步和互斥？什么是临界区？ “同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。“互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。如果在两个进程P1、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P（s）、V（s）之间的程序段称为临界区。3.15 进程间的通信可以由哪些方式进行？低级通信方式：P-V操作。高级通信方式：直接通信、信箱通信。推荐精选3.16 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，