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

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

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

3、.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块化，使问题的复杂性和人的思维统一起来了。出现了软件生产管理。硬件关系：磁盘问世，操作系统发展，非数值计算应用发

4、展，通信设备完善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。第三阶段：自动程序设计阶段特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法进一步改进。硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。1.9 什么是多媒体计算机？多媒体计算机包含那几项？什么是多媒体计算机？1 .“媒体”的概念分为两部分，其一是信息存储的实体，其二是表现信息形式的载体；2 .多媒体计算机是以计算机为核心，可以综合处理数值计算、文本文件、图形图像、声音视频等多种信息的计算机系统。3

5、 .多媒体是20世纪90年代计算机发展的新领域，它是计算机技术与图形图像、动画、声音和视频等领域顶尖技术结合的产物，它将人机交互的信息从单纯的视觉（文字、图形）扩大到两个以上的媒体信息B:多媒体的基本要素：文本，图形，图像，动画，音频，视频，可以看出，它是电脑，电视机，游戏机，录放机，传真机和电话机的综合体第二章常用数据结构及其运算2.1 什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。

6、它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2 何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：(1)对数据的描述，即数据结构。(2)对操作的描述，即算法。所以算法是程序的一个要素。2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。2.4

7、 试编写一个求多项式Pn=anxn+an-ixn-1+aix+a0的值Pn(x0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。A=(ao,aian)mul=1/sum=afori=1tonmul=mul*x/xsum=Ai*mul+sum/求和end(i)进行了n次时间复杂度为：2n2.5 计算下列各片段程序中号X+1执行次数(1)fori=1tonforj=1toifork=1tojxx+1end(k)end(j)end(i)执行次数：n*n*n(2)i1whilei<ndoxx+1ii+1end(while)执行次数：n-1fori=1tonj-

8、1fork=j+1tonxx+1end(k)end(i)执行次数：n*(n-1)2.6数据的存储结构主要有哪两种？它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，具存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。其数据元素可以分散存链式存储结果不需要一组连续的存储单元,放在存储空间中，其元素关系由指针来指向。2.8 已知线性表L(ai,a2,，an)元素按递增有序排列。用向量作为存储结构，试编写算法:删除表中值在c与d之间(c<=d)的元素大于等于cala2a3a4a5a6a7a8a9a10alla12a13a14a15找到第1个大于等于c的元

9、素，序号为s找到第一个大于d的元素，序号为tLs-LtLs+1Lt+1Ls+m-Lt+m/s+m=t-1m=t-s-1Ls+i-Lt+i/i=0tot-s-1i=1;/i从1循环到ns=-1;/第1个大于等于c的元素序号t=-1;/第1个大于d的元素序号fori=1tonstep-1ifs=-1andLi>=c/找到第1个大于等于c的元素s=iift=-1andLi>d/找到第1个大于d的元素l_t=i;endifs!=-1andt!=-1i=swhilei<tandi+t-s<=nLi=Li+t-si+end(while)elsereturn(错误没有找到元素在c和d

10、之间)end(if)forj=cton-d+cLj<-Lj+d-c/把j+d-c项给jEnd(j)N<-n-d+c/所有项数减少ReturnB是否为A2.9 线性表A,B中的元素为字符串类型，用向量结构存储，试编写算法，判断的子序列(例如A=ENGLISH,B=LIS,则B为A的子序列)AmBnA：B：ala2a3a4a5a6a7a8a9a10alla12a13a14a15blb2b3b4b5b6i=1检查A中第1个元素开始的字符串是否与B匹配i=2检查A中第2个元素开始的字符串是否与B匹配i=mn+1检查A中第(m-n+1)个元素开始的字符串是否与B匹配AmBnif(m<n

11、)thenreturnerrorfor(i=1;i<=m-n+1;i+)for(j=1;j<=n;j+)if(Ai+j-1!=Bj)break;:end(j)ifj>nthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A,B两个线性表的元素个数为m,nIf(m<=n)thenreturnFori=0ton-1a=Aiforj=0tom-1if(a=Bj)thenb+end(j)end(i)if(b=m)thenB为A的子集return2.11 写一个将向量L(ai,a2,an)倒置的算法。对L(ai,a?,an

12、)如果是奇数个元素，则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交换？停止！!ala2a3a4a5a6a7a8a9a10alla12a13a14a15如果是偶数个元素，则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,n-5交换7,8交换7,n-6交换8,7交换？8,n-7交换？停止小结：n个元素倒置的算法是,i=1while(

13、i<n-i+1)ai与an-i+1交换i+end(while)2.12 试编写算法求已知单链表长度，并考虑表空的情况。headp=headi=0While(p!=nil)/表不为空P<-next(p)/移动到下一个元素i+End(while)Returni/返回数据的个数2.13 试编写算法删除单链表中第k个结点。GETNODE(q)GETNODE(p)q<-headFori=1tok-1q<-next(q)End(i)P<-next(q);next(q)<-next(p)Ret(p)Return2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结

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试用单链表表示两个多项式；A=4x12+5x8+6x3+4,B=3x12+

15、6x7+2x4+5(1)设计此两个多项式的数据结构。(2)写出两个多项式相加的算法。(3)分析算法的时间、空间复杂度。ADD-POLY(ha,hb)1 .pnext(ha);qnext(hb)2 .preha；hcha/pre指向p的前趋，为c(x)头指针/3 .while(p<>nil)AND(q<>nil)do4 .case5 .EXP(p)<EXP(q):6 .pre-DP-next(p)7 .EXP(p尸EXP(q):8 .x-COEF(p)+COEF(q);9 .if(x<>0)thenCOEF(p)-x;prep10 .elsenext(p

16、re)-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)1.1 if(q<>nil)thennext(pre)-q17 .RET(hb)/释放多项式B(x)的头结点/18 .return2.22CQ0:10为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态：(1)d,e,b,g,h入队；rear=6front=1(2)d,e出队re

17、ar=6front=3(3)I,j,k,l,m入队rear=0front=3(4)b出队rear=0front=4(5)n,o,p,q,r入队rear=5front=4入队；（4）b出队;2.22CQ0:10为一循环队列，初态front=rear=1,画出下列操作后队的头、尾指示器状态：(1)d,e,b,g,h入队；(2)d,e出队；(3)i,j,k,l,m,(5)n,o,p,q,r入队。1O2.23试画出表达式A*(B-D)/C*(E*F)执行过程中NS,OS栈的变化情况。Tl-I3-L?13!-AFl2.24用一长度为m的数组存放一双向栈，两个栈顶分别为topi和top2,如图所示。上溢条

18、件为top1=top2,从键盘输入一串整数，奇数入stacki,偶数如stack2,直到上溢时停止输入。试编写一算法实现此过程。slacksstacki人_人、-bottom2top2topibottomlO_E(R,m,top1,top2,x)1. topim;top2-1/top1,top2置初值2. if(top1=top2)then上溢,return3. while(top1<>top2)do4. if(xmod2=0)thenRtop2x;top2-top2+15. elseRtop1x;top1-top1+16.end(while)7.retun2.25有一个二维数组A

19、1:m;1:n,假设A3,2地址为1110,A2,3地址为1115,若每个单元占一个空间，问A1,4的地址是多少答案：11202.26用三元组和带行辅助向量形式表示下列的稀疏矩阵：15OOO11OO;O门-i5OOO-1S(JO日15OOOD3OOOOO13OOOO口3OOOOO2<5nOoOOOOQOOOOO<>口OO2.O-1.3OOJOOC3OOOOOOGO_OO28口OOT-13ODOOOOO石ODO30-2.28 将题图2.3的一般树化为二叉树。答案：2.29 设一颗完全二叉数有1000个结点，试问:(1)有多少个叶子结点500(2)有多少个度为2的结点499(3)

20、有多少个结点只有非空左子树12.30 设一颗二叉树其中序和后序遍历为中序：BDCEAFHG后序：DECBHGFA答案：ABCDEFHGA2.31.对二叉树写出如下算法：(1)复制一棵二叉树；(2)判断两棵二叉树是否相等；(3)计算二叉树的树叶；(4)计算二叉树的深度；解：1) 复制一棵二叉树/*算法思想采用递规函数来实现(1)如果树为空，则复制一棵空树；(2)如果树不为空，则依次递规复制已知二叉树的左子树和有子树；(3)生成一个新的根结点，使复制得到的左子树和右子树的根指针分别成为这个新生成结点的左指针域和右指针域的值。算法编写：*/BiTree*CopyTree(BiTree*T)/if(!

21、T)returnNULL;if(T->lchild)newlchild=CopyTree(T->lchild);/elsenewlchild=NULL;/if(T->rchild)newrchild=CopyTree(T->rchild);/elsenewrchild=NULL;/newnode=GetTreeNode(T->data,newlchild,newrchild);/returnnewnode;/CopyTreeBiTNode*GetTreeNode(TelemTypeitem,BiTNode*lptr,BiTNode*rptr)/T=newBiTNo

22、de;T->data=item;T->lchild=lptr;T->rchild=rptr;returnT;/GetTreeNode(2)在这里要对一种情况进行说明当root1的左子树与root2的左子树相同，root1的右子树与root2的右子树相同时，这两颗二叉树相同。当root1的左子树与root2的右子树相同，root1的右子树与root2的左子树相同时，这两颗二叉树同样相同。以下是实现代码boolIsBSTEqual(BNode*root1,BNode*root2)if(root1=NULL&&root2=NULL)returntrue;elseif

23、(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);if(is_left&&is_right)returntrue;elseis_right=IsBSTEqual(root1->right,root2->left);is_left=

24、IsBSTEqual(root1->left,root2->right);if(is_left&&is_right)returntrue;elsereturnfalse;3)4)1,计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加空树返回-1.structTreeElementTypeElement;Tree*left;Tree*right;intCountLeaf(Tree*T)staticintcount=0;if(T!=NULL)CountLeaf(T-&

25、gt;left);CountLeaf(T->right);if(T->left=NULL&&T->right=NULL)count+;returncount;intDepth(Tree*T)intdepthLeft,depthRight,depth;if(T=NULL)return-1;elsedepthLeft=Depth(T->left);depthRight=Depth(T->right);depth=1+(depthLeft>depthRight?depthLeft:depthRight);)returndepth;)2.32.给定一

