计算机软件基础(二)习题答案

《计算机软件基础（二）》习题解答第1章概论复习题答案.怎样的计算机被称为裸机？什么是虚拟计算机？【解答】：对于一台只有硬件构成（通常包括：中央处理器cpu,储存器，输入和输出设备），而没有安装任何软件的计算机被称为裸机。而虚拟计算机则是指以硬件为物质基础，加装软件后的扩充后的计算机系统。.计算机软件资源的作用如何？在你使用的计算机上有那些软件资源？【解答工计算机软件资源的作用是只有在软件资源的支持下，用户所使用的计算机才能极大程度上满足用户需要的虚拟计算机。软件资源有：汇编程序；各种高级语言；各种语言的解释或编译程序；各种标准程序库；操作系统：数据库系统软件：计算机网络软件；各种应用软件等。.汇编语言和高级语言有什么不同？【解答】：汇编语言是面向机器的语言，即不同型号的计算机的汇编语言是各不相同的，进行程序设计时必须了解所使用的计算机的结构性能和指令系统，而且编好的程序也只是针对一类机器，不能通用。高级语言是面对过程的语言，用户不必了解具体机器的细节就能编写程序，方便了程序的设计，提高了效率，同时也便于人们的交流。.我们知道计算机只能执行机器指令，为什么它能运行汇编语言和高级语言编写的程序？【解答】：计算机之所以能运行汇编语言编写的程序是因为计算机系统中装有汇编程序,汇编程序的作用是将源程序翻译成用机器语言组成的目标程序，从而计算机能运行汇编语言编写的程序。计算机之所以能运行高级语言编写的程序是因为计算机系统中装有解释程序或编译程序，它们将用高级语言编写的程序翻译成用机器语言组成的目标程序，从而计算机能运行高级语言编写的程序。.你学习过那些高级语言?试分析它们的特点和适用的范围？（解答】:fortran语言主要用于科学和工程计算;pascal语言则具有良好的程序结构,cobol语言则是面向事务处理的；lisp语言是人工智能语言；c语言则是通用的程序设计语言；C++语言是面向对象的程序设计语言。.计算机软件的定义是什么？【解答】：计算机软件是指：计算机程序，实现程序功能所采用的方法，规则以及相关联的文档和在机器上运行它所需要的数据。.操作系统的作用是什么？【解答】：操作系统控制和管理计算机的硬件、软件资源，实现对处理机，存储器，I/O设备，文件等四类资源的管理，同时操作系统还作为用户和计算机系统之间的接口，方便了人机交互。.计算机操作系统在发展中经历了那些阶段？试简述它们的特点？【解答】：主要经历了：手工操作阶段、成批处理系统阶段、执行程序阶段、多道程序系统和分时系统阶段。手工操作阶段的特点：计算机的全部资源归一个用户的一个程序独占操作过程有人工来干预。成批处理系统阶段：相对于手工操作阶段，它提高了计算机资源的利用率和增强了系统的处理能力，但由于处理机和I/O设备是串行工作的，大部分时间被消耗在输入输出上，处理机的大部分时间处于等待状态，故处理机和I/O设备的速度不匹配的矛盾成为进一步提高计算机的效率的关键。执行程序阶段：使系统实现了模块化结构，易于设计、修改和扩充，但由于计算机本身的顺序性，计算机并不能完全消除对外设传输的等待。多道程序系统：它需要一个调度算法来解决cpu的分配问题，需要有一个储存管理程序来解决多道程序在内存中的定位，分配和免遭破坏，需耍有一个设备管理程序来解决外设的分配，释放和信息交换，此外还需要有一个文件管理程序来解决以文件形式存放于外存中的程序和数据。分时系统阶段：分时系统阶段采用划分时间片的方法来接受和处理各个用户从终端输入的命令，由于计算机运行的高速性和并行性，使每个用户感觉不到别的用户的存在，好像独占整台机器。.计算机应用软件有那些？【解答】：主要有以下三大领域：事务处理软件，工程和科学计算软件，实时应用软件。随着计算机技术的发展一些新的领域异军突起，如：嵌入式应用软件，微型机工具软件,人工智能软件。第2章数据结构复习题答案一、选择题.线性表L在情况下适用于使用链式结构实现。(A)：需经常修改L中的结点值；(B)：需不断对L进行删除和插入；(C)：L中含有大量的结点； (D)：L中结点结构复杂；【答案】：应选B..线性表在采用链表存储时其地址。(A)：必须是连续的； (B)：部分地址是连续的；(C)：一定不是连续的；(D)：连续不连续都可以；【答案］应选D..数组Q［n］用来表示一个循环队列，f为当前队列头元素的前一个位置，r为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素的公式为。(A)：r-f；(B)： (n+f-r)%n；(C)：n+r-f；(D)：(n+r-f)%n；【答案】：应选D..若入栈序列为1,2,3,4,在入栈的过程中允许出栈，则不可能是一个出栈序列。(A)：1,4,3,2； (B)：2,3,4,1；(C)：3,1,4,2；(D)：3,4,2,1；【答案】：应选C..一个二维数组M,行下标的范围是1到8,列下标的范围是。到9,每个数组元素用相邻的5个字节存储，存储器按字节编址，设存储数组元素M(l,0)的第一个字节的地址是98,且按列存储，则M(3,7)的第一个字节的地址是。(A)：135； (B)：233； (C)：290； (D)：388；【答案】：应选D。.由3个结点所构成的二叉树有种形态，由3个结点构成的树有种形态。(A)：3； (B)：4:(C)：5； (D)：6；【答案】：应选C和A；.不含任何结点的空树。(A)：是一棵树；(B)：是一棵二叉树；(C)：是一棵树也是一棵二叉树；(D)：既不是一棵树也不是一棵二叉树；【答案】:应选B。.一棵深度为k的满二叉树中结点的个数是。(A)：2-1；(B)：2k；(C)：2kZ(D)：2k+,；【答案】:应选A..一棵具有257个结点的完全二叉树，它的深度为。(A)：8：(B)：9；(C)：7； (D)：10；【答案】：应选B..二叉树是非线性数据结构，所以。(A)：它不能用顺序存储结构存储；(B)：它不能用链式存储结构存储；(C)：用顺序存储结构和链式存储结构都能存储；(D)：顺序存储结构和链式存储结构都不能存储；【答案］应选C..把一棵树转换为二叉树后，这棵二叉树的形态是。(A)：唯一的； (B)：有多种；(C)：有多种，但根结点都没有左孩子；(D)：有多种，但根结点都没有右孩子;【答案】：应选A..在表长为n的链表中进行线性查找，它的平均查找长度为o(A)：ASL=n: (B)：ASL=(n+l)/2；(C)：ASL3W+1 ；(D)：ASL=log2(n+l)-l；【答案】：应选B.二、填空题.数据的基本单位是,它可以由组成。【答案】：数据元素；数据项。.把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是【答案金顺序存储结构。.顺序表结构适宜于进行存取；链表适宜于进行存取。【答案】：随机存取：顺序存取。.栈是一种特殊的线性表，允许插入和删除运算的一端为，不允许插入和删除运算的一端为。【答案】：栈顶；栈底。.是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。【答案】：队列。.三元组表中的每个结点对应与稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的，和。【答案】：行下标；列下标；元素值。.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层最多能有个结点。【答案】：.把一棵树转化为二叉树以后，这棵二叉树的根结点没有o【答案】：右子树。.在数据的存放无规律而言的线性表中进行检索的最佳方法是。【答案】：线性检索。.有一个表长为m的散列表，初始状态为空，现将n(n<m)个不同的关键码插入到散列表中，解决冲突的方法是线性探测法，如果这n个关键码的散列地址都相同，则探测的总次数是。【答案】：1+2+3+……+n=n(n+l)/2..线性有序表(ai,a”a3, ,a256)是从小到大排列的，对一个给定的值k,用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。【答案】：9.三、判断下列概念的正确性，并做出简要的说明。.线性表在物理存储空间中也一定是连续的。【答案】：错误。线性表的存储方式分两种，顺序存储和链式存储。顺序存储的物理空间是连续的，但链式存储的物理空间可以不连续。.栈和队列是一种非线性数据结构。【答案】：错误。栈和对列均为操作上受限制的线性表。.链表的物理存储结构具有同链表一样的顺序。【答案】：错误。链表的物理存储空间是任意的。.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。【答案】：错误。计算机不会自动地将后续的各个单元向前移动，当删除链表中某个结点时「需要用语句来修改相应的指针。.栈和链表是两种不同的数据结构。【答案】：错误。栈和链表是两个不同的概念，栈表示后进先出的线性表，它可以用顺序表来存储，也可以用链表来存储。而链表是一种物理存储方法。.一个矩阵也是一个线性表。【答案】：正确。矩阵是数据元素为线性表的线性表。.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。【答案】：错误。线性表的每个结点可以是简单类型，也可以是一个复杂类型。而链表的每个结点因为是结构类型，所以它是一个复杂类型。.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表.【答案】：正确。.在表结构中最常用的是线性表，栈和队列不太常用。【答案】：错误。线性表、栈和队列都是最常用的线性结构。四、问答题.试比较顺序存储结构和链式存储结构的优缺点。【答案】：顺序存储结构的优点是：能实现随机存取；存储密度大，存储空间利用率高。缺点是：插入元素时会有表溢出的情况：在插入和删除元素时将要引起大量元素的移动。链式存储结构的优点是：插入元素时不会有表溢出的情况；在插入和删除元素时不需要移动任何元素，只需改变指针域中的指针值就可以了。缺点是：只能实现顺序存取：存储密度小，存储空间利用率不高。.写出一个计算单链表中结点个数的算法，其中指针p指向该链表的第一个结点。【分析】：根据单链表的特性，从单链表第一个结点开始计数，只要是非空结点，计数器加1,直到所有结点都走过一遍。【答案】：typedefstructsnode{chardata；structsnode*link；}NODE；intlength(NODE*p){NODE*q；inti；q=p；i=0;/*初始化♦/while(q!=NULL){i++；q=q->link；}return(i)；.给定一个n项元素的线性表V,写一个算法，将元素排列的次序颠倒过来，要求仍占用原来的空间，并且用顺序表和单链表两种方法表示。【分析】：将V[l]与V[n]交换，V[2]与V[nT]交换，……,V[n/2]与V[n/2+l]交换.【答案】：顺序表结构下的实现：#defineM1000intv[M]；intn；voidinvert(){inttemp；for(i=0；i<=n/2；i++){temp=v[i]；v[i]=v[n-i-l]；v[n-i_l]=teinp；}【分析】：依次从原单链衣的头部删除一个结点，在插入到另一个从空链表开始的单链表的头部。【答案】：单链表结构下的实现：typedefstructsnode{chardata；structsnode*link；}NODE；voidinvert(NODE*head){NODE*p,*u；p=NULL;while(head!=NULL){u=head；/*在头部删除一个结点*/head=head->link；u->link=p；/*将删除的结点插入到另一个链表中*/P=u；}head=p；/*新链表的头指针*/.试设计实现在单链表中删除值相同的多余结点的算法。【答案】：typedefstructsnode{chardata；structsnode*link；}NODE；voidpurge」klist(NODE*head){NODE*p,*q,*r；p=head->link；/*p指向当前检查结点的位置，先将其初始化*/if(p==NULL)return；/♦空表返回*/while(p->linkt!=NULL){/*当前结点不是尾结点*/q二P；while(q->link!=NULL)/*删除值与p所指结点的值相同的结点*/if(q->link->data==p->data){/*若有值相同的结点*q*/r=q->link；q->link=q->link->link；/*删除多余结点*/free(r)； }elseq=q->link；/*找下一个可以的多余结点♦/p=p->link；}/*更新检查结点*/.描述以下三个概念的区别：头指针、头结点、首元元素结点。【答案】：头指针：是指向单链表的第一个结点的指针。头结点：在链表的首元元素结点之前附设的一个结点。首元元素结点：是指用于存储线性表中第一个数据的结点。.写出计算线性链表长度的算法。【分析】：：根据单链表的特性，从单链表第一个结点开始访问，只要是非空结点，计数一次，直到所有结点访问一遍。【答案】：typedefstructsnode{chardata；structsnode*1ink；}NODE；intlength(NODE*head){NODE*p；inti；p=head；i=0；/*初始化*/while(p!=NULL){i++；p=p->link；}return(i)；}.设有一个线性链表，其结点为正整数，且按值从小到大链接。试写出一个算法，将此线性链表分解成两个线性链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。【分析】：在链表head中依次取元素(s->data),若取出的元素是奇数，把它插入到奇数链表ahead中，若取出的元素是偶数，把它插入到偶数链表bhead中，继续取下一个元素，直到链表的尾部，头指针ahead和bhead分别指向奇数链表和偶数链表。【答案】：typedefstructsnode{intdata；structsnode*1ink；}NODE；voidexamp7(NODE*head,*ahead,*bhead){NODE*p,*q,*s；ahead=(NODE*)malloc(sizeof(NODE))；/*建立奇数链表的头结点*/p二ahead；, /*工作指针p初始化。*/bhead=(NODE*)malloc(sizeof(NODE))；/*建立偶数链表的头结点*/q=bhead； /*工作指针q初始化。*/s=head->link；free(head)；/*s为原表中的工作指针，释放原表中的头结点*/while(s!=NULL){if(s->data%2==0)/*是偶数*/{q->link=s；q=q->link；}else /*是奇数*/{p->link=s；p=p->link；)s=s->link； /*取下一个结点*/}p->link=NULL；/*置奇数表的表尾*/q->link=NULL；/*置偶数表的表尾*/.假设有一个循环单链表的长度大于1,且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除S指针所指结点的前驱结点。【分析】：：设置一个指针p,指向S结点的前驱结点的前驱结点。【答案】：typedefstructsnode{chardata；structsnode*link；}NODE；NODE*s；voiddeleteprior()(NODE*p,*q；p=s；while(p->1ink->1ink!=s)p=p->link；/*让p指向s结点的前驱结点的前驱结点*/q=p->link；/*q指向被删除结点*/p->link=q->link；/*删除*/free(q)；).已知指针ha和hb分别指向两个单链表的头结点，且头结点的数据域中存放链表的长度,试写出一个算法将这两个链表连接在一起，并要求算法以尽可能短的时间内完成运算。【分析】:：令表hb的首元结点连在表ha中的最后一个结点之后，首先想将工作指针p从ha的首元结点开始遍历到表ha中的最后一个结点，he指向连接后的链表的头结点。【答案】：typedefstructsnode{chardata；structsnode*link；}NODE；NODE*ha,*hb,*hc；voidexample9(){NODE*p；inti；he=ha； /*he指向连接后的链表的头结点*/p=ha->link；i=l;/*用于表ha中结点的计数器*/while(i<ha->data)p=p->link；/*ha->data是表ha的长度*/p->link=hb->link；/*连接表hb的首元结点*/hc->data=ha->data+hb->data；/*连接后的链表的长度*/.对于下面的每一步，画出栈元素和栈顶指针示意图。(1)栈空；(2)在栈中入栈一个元素A；(3)在栈中入栈一个元素B；(4)出栈中一个元素；(5)在栈中入栈一个元素C；.设有编号为1,2,3,4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。【答案】：1,2,3,4；1,2,4,3；1,3,1,4；1,3,4,2；1,4,3,2；2,1,3,4；2,1,3,3；2,3,1,4；2,3,4,1;2,4,3,1;3,2,1,4；3,2,4,1；3,4,2,1；4,3,2,1;12.说明栈和队列的异同点。【答案】：相同点：栈和队列都是线性表结构；不同点：栈是限定在线性表的一端进行插入和删除的操作；而队列的插入和删除在线性表的两端进行；.顺序队的“假溢出”是怎样产生的？如何知道循环队是空还是满？【答案】：队列的尾指针已经到了数组的上界，此时如果还要执行入队运算，就要发生“上溢”，但是数组中还有空位置，这种现象称为“假溢出二在循环队中，当rear==front时，表示队空；当(rear+l)%M=二front时，表示队满。.设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后，有(1)front=11,rear=19；(2)front=19,rear=11；问在这两种情况下，循环队列中的各有多少个元素？【答案工(1)：8个； (2)：32；.假设一数组squ[m]存放循环队列的元素。若要使m个分量都得到利用，则需要另一个标志tag,以tag为0或1来区分队尾指针和队头指针值相同时队列的状态是“空”还是“满二试编写与此结构相应的入队和出队的算法。【答案】：^defineM100intsqu[M],front,rear,tag；/*队列中加一个标志域tag*/intaddque(intx){/*入队运算*/if((tag==l)&&(front==rear)){printf(wfullqueuer!\nw)；return(-1)； }else{rear=(rear+l)%M；squ[rear]=x；if(rear==front)tag=l；/*如果插入后队列满，则置标志*/intdelque(){/*出队运算*/if(tag==0)&&(front二二rear)){printf("emptyqueuer!\n")；return(-1)；}else{front=(front+1}%M；if(front==rear)tag=0；/*如果删除后队列空,则置标志*/return(squ[front])；).假设以带头结点的循环单链表表示队列，并且只设一个指针指向队尾元素结点，不设头指针，试编写相应的入队和出队算法。【答案】：typedefstructsnode{intdata；structsnode*link；}NODE；NODE*rear；/*定义结点的类型和指向队尾的指针*/voidaddqueue(intx){NODE*p；p=(NODE*)malloc(sizeof(NODE))；/*申请结点空间*/p->data=x；p->link=rear->next；rear->next=p；/*在队尾插入结点*/rear=p；/*修改队尾指针*/)intdelequeue(){ /*从链队中出列，返回出队的数据元素*/NODE*p；if(rear->link==rear){printf(aqueueisempty!\nw)；return(-1)； )else{p=rear->link；/*p指向头结点*/q=p->link；/*q指向被删除结点*/if(q==rear)rear=p； /*队列中仅有一个结点时，先修改尾指针*/p->1ink=q->link；x=q->data；free(q)；return(x)；/*删除结点并返回*/17.已知二维数组上.■采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为LOC(au),请写出LOC(au)的计算公式。如果采用列优先顺序存放呢？【答案】：按行优先顺序存放：L0C(aij)=L0C(a”)+((iT)*m+(j-l))*K；按列优先顺序存放：LOC(aij)=L0C(au)+((jT)*m+(i-l))*K；18.用三元组表表示下列稀疏矩阵:r0000000八0000-2>0000000000009003000800000000⑴400000000⑵00500000060000r000000000000000003000000005120000000J【答案】： (1) (2)行下标列下标元素值TOC\o"1-5"\h\z6 6 41 6 -22 5 94 3 56 5 3

行下标列下标元素值88532336854678581219.5列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。rr64611221312⑴〈313444536<61「4 5 5、1 1 1(2)I2 4 9j3 2 83 5 6\o"CurrentDocument"<4 3 7 ,0 00 0 0 0 、0 0 9 08 0 0 60 7 0 0【答案】：TOC\o"1-5"\h\z< 0 2 120 0 0⑴J 3 0 0I 0 0 00 0 6I 16 0 0.什么样的二叉树不是树？一棵度为2的树与一棵二叉树有何区别？【答案】：空树是二叉树，但不是树。树一定是非空的。在一棵度为2的树中至少有一个结点的度为2；但在一棵二叉树中每个结点的度可以都小于2,比如单枝树。.试分别画出具有3个结点的树和有3个结点的二叉树的所有不同形态。【分析】：无序树的子树没有顺序之分，而二叉树的子树分为左子树和右子树。【答案】：具有3个结点的树：有3个结点的二叉树:.设一棵完全二叉树具有1000个结点，问此完全二叉树(1)有多少个叶子结点？(2)有多少个度为2的结点？(3)有多少个结点只有非空左子树？(4)有多少个结点只有非空右子树？【分析】:有1000个结点的完全二叉树共有10层,在第10层有1000-(2-1)=1000-511=489个结点；都是叶子结点，它们共有244+1个双亲结点在第9层，其中有一个双亲结点只有一个孩子，其他共244个双亲结点的度均为2,所以在第9层还有256-245=11个结点的度为0,既为叶子结点。【答案】：(1)有500个叶子结点。(2)有255+244=499个度为2的结点；(3)有1个结点只有非空左子树；(4)没有结点只有非空右子树；.下面是有关二叉树的叙述，哪些是正确的？(1)二叉树中每个结点的两棵子树的高度差不大于1。(2)二叉树中每个结点的两棵子树的高度差等于1。(3)二叉树中每个结点的两棵子树是有序的。(4)二叉树中每个结点的两棵非空或有两棵空子树。(5)二叉树中每个结点的关键字值大于左子树(若存在的话)上所有结点的关键字值,且小于其右非空子树(若存在的话)上所有结点的关键字值。(6)二叉树中所有结点个数是2-'-1,其中k是树的深度。(7)二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。【答案】:(1)错误。AVL树中每个结点的两棵子树的高度差不大于1。(2)错误。(3)正确。(4)错误。二叉树中有些结点可以有一棵空子树，一棵非空子树。(5)错误。二叉排序树满足所叙述的条件。(6)错误。二叉树中所有结点个数至多是2k-1。(7)错误。二叉树中的结点，可以没有非空左子树，但有非空右子树。.用链式结构存储二叉树，试写出下列算法：(1)按层次输入所有结点；(2)输出所有叶子结点。【答案】：/*先定义二叉树的二叉链表结构*/typedefstructnode{intdata；structnode*lchild,*rchild；}NODE；(1)按层次输入所有结点：【分析本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。voidlayorder(NODE*root){/*设q是一个队列，函数initqueue(q)、addqueue(q,x)、delqueue(q)empty(q)在2.4.2队列中已实现*/initqueue(q)； /*初始化一个队列*/if(root!=NULL){printf("％d”,root->data)： /*输出结点值*/addqueue(q,root)； /*根结点入队*/while(NOTempty(q)){ /*如果队列不空*/p=delqueue(q)； /*对头元素出队*/if(p->lchild!=NULL){printf("%d”，p->lchild->data)； /*输出左孩子的值*/addqueue(q,p->lchild)； /*左孩子入队*/}if(p->rchild!=NULL){printf(a%d",p->rchild->data)；/*输出右孩子的值*/addqueue(q,p->rchild)； /*右孩子入队*/(2)输出所有叶子结点：【分析】：：本算法为先根遍历的递归算法。如果树不空，分三步进行：第一步，判断根结点是否为叶子结点，若是，则输出；第二步，调用该算法输出根结点的左子树上的所有叶子结点；第三步，调用该算法输出根结点的右子树上的所有叶子结点；【答案】：typedefstructnode{intdata；structnode*lchild,*rchild；}NODE；voidprintleaf(NODE*root){if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL))printf("%d"，root->data)；/*如根结点是叶子结点,则输出*/printleaf(root->lchiId)； /*输出左子树上的所有叶子结点*/printleaf(root->rchild)； /*输出右子树上的所有叶子结点*/.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组btree中，试编写一个算法打印出编号为i的结点的双亲和所以孩子。

【答案】：^defineN100intbtree[N]/*定义完全二叉树的存储结构*/voidprint_parent_child(intn,inti)(/*n为结点个数*/if(n==0){printf(uTreeisempty!w)；return；}/*空树*/elseif((i<l)||(i>n)){printf(worderierror!99)；return；}/*编号出错elseif(i==l) /*根结点无双亲*/{printf("Noparents'll")；if(2*i<=n)printf(aLchildis:%d\nw,btree[2*i])；if(2*i+K=n)printf(uRchildis:%d\nw,btree[2*i+l])；)else{printf(^Parentis:%d\nw,btree[i/2])； /*双亲*/if(2*i<=n)printf(uLchildis:%d\nw,btree[2*i])；/*左孩子*/if(2*i+l〈=n)printf("Rchildis:%d\n”,btree[2*i+l])；/*右孩子*/).试写出如下所示的二叉树分别按先序、中序、后序遍历得到的结点序歹IJ。【答案】：

先序序列:【答案】：

先序序列:

中序序列:

后序序列:ABDFJGKCEIIILMBFJDGKACHEL1MJFKGDBHLMIECA27.把如图所示的树转化为二叉树。MM.已知•棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,画出这棵二叉树。【分析】：由后序遍历序列能够得到的二叉树的根结点A(后序序列中最后一个结点)；在中序序列中，A的左边是A的左子树上的结点，A的右边是A的右子树上的结点；再到后序序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树。.对以链表作存储结构的二叉树设计求二叉树的深度的算法。typedefstructnode{intdata；structnode*lchild,*rchild；}NODE；【分析】：：本算法为递归算法。空树的深度为0,如果树不空，分三步进行：第一步,判断根结点是否为叶子结点，若是，则深度为1;第二步，调用该算法求根结点的左子树的深度hl,第三步，调用该算法求根结点的右子树的深度hr；二叉树的深度为max(hl,hr)+lo【答案】：intdepth(NODE*root){if(root==NULL)return0；elseif((root->lchild==NULL)&&(root->rchild==NULL))return(1)；/*如根结点是叶子结点，则深度为1*/else{hl=depth(root->lchiId)；/*左子树的深度*/

hr=depth(root->rchild)； /*右子树的深度*/if(hl>hr)return(hl+1)；elsereturn(hr+1)；/*深度为max(hl,hr)+1*/30.对序列12,7,17,11,16,2,13,9,21,4构成一棵二叉排序树。【答案】：.从供选择的答案中找出应添入下列叙述中的()内的正确答案。(1)要进行线性查找，则线性表();(2)要进行二分查找，则线性表()；(3)要进行散列查找，则线性表()；(A)：必须以顺序方式存储；(B)：必须以链式方式存储；(C)：必须以散列方式存储；(D)：既可以以顺序方式存储，也可以以链式方式存储：(E)：必须以顺序方式存储且数据元素已按值递增或递减的次序排好。(F)：必须以链式方式存储且数据元素已按值递增或递减的次序排好。【答案】：(1)选择D；(2)选择E；(3)选择A；.用二分查找的查找速度必然比线性查找的速度快。这说法对吗？为什么？【答案】：正确。因为用二分查找法来查找时，在每一次比较之后，如查找不成功，是将待查范围缩小一半。而采用线性查找时，每次比较之后是将待查范围缩小一个元素。二分查找的平均查找长度为：logm；而线性查找的平均查找长度为：(n+1)/2。.说明散列查找和其它查找方法的区别。【答案】：散列查找是希望平均查找长度与记录的个数无关，既不经过任何比较，“一次”存取就能得到所要查找的元素的查找方法。它要求在元素的存储位置和它的关键字之间建立个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。而其它的查找方法的平均查找长度都与记录的个数有关，但不必在元素的存储位置和它的关键字之间建立一个确定的对应关系。.r是一个顺序表结构的有序表，编写一个查找算法，要求在查找失败时做插入操作并保持表r的有序性。【分析】：：用二分查找方法，如查找成功，则返回待查元素在表中的位置，如果查找不成功,既low>high时，此时high+1的位置为待查元素所应插入的位置，这样可以保持表r的有序性。【答案】：ttdefineM500typedefstruct{intkey；charinfo；}NODE；NODEr[M]；intbinsrchinsert(intn,intk){/*k为要查找的数据，n为实际的表长*/intlow,high,mid,k；NODEtemp；low=l；high=n；while(low<=high){mid=(low+high)/2；if(k==r[mid].key)return(mid)； /*查找成功,返回*/elseif(k<r[mid],keyhigh=midT；elselow=mid+l；/*以下做有序插入*/

if(n=M){printf(uTableisfull!\n")；return0；}/*表满不能插入*/else{for(k=n；k>=high+l；k-)r[k+l]=r[k]； /*从r[high+1]到r[n]的所有元素右移一个位置*/r[high+l].key=k；r[high+1].info= ；/*数据插入*/35.设记录的关键字集合为K=(32,13,49,55,22,39,17),用模除散列函数得到散列地址，解决冲突的办法为线性探测法，按上述条件将集合中的各值依次添如下表中。35.【答案】：324939171322550 1 2 3 4 5 6 736.选取散列函数H(key)=(3*key)%11,用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0〜10,表长为11的散列表,(22,41,53,08,46,30,01,31,66).0 12 337.关键字序列0 12 337.关键字序列T={13,6,3中间过程序列。[答案]:(1)选择排序：i初始序列：13 6i完成第一趟：3[6完成第二趟：3 5完成第三趟： 3 5完成第四趟： 3 5完成第五趟： 3 5完成第六趟： 3 5完成第七趟： 3 5(2)直接插入排序：初始序列：136第一趟： [13]第二趟： [64 5 6 7 831,9,27,5,11),分别k3 31 9 27 5 11k13 31 9 27 5 11]i k[13 31 9 27 6 11]ik6 [31 9 27 13 11]i k6 9 [31 27 13 11]ik6 9 11 [27 13 31]i=k6 9 1113[ 27i=k6 9 111327[3 31 9 27 5 116 3 31 9 27 513] 3 31 9 279 10导出选择排序和直接插入与T[3]交换*//*1[2]与1[7]交换*//*1'[3]与鹿7]交换*//*T[4]与T[5]交换*//*U5]与屋8]交换*//*1[6]与1[7]交换*/31]/*不用交换*/31]115 11220141306653463108

第三趟[3613]31927511第四趟[361331]927511第五趟[3691331]27511第六趟[369132731]511第七趟[3569132731]11第八趟[356911132731]38.对于整数序列100,99, 3,2,1,如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？【答案】:对冒泡排序方法来说，这个序列是最坏的情况，n=100个数据，共进行99趟排序操作,第一趟要比较99次，第二趟要比较98次，……，第99趟要比较1次，每一次比较都执行了一次交换，所以共进行了99+98+97+……+1=100*99/2=4950次比较和交换。对快速排序方法来说，这个序列也是最坏的情况，与冒泡排序一样，共进行99趟排序。第一趟要比较99次，进行一次交换，第二趟要比较98次，不需要交换，第三趟要比较97次，进行一次交换，第四趟要比较96次，不需要交换，……，所以总的比较次数为4950次，交换的次数为50次。39.对关键码值为｛35,11,52,69,6,17,76,64,82｝的序列执行以下排序算法,画出执行过程中每个中间状态和结束时的状态:（1）直接插入排序；（1）直接插入排序；（2）二分插入排序;（3）直接选择排序；（4）冒泡排序；（5）快速排序。（3）直接选择排序:（3）直接选择排序:

初始序列：［

第一趟：

第二趟：

第三趟：

第四趟：

第五趟：

第六趟：35 11 52 69 66 [ 11 52 696 11 [ 52 696 11 17 [ 696 11 17 35 [696 11 17 35 526 11 17 35 5217 76 64 82 ]35 17 76 64 8235 17 76 64 8235 52 76 64 8252 76 64 82 ]6976648264[ 766982【答案1（1）直接插入排序:初始序列：35115269617766482第一趟[35]115269617766482第二趟[1135]5269617766482第三趟[113552]69617766482第四趟[11355269]617766482第五趟[611355269]17766482第六趟[61117355269]766482第七趟[6111735526976]6482第八趟[611173552646976]82第九趟[61117355264697682]（2）二分插入排序：与直接插入排序类似，只是在找插入位置时用二分查找方法。

第七趟:第八趟:69[ 7682]6976第七趟:第八趟:69[ 7682]6976[ 82]6 11 17 35 52 64(4)冒泡排序：初始序列：35115269617766482第一趟：11355261769647682/*4次交换*/第二趟：11356175264697682/*3次交换*/第三趟：11617355264697682/*2次交换*/第四趟：61117355264697682/*1次交换*/第五趟：61117355264697682/*没有任何交换，完成*/(5)快速排序：ij初始序列：115269617766482/*初始化i=l.j=9*/第一次交换：1171152696sj766482/*j=6时与因交换*/第二次交换：171169652j766482/*i=3时与因交换*/第三次交换：1711i669血52766482/*j=5时与因交换*/第四次交换：17116向j6952766482/*i=4时与因交换*/完成•趟排序：[17116]i=j35[6952766482]/*i=j=4*/下一趟初始：[011向527664j82]第一次交换：[611向i[645276由82]第二次交换：i=j[6452j7682]完成第二趟排序:[611]17[6452]i=j69[7682]下一趟初始：i[611]i向52jiJ082]第一次交换：i=Jij[520i=j完成第三趟排序:6[11][52]6476[82]排序完成：6111735526469 76 82第3章操作系统复习题答案选择题1.B2.C3.B4.B5.ABC6.DAA10.B17.B18.A11.C12.A选择题1.B2.C3.B4.B5.ABC6.DAA10.B17.B18.A11.C12.A19.D20.C13.A14.A15.B16.B填空题1.虚拟 2.死锁 3.就绪、执行、阻塞 4.PCB5.一个 6.资源 7.程序、出现前缀、环境块 8.外存9.动态、执行10.记录式、流式11.顺序、链接、索引12.树型.阻塞、进程、唤醒 14.系统调用、命令接口.编辑、汇编、连接、执行三.问答题.什么是操作系统？它的主要功能是什么？【解答】：操作系统是最基本的系统软件，它直接运行在裸机之上，对计算机进行资源管理和文件管理，同时为其它软件提供运行平台，为用户提供一个方便、高效、友好的使用环境。主要功能有：1）处理器管理，主要解决处理机的分配策略、实施方法和资源1口1收等问题。2）存贮管理，主要对内存资源的分配进行管理。3）文件管理，对计算机软件资源进行管理。4）设备管理，对除CPU和内存以外的所有I/O设备进行管理。5）作业管理，对用户提交的作业提供接口，同时对作业运行的其它面进行调度，组织的管理等。.对用户而言，分时系统与成批处理系统相比，有哪些优点？【解答】：1）分时系统的基本运行单位是时间片，而批处理系统的运行单位是作业，由于时间片运行时间短，并且处理器每次只运行一个时间片的任务，所以对于用户来讲，分时系统反应快，像每个用户独占一台计算机，而批处理系统需要等待。2）分时系统对时间要求严格，每次只运行一个时间片，而批处理对时间要求而不是很严格。3）分时系统可以用户对其完成的东西进行干预，而批处理系统在一个作业完成之前，用户是不能干预的。.说明分时系统和实时系统的差别【解答】：分时系统是为多个用户提供一个可以与系统进行交互会话的终端，处理器对每个用户侵入的命令，使用时间片的方式，对其进行处理，其特点是并行工作。而实时系统是是采用了事件驱动的设计方法，在系统接收到某种信息后，自动选择一个程序加以处理，并在严格的计里程控制进行。其特点是响应时间快，有较高的可行性。4.进程的概念是什么，它与程序的主要差别是什么？【解答】：进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。差别：1）程序是具有独立功能的一组指令的集合，它指出了处理机执行操作的步骤，而进程是指令的执行，是由一个动作系统组成。因此程序是表态的概念，而进程是动态的概念。2）进程是程序的一次运行活动，进程的存在是暂时的，而程序是永存的。3）进程的组成包含了程序和数据，即一个进程可以包含多个程序，而同一个程序运行在不同的数据集合上就可以构成了不同的进程。.一个进程至少要有几种状态？它们在什么情况下转化？【解答】：一个进程有三种基本状态：就绪、运行、等待；当进程刚被创建时，他的初始状态是就绪态。当处理机有空闲时，系统将根据一定的调度算法，从多个处于就绪态的进程中选择一个进程占用处理机。处于运行态的进程的发展有三种可能：如果该进程完成了他的任务，他将结束他的生命而消失；如果分配给该进程站用处理机的时间片用完了，那么它将被迫让出处理机而进入就绪态；如果进程在运行过程中需要某一条件而不能马上满足时，他将主动放弃处理机而进入等待态。处于等待态的进程只要它所等待的时间结束，该进程将进入就绪态。.什么是进程调度？常用的进程调度算法有哪些？【解答】:按照一定的算法,将处理机分配给就绪队列中某一个处于就绪状态的进程。常用的进程调度算法有：先来先服务调度算法、优先数调度算法、时间片轮转调度算法等。.什么是死锁？发生死锁的必要条件是什么？【解答】：死锁是因竞争而引起的一种现象。发生死锁的必要条件是：互斥条件、不可夺条件、部分分配条件、循环等待条件。.可以用哪些方法来预防死锁？【解答】：预防方法：预先静态分配、有序资源分配、抢夺式分配。.进程的互斥与同步有什么区别？它们之间又有什么共同之处？【解答】：进程的互斥是指进程间访问临界资源时必须采用互斥的方式，而同步是指多个进程能并发运行。它们的共同之处是对于临界资源都要互斥访问。.什么是临界区和临界资源？【解答】：临界资源是指进程间必须通过互斥方式实现共享的资源。我们把在每个进程中访问临界资源的那段代码称为临界区。.说明P,V操作的定义？【解答】：PV操作是是由P操作组成,。这两个操作是两个不可中断的过程，即是两条原语。在计算机中原语是指由若干条所构成的用以完成特定功能的一段程序，原语的执行过程是不允许中断的。.DOS的用户进程是什么？用户进程的实体由那几部分组成？【解答】：DOS的用户进程是指一个已调入内存的，当前正在执行的或正准备执行的程序。DOS用户进程的实体是由程序本身（包括代码，堆栈和数据等），-个程序段前缀（PSP）和一个环境块（EVB）三部分组成。.存储管理的功能？【解答】：存储管理的功能主要包括以下五点：1）主存空间的分配2）存储的保护3）地址的转换4）主存空间的共享5）主存空间的扩充.什么是重定位？为什么要对程序进行重定位？【解答】：允许作业在运行过程中在内存中移动的技术，必须获得硬件地址变换机构的支持。即在系统中增加一个重定位寄存器，用它来装入程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而成的，这就叫做重定位。我们知道，在连续分配方式中，为了利用“碎片”将作业装入，需要将内存中分散的小分区拼接成大分区,称为“拼接”或“紧凑”，但由于经过紧凑后的用户程序在内存中的位置发生了变化，若不对程序和数据的地址进行修改，程序将无法执行,所以必须进行重定位。.静态重定位和动态重定位的区别？【解答】：动态重定位，地址变换过程是在程序执行期间，随着对每条指令和数据的访问而自动进行的，而静态重定位则是在程序执行前装入程序在内存中的起始地址。这是两者的最显著区别。.什么是虚拟存储器？它的大小受什么限制？【解答】：所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统具体地说，就是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。其逻辑容量由内存和外存容量之和所决定。.在页式虚拟存储管理中，调页是如何实现的？【解答】：为了管理分散于内外存的页，页式虚拟存储管器对页表进行了修改，增加了标志位和磁盘上的位置两个数据项。在作业的执行过程中，在采访某页时,若该页的标志位1,则进行相应的地址转换，得到绝对地址，处理过程同简单的页式存储管理一样，若标志为0,说明该页不在主存中由硬件发出一个“缺页中断”，在缺页中断中，首先在主存中找到空闲块，其次按该页在磁盘中的位置把该页调入主存，然后在页表中填入该页所占的主存号，并把标准位改为1,最后退出缺页中断，，继续执行被中断的程序。.在页式虚拟存储管理中，淘汰页的算法主要有那几种？【解答】：在页式虚拟存储管理中，淘汰页的算法主要有:1）先进先出算法FIFO（First-InFirst-Out）2)最近最久未用算法LRU(LeastRecentlyUsed)3)最久最少使用算法LFU(LeastFrequentlyUsed).段式系统中的“段”是以什么来划分的？它与页式系统中的“页”有什么区别？【解答】：段是信息的逻辑单位，它含有一组其意义相对完整的信息，逻辑信息组的长度决定了段的长度。分段的目的是为了能更好地满足用户的需要。段的长度是不固定的。页是信息的物理单位，分页是为实现离散分配方式，提高内存的利用率，或者说，分页仅仅是由于系统管理的需要，页的大小周定且由系统决定。此外，分页的作业地址空间是一维的，而分段的作业地址空间是二维的，在标识一个地址时，既须给出段名，又需给出段内地址。.86系列CPU的工作模式有几种？DOS是工作在那种模式？【解答】：8086/88只有一种模式一实地址模式，80286则有两种模式：实地址模式和保护模式，80486及其后续机型还增加了另一种模式一虚拟86模式。DOS是工作在实地址模式下。.内存控制块的作用是什么？它提供了什么信息？【解答】：系统运行时，每当加载一个命令程序或者某个进程申请内存空间时，DOS要为它们申请的内存空间建立一个内存块供申请者使用，并在该内存块的头部设置16字节的区域头，称之为内存控制块。它提供了：标志；内存块拥有者;内存块长度；程序名等信息。.什么是文件？文件怎样划分？【解答】：文件是一个逻辑上具有完全意义的一组相关信息的有序的集合。其通常的划分有：1）按文件的性质和用途可分：系统文件，库文件和用户文件2）按文件的保存期限可分：临时文件，永久文件和档案文件3）按文件的保护级别可分：执行文件，只读文件，读写文件和无保护文件4）按文件的的逻辑结构可分：记录式文件和流式文件5）按文件的的物理结构可分：顺序文件，链接文件和索引文件6）按文件的的存取方式可分：顺序存取文件和随机读取文件23.文件系统为用户提供了哪些功能？【解答】：有：1）实现文件从名字空间到外存地址空间的转换2）管理文件的储存空间（即外存）3）建立文件目录4）实现对文件的控制操作和存取操作5）实现文件的共享、保护和保密.文件的存取方法主要有那些？各有什么特点？【解答】：有：1）顺序存取。其特点是按照文件的逻辑地址顺序进行，每次存取都是在上次存取的基础上进行的。2）随机存取。随机存取允许用户以任意的次序读写文件.文件的物理组织形式主要有哪几种？比较他们的优缺点？【解答】：文件的物理组织形式主要有三种：连续结构、链接结构和索引结构。连续结构的优点是简单只要记住存取信息的当前位置，则后续信息一定在下一位置匕但要在文件中加载信息时就十分费事了。链接结构的优点是允许用户扩充或缩小文件，只要调整文件的链接指针就很容易插入或删除物理块，其缺点是一般只宜顺序存取。索引结构除具有链接结构的优点外，还克服了其缺点，即也能随机存取，其缺点是由于有了索引表而增加了存储空间的开销，另外在存取文件要两次访问存储器，也增加了文件存取的时间。.文件系统中磁盘空闲空间管理技术主要有那几种？【解答】：一般有以下三种：1）位示图。位示图是由若干字节组成的一张表，字节的每一位对应一个物理块，用该位置的值是“0”和“1”表示对应的物理块是空闲块还是已分配。2）空闲区表。将存储空间的所有的空闲块按索引文件的方式组织，产生一个空闲区表，该表记有空闲物理块的位置及其它连续块的个数。3）空闲块链。系统将所有的空闲块链接在一起，系统设置一个空闲块链的头指针以指向第一个空闲块，每一个空闲块均有一个链接指针指向下一个空闲块，最后一个空闲块设有链尾标志。.文件目录的作用？为什么要建立多级目录？【解答】：文件目录的作用是在文件系统上实现按名存取，在文件符号名与文件的物理地址之间建立联系。之所以建立多级H录是因为其实现了不同的用户可以用相同的文件名去命名文件，而且实现了同一个用户在自己的不同的子目录中使用相同的文件名。.什么是簇号？DOS系统是如何了解某个文件所占有的存储位置的？【解答】：簇号是描述磁盘空间的一种单位，也是DOS为文件分配磁盘空间的最小单位，一个簇是一组连续的扇区。同时簇号也是文件分配表（FAT）的表目号，簇号又与磁盘上的扇区的位置对应，这样知道了文件分配到的簇号，也就知道了具体的扇区的物理位置。在DOS中上用•条“簇号链”把一个文件分配到的簇号连接起来。.设备管理的任务是什么？【解答】：主要有：1）使用实现对外围设备的分配和回收2）实现外围设备的启动3）处理外围设备的中断事件4）实现虚拟设备.简述通道技术和缓冲技术？【解答】：通道技术是指采用了专用的I/O处理机来管理外设与内存之间的信息交换，可以把通道看成一个比DMA控制器功能更强的接口。缓冲技术是指在内存中开辟专门用于数据传输过程中暂存数据的缓冲区。缓冲区的引入，减少了I/O操作占用通道的时间，缓解了因通道数比设备少而产生的“瓶颈”。.什么是独占设备、共享设备以及虚拟设备？【解答工独占设备是指一个作业在整个执行期间都占用的设备；共享设备是指可以由几个作业同时使用的设备;虚拟设备是利用高速的直接存储设备来模拟低速的独占设备，使独占设备转化为逻辑上的共享设备。.什么是假脱机技术？【解答】：假脱机技术的实现的基本思想是：1）将原来使用独占设备的输入过程分为两步，第一步是将作业所需要的数据通过物理输入设备送入外存的一个专门的区域（输入井）中，这一工作由SPOOLing系统这预输入程序来完成。第二步是当作业执行的过程这需要输入数据时，由SPOOLing系统并管理程序负责从输入井中读出有关数据。2）在输出时也分为两步，作业在执行过程需要输出数据时，第一步是由SPOOLing系统井管理程序把耍输出的数据暂存于外存的另一个区域（输出井）中，各进程的数据文件形成一个输出队列，由SPOOLing系统中井的管理程序把输出数据文件输出到具体的物理输出设备上。.什么是系统设备表？它包含了那些必要的信息？【解答】：系统设备表是系统范围内的数据结构，它记录来系统中全部的I/0设备,每一个设备一个表目，表目中列出来该设备的型号，设备的标识符等信息，指明了已分配到此设备的进程，还可从表目中找到该设备的设备控制表的位置。.什么是DOS的设备链？如何在设备链中增加新的设备驱动程序？【解答工设备链是山设备头链接而成，设备头中所标识的设备名是逻辑设备名，CON所对•应的是键盘和显示器两个物理设备，而PRN和LPT1对应系统的第一个并行打印机，AUX和COM1都是系统的第一个串行通信口。设备链中增加新的设备驱动程序只要在系统配置文件config.sys中以device命令的形式说明驱动程序的文件路径的全名即可。.什么是作业和作业步？【解答】：作业是用户在一次算题过程中，或一次事务处理过程中，要求计算机系统所作工作的集合。一个作业可以划分成多个作业步，每个作业步相对独立又相互关联，完成（汇编、连接、运行）的集合中一个特定的工作。.用户如何组织自己的作业和控制作业的运行？【解答工操作系统提供的作业级的用户接口为用户提供了各种操作命令，用户就是利用这些操作命令来组织自己的作业和控制作业的运行。作业级的用户接口分为两类：联机接口和脱机接口。联机用户在终端或控制台上输入联机操作命令，向系统提出要求，控制作业运行。脱机用户不能直接干预作业的运行，而是事先用作业控制命令写成一份作业说明书，连同作业的程序和数据一起提交给系统。.作业有那几种状态？它们之间如何转换？【解答】：作业有以下几种状态：进入状态、后备状态、执行状态、完成状态，就绪状态和等待状态。其转换如图：.作业调度的任务是什么？它与进程调度之间是什么关系？【解答】:作业调度是从进入系统等待处理的用户作业中按一定的规则选区若干个作业，为他们分配必要的资源，让他们进入主存储器，使他们能够有机会去占有处理器以便运行。作业调度的任务：完成作业从后备状态到执行状态以及刀完成状态的转换。它是按照莫种调度算法，从后备作业队列中选取一些作业进入执行状态，为选中的座也分配内存和外部资源，并为其建立有关的进程，在作业执行结束时，进入完成状态时，做好释放资源等善后处理工作。作业调度的目标：使作业运行最大限度的发挥各种资源的利用率和保持系统内各种活动的充分并行。他和进程调度不同的是，前者调度的是作业，后者是进程，每个作业可以多个进程，所以两者还是又必然的联系的。.作业的交互控制方式主要有那几种？各自的特点？【解答工不同的操作系统提供的交互控制方式是不同的，但一般提供以下的一种或几种：命令驱动方式；菜单驱动方式；命令文件方式。命令驱动方式是用户通过终端或控制台输入一条命令来控制作业的执行。命令驱动方式的优点是用户可以灵活的控制作业的执行，但其众多的命令给初学者带来来不便，而菜单驱动方式使用户按照菜单的提示来控制作业的完成。命令驱动方式是把键盘命令按作业顺序组成一个命令文件，执行此文件就可以自动控制作业的执行。.DOS系统为用户提供了那些作业管理的接口？【解答】：dos向用户提供了两类接口，即程序级接口和作业控制级接口。在程序级接口中，dos提供了软中断及系统功能调用程序员使用，在作业控制级接口中，提供了一组错作命令共用户使用。Dos下作业管理只有作业控制的功能，没有作业调度的作用。.Windows的用户界面采用了那些技术？【解答】：在windows用户界面中采用了一卜技术：1多窗口技术，支持在桌面上大开关闭窗口，改变窗口的活动或非活动状态，窗口的放大、缩小和任意移动，允许窗口的重叠合拼接。2菜单技术，能够减轻用户的记忆负担，简化用户的操作，减少键入的字符。3联机帮助技术，主要是在系统运行中，随时接受用户的查询，同时也对用户的操作主动进行引导，它一般用help软件或者对话框的形式来提供联机帮助。第4章数据库系统基础复习题答案.数据管理技术的发展经历了哪几个阶段？【解答】：人工管理阶段、文件系统阶段和数据库阶段。.数据库技术的主要特点是什么？【解答】：（1）采用复杂的结构化的数据模型；（2）最低的冗余度：（3）有较高的数据独立性；（4）保证数据的完整性。.数据的物理独立性的含义是什么？数据的逻辑独立性的含义是什么？【解答】：数据的物理独立性：概念模式和内模式之间的映像是数据的全局逻辑结构和数据的存储结构之间的映像，当数据库的存储结构发生了变化时，内模式将发生改变，但数据的逻辑结构可以保持不变，由此应用程序可以不必修改。数据的逻辑独立性：概念模式和外模式之间的映像是数据的全局逻辑结构和数据的局部逻辑结构之间的映像，当数据的全局逻辑结构发生了变化时，对不受该全局变化影响的那些局部而言，局部逻辑结构不必改变，因此根据这些局部逻辑结构所开发的应用程序也不必修改。.根据所用数据模型的不同，比较流行的数据库系统可以分为哪三类？【解答】：层次数据库系统、网状数据库系统和关系数据库系统。.什么是数据库系统？什么是数据库管理系统？它们之间是什么关系？【解答】：数据库系统由三部分组成：应用程序、数据库管理系统和数据库。数据库管理系统是管理数据的软件系统，它为用户或应用程序提供访问数据库的方法。它们之间的关系如下图所示：.解释外模式、内模式和概念模式。【解答】：外模式：又称子模式，是由用户视图中各种记录类型的相应定义所组成的，是用户允许使用的那部分数据的逻辑结构。概念模式：又称模式，是对数据库中全体数据的整体逻辑结构的描述，是所有用户的公共数据视图。它与具体的应用程序以及使用的程序设计语言无关。它除了定义数据的逻辑结构以外，还要定义与数据有关的安全性、完整性要求。内模式：又称存储模式，是最接近物理存储的一层，是数据库中最低•级的表达。

.举例分别说明实体集之间是1：1,1：n,m：n的联系。【解答】：机票与座位的联系是1：1。每一张机票对应一个座位；每一个座位对应一张机票。学生与成绩的联系是1：n。每个学生有多个成绩，每个成绩对应一个学生。学生与课程的联系是m：n。每个学生可以选修多门课程，每门课程可以被多个学生选修。.关系是一个二维表，任意一个二维表是否就是一个关系？为什么？【解答】：不是。如果二维表中出现相同的行或同一列的值不是相同的数据类型就不是一个关系。.举例说明传统的集合运算：并、差、交和笛卡尔积。【解答】：假设有两个关系：R和S。R商品编号商品名称生产厂家1001奶粉北京1005酱油天津1010饼干青岛商品编号商品名称生产厂家1001奶粉北京1006醋天津1011曲奇青岛1022酒河北

RUS商品编号商品名称生产厂家1001奶粉北京1005酱油天津1010饼干青岛1006醋天津1011曲奇青岛1022酒河北R-S商品编号商品名称生产厂家1005酱油天汴1010饼1青岛RAS商品编号商品名称生产厂家1001奶粉北京R与S的笛卡尔积商品编号商品名称生产厂家商品编号商品名称生产厂家1001奶粉北京1001奶粉北京1001奶粉北京1006醋天津1001奶粉北京1011曲奇青岛1001奶粉北京1022酒河北1005酱油天津1001奶粉北京1005酱油天津1006醋天津1005酱油天津1011曲奇青岛1005酱油天津1022酒河北1010饼干青岛1001奶粉北京1010饼干青岛1006醋天津1010饼干青岛1011曲奇青岛1010饼干青岛1022酒河北.已知如下关系M,N,求MUN,M-N,MAN。【解答】：

关系MABCalblc2alb2c3a2blc3关系NABCalb2c3a2blc2alb3c2MUNABCalblclalb2c3a2blc3a2blc2alb3c2M-NABCalblcla2blc3MANABCalb2c3.已知两个关系R、So试求出R[X]S的结果。B>D【解答1

【解答1结果ABCDEFb6D5e9.已知两个关系G,H。试求出RXS的结果。【解答1FZ匚匚ZJzdH匚结果ABCDb3c7c4d8c4d9.对于表4-12,请用关系代数运算，查找：陈中金老师所教的学生的姓名。选修英语的学生的年龄和成绩。魏立同学选修的课程的名称和教师姓名。【解答】；教师情况关系T教师号T#教师姓名TN所属系TD203王朝阳数学301刘子咏物理411张梅外语504陈中金计算机507洪文源计算机

课程关系c课程号C#课程名CN教师号T#21高等数学20331普通物理30141英语41151微机原理50452软件基础507学生情况关系S学生号T#学生姓名SN年龄SA9031林强199032高峰209033孙钵209034黄殷199035陆伟199036魏立209037蔡军20学生成绩关系SC学生号S#课程号CN成绩G903121A903141B903151B903221B903241A903251B903321B903331B903341A903431B903451A903452B903541A903551B903552B903621A903631B903652A903741B903751A903752A(1)①对T进行选择运算，条件是丁^陈中金，得到新的关系A。

关系AT#TNTD504陈中金计算机②把关系A和C进行自然连接，得到关系B。关系BT#TNTDc#CN504陈中金计算机51微机原理③关系B在TN和C#上投影，得到关系D。关系DTNC#陈中金51④关系D和关系SC进行自然连接，得到关系E。关系ETNc#S#G陈中金519031B陈中金519034A陈中金519035B陈中金519037A⑤关系E和关系S进行自然连接的关系F。关系FTNc#S#GSNSA陈中金519031B林强19陈中金519034A黄殷19陈中金519035B陆伟19陈中金519037A蔡军20⑥关系E在SN上进行投影运算得关系G。

关系GSN林强黄殷蔡军(2)①对C进行选择运算，条件是CN=英语，得到新的关系A。关系AC#CNT#41英语411②把关系A和SC进行自然连接，得到关系B。关系BC#CNS#G41英语9031B41英语9032A41英语9033A41英语9035A41英语9037B③关系B在S#和G上投影，得到关系Eo关系E④关系E和关系S功s#G9031B9032A9033A9035A9037BE行自然连接，得到关系F。关系FS#GSNSA9031B林强199032A高峰209033A孙钵209035A陆伟199037B蔡军20⑤关系F在SA和G上进行投影的关系Go关系GSAG19B20A20A19A20B（3）①对S进行选择运算,条件是SN=魏立，得到新的关系A。关系AS#SNSA903620②把关系A和SC进行自然连接，得到关系B。关系BS#SNSAcnG9036魏立2021A9036魏立2031B9036魏立2052A③关系B在C#上投影，得到关系C1。关系C1C#21~31~52④关系C1和关系C进行自然连接，得到关系D。关系DC#GNT#21高等数学20331普通物理30152软件基础507⑤关系D和关系T进行自然连接，得关系E。关系EC#CNT#TNTD21高等数学203王朝阳数学31普通物理301刘子咏物理52软件基础507洪文源计算机⑥关系E在CN和TN上进行投影，得关系F。关系FCNTN高等数学王朝阳普通物理刘子咏软件基础洪文源.FoxPro数据库文件中的字段有哪儿种类型？【解答】：字符型（C）、数值型（N）、浮点型（F）、日期型（D）、逻辑型（L）和备注型（M）。.建立数据库通常包含那些步骤？【解答】：（1）建立数据库的结构（包括字段名、数据类型、宽度、小数位数）。具体操作如下：在命令窗口输入以下命令：create数据库名.dbf,并回车，待出现输入字段的窗口后，依次输入全部字段的有关内容。然后按下Ctrl+W,将库结构存盘。（2）输入数据库记录。具体操作如下：在命令窗口输入Insert命令或Appe命令插入记录或增加记录。.在FoxPro中，DISPLAY和LIST命令有何异同？【解答】：