26、组元素亿28,36,54,30,27,94,15,21,83,40,画出由此生成的二叉排序树。解：(1)写出此图的邻接表与邻接矩阵；(2)由给点V1作深度优先搜索和广度优先搜索;(3)试说明上述搜索的用途。G1001001000000000000、TOIOOOGOOTOOOOOOOOOOOTOTOOOOOOOIOOOOOOOOOOIDTOODOOGOTOODOOOOTOOTOIOOOOOOOOODOOOOOOOOTOIOOOOOOOIOOOGOOOOOOTOTOOOOOOOOTOOOTOOGOOTOTOOOOOOOOOOOOOOOOOOTOTOOOOOOOIDOOTOOOOOOTOTOOOOO

27、OOOO00000000010100000010OOIOOOOOOOIOTOOOOOOOOOOOOOOOOOOIOIOOODOIOOOTOOOOOOOOTOIOOOOOOOOOOTOOOOOOOTOIODOOOOOOOOOOOOOOOOIOTOOTOOOOOOTOQOOOOCOTOIOOOOOOOOOOTOOOOOQOTOIO00000000001000000101VooooooooooooTooiooio/:搦125_48A'L.21310A,-34212A,443>514A.1.514t6A,p-657>15A-W768M17AL.8117d15ALAF981018A1

28、0、2911Ar.A11>10P1219AA1231113A.13_一1214一20A1441315A=IF八1546一»1416AA16J151720A.A177-to16h18A.18491719AhA191118工20AP201316>19-A.A(2)V1作深度优先搜索*/ThT/T%V1作广度优先搜索：匕T%T%T%T%T%nT%T/T%TKT%*T4iT«uT%5T%T%'f%TLT%T%(3)为了避免同一顶点被多次访问。2.35.有一又向图如题图2.5所示：(1)写出每一结点的入度和出度各为多少;(2)写出上图的邻接矩阵和邻接表。解：V1:

29、入度=3出度=0V2:入度=2出度=2V3:入度=1出度=2V4:入度=2出度=2V5:入度=2出度=1V6:入度=0出度=40000001100100010Q01001010100000L110110J3.36求题图2.6中结点a到各结点之间最短路径。a-*b:2a->c：3abd：4m7fd一%6"b->d->e-*g：82.37求题图2.7中所示AOV网所有可能的拓扑顺序结果。解：拓扑排序：V7->V5->V2->V4->V6->V3->V1->V82.38题图2.8所示AOE网，求：(1).每一事件最早开始时间和最晚

30、开始时间；(2).该计划最早完成时间为多少。解：活动最早最迟开始时间ala2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最迟开始时间V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL096121923202325272.39某校97级同学举办运动会，报名同学学号为97438,97102,97528,97136,97338,97250,97407,97239,9722797517,97321,97421,97

31、451,97241,97118,97543,97309画出进行分块查找的数据组织形式。2.40画一棵对20个记录进行对分查找的判定树，并求等概率情况下的平均查找长度。Q-THTE.071367229-724107433O7S177343第1陕搞2供9k43索引我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)mod13,Rj取自伪

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

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

34、96183131535416284965739796183131535394162849657796183131535394157628496796183131535394157616284967983131535394157616279849683131535394157616279838496堆排序41621384359657397961158396,84,83,79,62,61,57,41,39,35,15,13冒泡排序41,62,13,84,35,41,13,62,35,84,57,39,79,61,15,13,41,35,62,57,39,79,61,15,83,13,35,41,5

35、7,39,62,61,15,79,83,13,35,41,39,57,61,15,62,79,83,13,35,39,41,57,15,61,62,79,83,13,35,39,41,15,57,61,62,79,83,13,35,39,15,41,57,61,62,79,83,13,35,15,39,41,57,61,62,79,83,13,15,35,39,41,57,61,62,79,83,13,15,35,39,41,57,61,62,79,83,13,15,35,39,41,57,61,62,79,83,13,15,35,39,41,57,61,62,79,83,快速排序41,62,

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

37、62,79,84,13,15,35,39,41,57,61,62,79,83,二叉树排序二叉树建立过程4141,6213,41,6213,41,62,8413,35,41,62,8413,35,41,62,84,9613,35,41,57,62,84,9613,35,39,41,57,62,84,969657397961158383,9684,9684,9684,9684,9684,9684,9684,9684,9684,9684,9684,969657397961158384,6284,6284,6284,6284,6284,9683,9683,9683,9683,9684,9613,35,

38、39,41,57,62,79,84,9613,35,39,41,57,61,62,79,84,9613,15,35,39,41,57,61,62,79,84,9613,15,35,39,41,57,61,62,79,83,84,96持序方法最好时间平均时间最坏时间辅助空间稳定性直接插入0(n)0(n2)0(n3)0(1)稳定二分插入。O(n2)O(n?)0(1)不稳定希尔0(n1J5)0(1)冒泡。8）0(n2)0(n2)0(1)稳定快速0Mgn)0(nlgn)0(n2)。面）不稳定直接选择0(n2)0(n3)0(n2)0(1)不稳定堆0(nlgn)。（喙n）0(nlgn)不稳定归并0(nlg

39、n)0(nlgn)0(nlgn)0(n)稳定基数0(d(rd+n)0(d(rd+n)0(d(rd+n)0(rd+n)稳定第三章操作系统3.1操作系统的基本功能是什么？它包括哪些部分？基本功能：操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。构成部分：（1）.对CPU的使用进行管理的进程调度程序。（2） .对内存分配进行管理的内存管理程序。（3） .对输入输出设备进行管理的设备驱动程序。（4） .对外存中信息进行管理的文件系统。3.2 试说明虚拟机的概念以及实现的方法。在裸机外面每增加一个软件层后就会变成一台功能更强的

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

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

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

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

44、作系统资源管理的一个重要问题，处理器管理就是用来解决此问题的。3.12 什么是进程的同步和互斥？什么是临界区？同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。如果在两个进程Pi、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P(s)、V(s)之间的程序段称为临界区。3.15 进程间的通信可以由哪些方式进行？低级通信方式：P-V操作。高级通信方式：直接通信、信箱通信

45、。3.16 死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，继续占用已分配到的资源；3.一个进程占有的资源不能被别的进程强行抢占；4.一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。死锁的预防是研究如何破坏产生死锁的必要条件之一，从而达到不使死锁发生地目的。死锁的避免与死锁的预防区别在于，死锁的预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。而死锁的避免并不严格限制必要条件的存在，因为必要条件存

46、在并不一定产生死锁。而进程推进顺序不当，也可以导致系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法进行恢复。利用化简进程-资源有向图的方法来检测系统在某一特定状态时是否处于死锁状态。3.17 通道、控制器和设备的各种不同连接方式各有什么特点？第一种连接方式(书中图3.41(a):控制器与设备是一一对应的，当系统对某设备提出申请时，CPU将设备号及有关操作要求传递给通道，由通道启动该设备，并完成对该设备的操作。第二种连接方式(书中图3

47、.41(b):是一个控制器控制若干个设备，只有当被申请的设备及相应的控制器均为空闲状态时才能启动。第三种连接方式(书中图3.41(c):是同道、控制器与设备交叉连接，提高了控制的灵活性，但必须在相应的设备、控制器、同道均为空闲时才能工作。3.18 什么是瓶颈”问题？引入缓冲区为何可以解决这一问题？系统中的独占类型设备，只能由单个作业独占，这样使其他需要改设备的进程由于等待设备而被阻塞，称为系统的瓶颈缓冲技术是指在内存中划出一个由n个单元组成的区域，称为缓冲区，作为外部设备在进行数据传输时的暂存区。引入缓冲技术的根本原因是CPU数据处理速度与设备传输数据速度不相匹配，利用缓冲区来缓解其间的速度矛

48、盾，减少瓶颈现象。3.19 设备管理的功能是什么？怎样把一台物理设备虚拟为多台设备？设备管理的功能：设备驱动程序；即插即用；通用即插即用；集中、同一管理；添加硬件。通过虚拟机软件，就可以在一台物理计算机上模拟出一台或多台虚拟的计算机。3.20 什么是记录、文件、文件系统？记录：文件由若干个记录组成，每一个记录是一些相关信息的集合。文件：在逻辑上具有完整意义的数据或字符序列的集合。文件系统：负责存取和管理文件的机构，又称为文件管理系统。3.21 文件的逻辑结构和物理结构有何区别？文件的存储方式与文件的存取有何关系？文件的逻辑结构是从用户的角度看到的文件面貌，也就是它的记录结构。文件的物理结构是指

49、一个逻辑文件在外存储器上的存放形式。各种文件应用场合不同，对文件的存取要求也就不同，对应不同的存取方式，对文件的物理结构即存储方式有不同的要求3.22 什么是文件目录？有几种目录结构形式？各有什么特点？为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。通常有一级目录、二级目录和多级目录结构。一级目录：把系统中所有文件都建立在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各

50、用户文件目录才指出其所属各具体文件的描述信息，不同用户的文件可以起相同的名字。多级目录：是树形结构，每一个结点出来的分支可以是文件，也可以是下一级，在一定时间内以某一级目录作为当前目录，用户只需从当前目录”查看即可。3.23 文件的共享与安全保密问题如何解决？共享的实现：通过文件路径实现共享；通过联接实现共享。保密问题的解决：采用存取控制矩阵方法；采用按用户分类的存取控制的方法；采用口令设置。3.24 什么是文件操作指令？每个命令的具体功能是什么？文件操作指令：是指文件系统提供给用户的一系列操作使用命令，其中最基本的命令是查询文件目录。建立文件：当用户需要将其信息作为文件保存时，向系统提出建立

51、文件指令，系统按照用户提供的参数为该文件建立一个表目，放入相应的文件目录中。打开文件：当用户需要访问文件中某个记录时，首先要进行打开文件操作，此时系统将欲访问的文件表目从目录文件调入活动文件表中。读文件：把文件中相关的记录从外存储器的文件区中读入主存用户工作区中。写文件：把用户要求插入、增加或删除的记录写入文件区相应位置。关闭文件：文件暂时不用时，必须将它3.253.26操作系统与用户的接口有几种？各有什么特点？试举例说明你所使用过的接口形式。通常操作系统为用户提供两种接口：一类是程序接口；另一类是作业控制方面的接口。程序一级接口是由一组系统调用命令组成，它是操作系统提供给用户的各种服务，以子程序的形式供用户在程