自考02365《计算机软件基础(二)》习题解答.pdf 53页

'《计算机软件基础�二�》习题解答第1章概论复习题答案1�怎样的计算机被称为裸机�什么是虚拟计算机�【解答】�对于一台只有硬件构成�通常包括�中央处理器cpu�储存器�输入和输出设备��而没有安装任何软件的计算机被称为裸机。而虚拟计算机则是指以硬件为物质基础�加装软件后的扩充后的计算机系统。2�计算机软件资源的作用如何�在你使用的计算机上有那些软件资源�【解答】�计算机软件资源的作用是只有在软件资源的支持下�用户所使用的计算机才能极大程度上满足用户需要的虚拟计算机。软件资源有�汇编程序�各种高级语言�各种语言的解释或编译程序�各种标准程序库�操作系统�数据库系统软件�计算机网络软件�各种应用软件等。3�汇编语言和高级语言有什么不同�【解答】�汇编语言是面向机器的语言�即不同型号的计算机的汇编语言是各不相同的�进行程序设计时必须了解所使用的计算机的结构性能和指令系统�而且编好的程序也只是针对一类机器�不能通用。高级语言是面对过程的语言�用户不必了解具体机器的细节就能编写程序�方便了程序的设计�提高了效率�同时也便于人们的交流。4�我们知道计算机只能执行机器指令�为什么它能运行汇编语言和高级语言编写的程序�【解答】�计算机之所以能运行汇编语言编写的程序是因为计算机系统中装有汇编程序�汇编程序的作用是将源程序翻译成用机器语言组成的目标程序�从而计算机能运行汇编语言编写的程序。计算机之所以能运行高级语言编写的程序是因为计算机系统中装有解释程序或编译程序�它们将用高级语言编写的程序翻译成用机器语言组成的目标程序�从而计算机能运行高级语言编写的程序。5�你学习过那些高级语言?试分析它们的特点和适用的范围�【解答】�fortran语言主要用于科学和工程计算�pascal语言则具有良好的程序结构�cobol语言则是面向事务处理的�lisp语言是人工智能语言�c语言则是通用的程序设计语言�c��语言是面向对象的程序设计语言。6�计算机软件的定义是什么�【解答】�计算机软件是指�计算机程序�实现程序功能所采用的方法�规则以及相关联的文档和在机器上运行它所需要的数据。7�操作系统的作用是什么�【解答】�操作系统控制和管理计算机的硬件、软件资源�实现对处理机�存储器�I/O设备�文件等四类资源的管理�同时操作系统还作为用户和计算机系统之间的接口�方便了人机交互。1 8�计算机操作系统在发展中经历了那些阶段�试简述它们的特点?【解答】�主要经历了�手工操作阶段、成批处理系统阶段、执行程序阶段、多道程序系统和分时系统阶段。手工操作阶段的特点�计算机的全部资源归一个用户的一个程序独占操作过程有人工来干预。成批处理系统阶段�相对于手工操作阶段�它提高了计算机资源的利用率和增强了系统的处理能力�但由于处理机和I/O设备是串行工作的�大部分时间被消耗在输入输出上�处理机的大部分时间处于等待状态�故处理机和I/O设备的速度不匹配的矛盾成为进一步提高计算机的效率的关键。执行程序阶段�使系统实现了模块化结构�易于设计、修改和扩充�但由于计算机本身的顺序性�计算机并不能完全消除对外设传输的等待。多道程序系统�它需要一个调度算法来解决cpu的分配问题�需要有一个储存管理程序来解决多道程序在内存中的定位�分配和免遭破坏�需要有一个设备管理程序来解决外设的分配�释放和信息交换�此外还需要有一个文件管理程序来解决以文件形式存放于外存中的程序和数据。分时系统阶段�分时系统阶段采用划分时间片的方法来接受和处理各个用户从终端输入的命令�由于计算机运行的高速性和并行性�使每个用户感觉不到别的用户的存在�好像独占整台机器。9�计算机应用软件有那些�【解答】�主要有以下三大领域�事务处理软件�工程和科学计算软件�实时应用软件。随着计算机技术的发展一些新的领域异军突起�如�嵌入式应用软件�微型机工具软件�人工智能软件。2 第2章数据结构复习题答案一、选择题1�线性表L在情况下适用于使用链式结构实现。�A��需经常修改L中的结点值��B��需不断对L进行删除和插入��C��L中含有大量的结点��D��L中结点结构复杂�【答案】�应选B�2�线性表在采用链表存储时其地址。�A��必须是连续的��B��部分地址是连续的��C��一定不是连续的��D��连续不连续都可以�【答案】�应选D�3�数组Q[n]用来表示一个循环队列�f为当前队列头元素的前一个位置�r为队尾元素的位置�假定队列中元素的个数小于n�计算队列中元素的公式为。�A��r-f��B��(n+f-r)%n��C��n+r-f��D��(n+r-f)%n�【答案】�应选D�4�若入栈序列为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�5�一个二维数组M�行下标的范围是1到8�列下标的范围是0到9�每个数组元素用相邻的5个字节存储�存储器按字节编址�设存储数组元素M�1�0�的第一个字节的地址是98�且按列存储�则M�3�7�的第一个字节的地址是。�A��135��B��233��C��290��D��388�【答案】�应选D。6�由3个结点所构成的二叉树有种形态�由3个结点构成的树有种形态。�A��3��B��4��C��5��D��6�【答案】�应选C和A�7�不含任何结点的空树。�A��是一棵树��B��是一棵二叉树��C��是一棵树也是一棵二叉树��D��既不是一棵树也不是一棵二叉树�【答案】�应选B。8�一棵深度为k的满二叉树中结点的个数是。kkk-1k+1�A��2-1��B��2��C��2��D��2�【答案】�应选A�9�一棵具有257个结点的完全二叉树�它的深度为。3 �A��8��B��9��C��7��D��10�【答案】�应选B�10�二叉树是非线性数据结构�所以。�A��它不能用顺序存储结构存储��B��它不能用链式存储结构存储��C��用顺序存储结构和链式存储结构都能存储��D��顺序存储结构和链式存储结构都不能存储�【答案】�应选C�11�把一棵树转换为二叉树后�这棵二叉树的形态是。�A��唯一的��B��有多种��C��有多种�但根结点都没有左孩子��D��有多种�但根结点都没有右孩子�【答案】�应选A�12�在表长为n的链表中进行线性查找�它的平均查找长度为。�A��ASL=n��B��ASL=(n+1)/2��C��ASL=n+1��D��ASL�log2(n+1)-1�【答案】�应选B�二、填空题1�数据的基本单位是�它可以由组成。【答案】�数据元素�数据项。2�把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是。【答案】�顺序存储结构。3�顺序表结构适宜于进行存取�链表适宜于进行存取。【答案】�随机存取�顺序存取。4�栈是一种特殊的线性表�允许插入和删除运算的一端为�不允许插入和删除运算的一端为。【答案】�栈顶�栈底。5�是被限定为只能在表的一端进行插入运算�在表的另一端进行删除运算的线性表。【答案】�队列。6�三元组表中的每个结点对应与稀疏矩阵的一个非零元素�它包含有三个数据项�分别表示该元素的�和。【答案】�行下标�列下标�元素值。7�对于一棵非空二叉树�它的根结点作为第一层�则它的第i层最多能有个结点。4 i-1【答案】�2。8�把一棵树转化为二叉树以后�这棵二叉树的根结点没有。【答案】�右子树。9�在数据的存放无规律而言的线性表中进行检索的最佳方法是。【答案】�线性检索。10�有一个表长为m的散列表�初始状态为空�现将n(nlink�}return(i)�}3�给定一个n项元素的线性表V�写一个算法�将元素排列的次序颠倒过来�要求仍占用原来的空间�并且用顺序表和单链表两种方法表示。【分析】�将V[1]与V[n]交换�V[2]与V[n-1]交换�„„�V[n/2]与V[n/2+1]交换.【答案】�顺序表结构下的实现�#defineM1000intv[M]�intn�voidinvert(){inttemp�for(i=0�i<=n/2�i++){temp=v[i]�v[i]=v[n-i-1]�v[n-i-1]=temp�}}6 【分析】�依次从原单链表的头部删除一个结点�在插入到另一个从空链表开始的单链表的头部。【答案】�单链表结构下的实现�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�/*新链表的头指针*/}4�试设计实现在单链表中删除值相同的多余结点的算法。【答案】�typedefstructsnode{chardata�structsnode*link�}NODE�voidpurge_lklist(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�}/*更新检查结点*/}5�描述以下三个概念的区别�头指针、头结点、首元元素结点。【答案】�头指针�是指向单链表的第一个结点的指针。头结点�在链表的首元元素结点之前附设的一个结点。首元元素结点�是指用于存储线性表中第一个数据的结点。6�写出计算线性链表长度的算法。【分析】��根据单链表的特性�从单链表第一个结点开始访问�只要是非空结点�计数一次�直到所有结点访问一遍。【答案】�typedefstructsnode{chardata�structsnode*link�}NODE�7 intlength(NODE*head){NODE*p�inti�p=head�i=0�/*初始化*/while(p!=NULL){i++�p=p->link�}return(i)�}7�设有一个线性链表�其结点为正整数�且按值从小到大链接。试写出一个算法�将此线性链表分解成两个线性链表�其中一个链表中的结点值均为奇数�而另一个链表中的结点值均为偶数�且这两个链表均按值从小到大链接。【分析】�在链表head中依次取元素(s->data)�若取出的元素是奇数�把它插入到奇数链表ahead中�若取出的元素是偶数�把它插入到偶数链表bhead中�继续取下一个元素�直到链表的尾部�头指针ahead和bhead分别指向奇数链表和偶数链表。【答案】�typedefstructsnode{intdata�structsnode*link�}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�/*置偶数表的表尾*/}8�假设有一个循环单链表的长度大于1�且表中既无头结点也无头指针。已知S为指向链表中某结点的指针�试编写算法�在链表中删除S指针所指结点的前驱结点。【分析】��设置一个指针p�指向S结点的前驱结点的前驱结点。【答案】�typedefstructsnode{chardata�structsnode*link�}NODE�NODE*s�voiddeleteprior(){NODE*p�*q�p=s�while(p->link->link!=s)p=p->link�/*让p指向s结点的前驱结点的前驱结点*/8 q=p->link�/*q指向被删除结点*/p->link=q->link�/*删除*/free(q)�}9�已知指针ha和hb分别指向两个单链表的头结点�且头结点的数据域中存放链表的长度�试写出一个算法将这两个链表连接在一起�并要求算法以尽可能短的时间内完成运算。【分析】��令表hb的首元结点连在表ha中的最后一个结点之后�首先想将工作指针p从ha的首元结点开始遍历到表ha中的最后一个结点�hc指向连接后的链表的头结点。【答案】�typedefstructsnode{chardata�structsnode*link�}NODE�NODE*ha�*hb�*hc�voidexample9(){NODE*p�inti�hc=ha�/*hc指向连接后的链表的头结点*/p=ha->link�i=1�/*用于表ha中结点的计数器*/while(idata)p=p->link�/*ha->data是表ha的长度*/p->link=hb->link�/*连接表hb的首元结点*/hc->data=ha->data+hb->data�/*连接后的链表的长度*/}10�对于下面的每一步�画出栈元素和栈顶指针示意图。�1�栈空��2�在栈中入栈一个元素A��3�在栈中入栈一个元素B��4�出栈中一个元素��5�在栈中入栈一个元素C��6�出栈中一个元素��7�出栈中一个元素�【答案】�BCAAAAA�1��2��3��4��5��6��7�11�设有编号为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�说明栈和队列的异同点。9 【答案】�相同点�栈和队列都是线性表结构�不同点�栈是限定在线性表的一端进行插入和删除的操作�而队列的插入和删除在线性表的两端进行�13�顺序队的“假溢出”是怎样产生的�如何知道循环队是空还是满�【答案】�队列的尾指针已经到了数组的上界�此时如果还要执行入队运算�就要发生“上溢”�但是数组中还有空位置�这种现象称为“假溢出”。在循环队中�当rear==front时�表示队空�当(rear+1)%M==front时�表示队满。14�设循环队列的容量为40�序号从0到39��现经过一系列的入队和出队运算后�有�1�front=11�rear=19��2�front=19�rear=11�问在这两种情况下�循环队列中的各有多少个元素�【答案】��1��8个��2��32�15�假设一数组squ[m]存放循环队列的元素。若要使m个分量都得到利用�则需要另一个标志tag�以tag为0或1来区分队尾指针和队头指针值相同时队列的状态是“空”还是“满”。试编写与此结构相应的入队和出队的算法。【答案】�#defineM100intsqu[M]�front�rear�tag�/*队列中加一个标志域tag*/intaddque(intx){/*入队运算*/if((tag==1)&&(front==rear)){printf(“fullqueuer!n”)�return(-1)�}else{rear=(rear+1)%M�squ[rear]=x�if(rear==front)tag=1�/*如果插入后队列满�则置标志*/}}intdelque(){/*出队运算*/if(tag==0)&&(front==rear)){printf(“emptyqueuer!n”)�return(-1)�}else{front=�front+1}%M�if(front==rear)tag=0�/*如果删除后队列空�则置标志*/return(squ[front])�}}16�假设以带头结点的循环单链表表示队列�并且只设一个指针指向队尾元素结点�不设头10 指针�试编写相应的入队和出队算法。【答案】�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(“queueisempty!n”)�return(-1)�}else{p=rear->link�/*p指向头结点*/q=p->link�/*q指向被删除结点*/if(q==rear)rear=p�/*队列中仅有一个结点时�先修改尾指针*/p->link=q->link�x=q->data�free(q)�return(x)�/*删除结点并返回*/}}17�已知二维数组Am�m采用按行优先顺序存放�每个元素占K个存储单元�并且第一个元素的存储地址为LOC�a11��请写出LOC�aij�的计算公式。如果采用列优先顺序存放呢�【答案】�按行优先顺序存放�LOC(aij)=LOC(a11)+((i-1)*m+(j-1))*K�按列优先顺序存放�LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*K�18�用三元组表表示下列稀疏矩阵�0000000000000-20000000000009003000800000000�1�00000000�2�00500000060000000000000000000000300000000520000000【答案】��1��2�行下标列下标元素值66416-225943565311 行下标列下标元素值88532336854678581219�下列各三元组表分别表示一个稀疏矩阵�试写出它们的稀疏矩阵。6461224551312111�1�313�2�2494443285363566116437【答案】�0212010000000000090�1��3000�2��0800600040070000601600020�什么样的二叉树不是树�一棵度为2的树与一棵二叉树有何区别�【答案】�空树是二叉树�但不是树。树一定是非空的。在一棵度为2的树中至少有一个结点的度为2�但在一棵二叉树中每个结点的度可以都小于2�比如单枝树。21�试分别画出具有3个结点的树和有3个结点的二叉树的所有不同形态。【分析】�无序树的子树没有顺序之分�而二叉树的子树分为左子树和右子树。【答案】�具有3个结点的树�12 有3个结点的二叉树�22�设一棵完全二叉树具有1000个结点�问此完全二叉树�1�有多少个叶子结点��2�有多少个度为2的结点��3�有多少个结点只有非空左子树��4�有多少个结点只有非空右子树�9【分析】�有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�没有结点只有非空右子树�23�下面是有关二叉树的叙述�哪些是正确的��1�二叉树中每个结点的两棵子树的高度差不大于1。�2�二叉树中每个结点的两棵子树的高度差等于1。�3�二叉树中每个结点的两棵子树是有序的。�4�二叉树中每个结点的两棵非空或有两棵空子树。�5�二叉树中每个结点的关键字值大于左子树�若存在的话�上所有结点的关键字值�且小于其右非空子树�若存在的话�上所有结点的关键字值。k-1�6�二叉树中所有结点个数是2–1�其中k是树的深度。�7�二叉树中所有结点�如果不存在非空左子树�则不存在非空右子树。【答案】��1�错误。AVL树中每个结点的两棵子树的高度差不大于1。�2�错误。�3�正确。�4�错误。二叉树中有些结点可以有一棵空子树�一棵非空子树。�5�错误。二叉排序树满足所叙述的条件。k�6�错误。二叉树中所有结点个数至多是2–1。�7�错误。二叉树中的结点�可以没有非空左子树�但有非空右子树。24�用链式结构存储二叉树�试写出下列算法��1�按层次输入所有结点��2�输出所有叶子结点。【答案】�/*先定义二叉树的二叉链表结构*/13 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(“%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->lchild)�/*输出左子树上的所有叶子结点*/printleaf(root->rchild)�/*输出右子树上的所有叶子结点*/}}25�已知一棵具有n个结点的完全二叉树被顺序存储于一维数组btree中�试编写一个算法打印出编号为i的结点的双亲和所以孩子。14 【答案】�#defineN100intbtree[N]/*定义完全二叉树的存储结构*/voidprint_parent_child(intn�inti){/*n为结点个数*/if(n==0){printf(“Treeisempty!”)�return�}/*空树*/elseif((i<1)||(i>n)){printf(“orderierror!”)�return�}/*编号出错*/elseif(i==1)/*根结点无双亲*/{printf(“Noparentsn”)�if(2*i<=n)printf(“Lchildis:%dn”�btree[2*i])�if(2*i+1<=n)printf(“Rchildis:%dn”�btree[2*i+1])�}else{printf(“Parentis:%dn”�btree[i/2])�/*双亲*/if(2*i<=n)printf(“Lchildis:%dn”�btree[2*i])�/*左孩子*/if(2*i+1<=n)printf(“Rchildis:%dn”�btree[2*i+1])�/*右孩子*/}}26�试写出如下所示的二叉树分别按先序、中序、后序遍历得到的结点序列。ABCDEFGHIJKLM【答案】�先序序列�ABDFJGKCEHILM中序序列�BFJDGKACHELIM后序序列�JFKGDBHLMIECA27�把如图所示的树转化为二叉树。ABCDEFGHIJKLM【答案】�ABECKFHDLGIMJ15 28�已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA�画出这棵二叉树。【分析】�由后序遍历序列能够得到的二叉树的根结点A�后序序列中最后一个结点��在中序序列中�A的左边是A的左子树上的结点�A的右边是A的右子树上的结点�再到后序序列中找左子树和右子树的根结点�依次类推�直到画出该二叉树。【答案】�ABFGCDEH29�对以链表作存储结构的二叉树设计求二叉树的深度的算法。typedefstructnode{intdata�structnode*lchild�*rchild�}NODE�【分析】��本算法为递归算法。空树的深度为0�如果树不空�分三步进行�第一步�判断根结点是否为叶子结点�若是�则深度为1�第二步�调用该算法求根结点的左子树的深度hl�第三步�调用该算法求根结点的右子树的深度hr�二叉树的深度为max(hl�hr)+1。【答案】�intdepth(NODE*root){if(root==NULL)return0�elseif((root->lchild==NULL)&&(root->rchild==NULL))return(1)�/*如根结点是叶子结点�则深度为1*/else{hl=depth(root->lchild)�/*左子树的深度*/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构成一棵二叉排序树。【答案】�127172121116491316 31�从供选择的答案中找出应添入下列叙述中的��内的正确答案。�1�要进行线性查找�则线性表����2�要进行二分查找�则线性表����3�要进行散列查找�则线性表����A��必须以顺序方式存储��B��必须以链式方式存储��C��必须以散列方式存储��D��既可以以顺序方式存储�也可以以链式方式存储��E��必须以顺序方式存储且数据元素已按值递增或递减的次序排好。�F��必须以链式方式存储且数据元素已按值递增或递减的次序排好。【答案】��1�选择D��2�选择E��3�选择A�32�用二分查找的查找速度必然比线性查找的速度快。这说法对吗�为什么�【答案】�正确。因为用二分查找法来查找时�在每一次比较之后�如查找不成功�是将待查范围缩小一半。而采用线性查找时�每次比较之后是将待查范围缩小一个元素。二分查找的平均查找长度为�log2n�而线性查找的平均查找长度为��n+1�/2。33�说明散列查找和其它查找方法的区别。【答案】�散列查找是希望平均查找长度与记录的个数无关�既不经过任何比较�“一次”存取就能得到所要查找的元素的查找方法。它要求在元素的存储位置和它的关键字之间建立一个确定的对应关系�使每个关键字和结构中一个唯一的存储位置相对应。而其它的查找方法的平均查找长度都与记录的个数有关�但不必在元素的存储位置和它的关键字之间建立一个确定的对应关系。34�r是一个顺序表结构的有序表�编写一个查找算法�要求在查找失败时做插入操作并保持表r的有序性。【分析】��用二分查找方法�如查找成功�则返回待查元素在表中的位置�如果查找不成功�既low>high时�此时high+1的位置为待查元素所应插入的位置�这样可以保持表r的有序性。【答案】�#defineM500typedefstruct{intkey�charinfo�}NODE�NODEr[M]�intbinsrch_insert(intn�intk){/*k为要查找的数据�n为实际的表长*/intlow�high�mid�k�NODEtemp�low=1�high=n�while(low<=high){mid=(low+high)/2�if(k==r[mid].key)return(mid)�/*查找成功�返回*/elseif(k=high+1�k--)r[k+1]=r[k]�/*从r[high+1]到r[n]的所有元素右移一个位置*/r[high+1].key=k�r[high+1].info=„„�/*数据插入*/}}35�设记录的关键字集合为K=�32�13�49�55�22�39�17��用模除散列函数得到散列地址�解决冲突的办法为线性探测法�按上述条件将集合中的各值依次添如下表中。【答案】�324939171322550123456736�选取散列函数H�key�=�3*key�%11�用线性探测法处理冲突�对下列关键码序列构造一个散列地址空间为0~10�表长为11的散列表��22�41�53�08�46�30�01�31�66�。22014130665346310801234567891037�关键字序列T={13�6�3�31�9�27�5�11}�分别写出选择排序和直接插入排序的中间过程序列。【答案】��1�选择排序�ik初始序列�136331927511/*T[1]与T[3]交换*/ik完成第一趟�3[61331927511]/*T[2]与T[7]交换*/ik完成第二趟�35[1331927611]/*T[3]与T[7]交换*/ik完成第三趟�356[319271311]/*T[4]与T[5]交换*/ik完成第四趟�3569[31271311]/*T[5]与T[8]交换*/ik完成第五趟�356911[271331]/*T[6]与T[7]交换*/i=k完成第六趟�35691113[2731]/*不用交换*/i=k完成第七趟�3569111327[31]�2�直接插入排序�初始序列�136331927511第一趟�[13]6331927511第二趟�[613]33192751118 第三趟�[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�直接插入排序��2�二分插入排序��3�直接选择排序��4�冒泡排序��5�快速排序。【答案】��1�直接插入排序�初始序列�35115269617766482第一趟�[35]115269617766482第二趟�[1135]5269617766482第三趟�[113552]69617766482第四趟�[11355269]617766482第五趟�[611355269]17766482第六趟�[61117355269]766482第七趟�[6111735526976]6482第八趟�[611173552646976]82第九趟�[61117355264697682]�2�二分插入排序�与直接插入排序类似�只是在找插入位置时用二分查找方法。�3�直接选择排序�初始序列�[35115269617766482]第一趟�6[1152693517766482]第二趟�611[52693517766482]第三趟�61117[693552766482]第四趟�6111735[6952766482]第五趟�611173552[69766482]第六趟�61117355264[766982]19 第七趟�6111735526469[7682]第八趟�611173552646976[82]�4�冒泡排序�初始序列�35115269617766482第一趟�11355261769647682/*4次交换*/第二趟�11356175264697682/*3次交换*/第三趟�11617355264697682/*2次交换*/第四趟�61117355264697682/*1次交换*/第五趟�61117355264697682/*没有任何交换�完成*/ij�5�快速排序�初始序列�35115269617766482/*初始化i=1�j=9*/ij第一次交换�17115269635766482/*j=6时与35交换*/ij第二次交换�17113569652766482/*i=3时与35交换*/ij第三次交换�17116693552766482/*j=5时与35交换*/ij第四次交换�17116356952766482/*i=4时与35交换*/i=j完成一趟排序�[17116]35[6952766482]/*i=j=4*/ijij下一趟初始�[17116][6952766482]ijij第一次交换�[61117][6452766982]i=jij第二次交换�[6452697682]i=j完成第二趟排序�[611]17[6452]69[7682]ijijij下一趟初始�[611][6452][7682]i=jiji=j第一次交换�[5264]完成第三趟排序�6[11][52]6476[82]排序完成�6111735526469768220 第3章操作系统复习题答案一�选择题1�B2�C3�B4�B5�ABC6�D7�C8�A9�A10�B11�C12�A13�A14�A15�B16�B17�B18�A19�D20�C二�填空题1�虚拟2�死锁3�就绪、执行、阻塞4�PCB5�一个6�资源7�程序、出现前缀、环境块8�外存9�动态、执行10�记录式、流式11�顺序、链接、索引12�树型13�阻塞、进程、唤醒14�系统调用、命令接口15�编辑、汇编、连接、执行三�问答题1�什么是操作系统�它的主要功能是什么�【解答】�操作系统是最基本的系统软件�它直接运行在裸机之上�对计算机进行资源管理和文件管理�同时为其它软件提供运行平台�为用户提供一个方便、高效、友好的使用环境。主要功能有�1)处理器管理�主要解决处理机的分配策略、实施方法和资源回收等问题。2)存贮管理�主要对内存资源的分配进行管理。3)文件管理�对计算机软件资源进行管理。4)设备管理�对除CPU和内存以外的所有I/0设备进行管理。5)作业管理�对用户提交的作业提供接口�同时对作业运行的其它面进行调度�组织的管理等。2�对用户而言�分时系统与成批处理系统相比�有哪些优点�【解答】�1�分时系统的基本运行单位是时间片�而批处理系统的运行单位是作业�由于时间片运行时间短�并且处理器每次只运行一个时间片的任务�所以对于用户来讲�分时系统反应快�像每个用户独占一台计算机�而批处理系统需要等待。2�分时系统对时间要求严格�每次只运行一个时间片�而批处理对时间要求而不是很严格。3�分时系统可以用户对其完成的东西进行干预�而批处理系统在一个作业完成之前�用户是不能干预的。3�说明分时系统和实时系统的差别【解答】�分时系统是为多个用户提供一个可以与系统进行交互会话的终端�处理器对每个用户侵入的命令�使用时间片的方式�对其进行处理�其特点是并行工作。而实时系统是是采用了事件驱动的设计方法�在系统接收到某种信息后�自动选择一个程序加以处理�并在严格的计里程控制进行。其特点是响应时间快�有较高的可行性。21 4�进程的概念是什么�它与程序的主要差别是什么�【解答】�进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。差别�1�程序是具有独立功能的一组指令的集合�它指出了处理机执行操作的步骤�而进程是指令的执行�是由一个动作系统组成。因此程序是表态的概念�而进程是动态的概念。2�进程是程序的一次运行活动�进程的存在是暂时的�而程序是永存的。3�进程的组成包含了程序和数据�即一个进程可以包含多个程序�而同一个程序运行在不同的数据集合上就可以构成了不同的进程。5�一个进程至少要有几种状态�它们在什么情况下转化�【解答】�一个进程有三种基本状态�就绪、运行、等待�当进程刚被创建时�他的初始状态是就绪态。当处理机有空闲时�系统将根据一定的调度算法�从多个处于就绪态的进程中选择一个进程占用处理机。处于运行态的进程的发展有三种可能�如果该进程完成了他的任务�他将结束他的生命而消失�如果分配给该进程站用处理机的时间片用完了�那么它将被迫让出处理机而进入就绪态�如果进程在运行过程中需要某一条件而不能马上满足时�他将主动放弃处理机而进入等待态。处于等待态的进程只要它所等待的时间结束�该进程将进入就绪态。6�什么是进程调度�常用的进程调度算法有哪些�【解答】�按照一定的算法�将处理机分配给就绪队列中某一个处于就绪状态的进程。常用的进程调度算法有�先来先服务调度算法、优先数调度算法、时间片轮转调度算法等。7�什么是死锁�发生死锁的必要条件是什么�【解答】�死锁是因竞争而引起的一种现象。发生死锁的必要条件是�互斥条件、不可夺条件、部分分配条件、循环等待条件。8�可以用哪些方法来预防死锁�【解答】�预防方法�预先静态分配、有序资源分配、抢夺式分配。9�进程的互斥与同步有什么区别�它们之间又有什么共同之处�【解答】�进程的互斥是指进程间访问临界资源时必须采用互斥的方式�而同步是指多个进程能并发运行。它们的共同之处是对于临界资源都要互斥访问。10�什么是临界区和临界资源�【解答】�临界资源是指进程间必须通过互斥方式实现共享的资源。我们把在每个进程中访问临界资源的那段代码称为临界区。11�说明P�V操作的定义�【解答】�PV操作是是由P操作组成�。这两个操作是两个不可中断的过程�即是两条原语。在计算机中原语是指由若干条所构成的用以完成特定功能的一段程序�原语的执行过程是不允许中断的。22 12�DOS的用户进程是什么�用户进程的实体由那几部分组成�【解答】�DOS的用户进程是指一个已调入内存的�当前正在执行的或正准备执行的程序。DOS用户进程的实体是由程序本身�包括代码�堆栈和数据等��一个程序段前缀�PSP�和一个环境块�EVB�三部分组成。13�存储管理的功能�【解答】�存储管理的功能主要包括以下五点�1�主存空间的分配2�存储的保护3�地址的转换4�主存空间的共享5�主存空间的扩充14�什么是重定位�为什么要对程序进行重定位�【解答】�允许作业在运行过程中在内存中移动的技术�必须获得硬件地址变换机构的支持。即在系统中增加一个重定位寄存器�用它来装入程序在内存中的起始地址。程序在执行时�真正访问的内存地址是相对地址与重定位寄存器中的地址相加而成的�这就叫做重定位。我们知道�在连续分配方式中�为了利用“碎片”将作业装入�需要将内存中分散的小分区拼接成大分区�称为”拼接”或”紧凑”,但由于经过紧凑后的用户程序在内存中的位置发生了变化,若不对程序和数据的地址进行修改,程序将无法执行,所以必须进行重定位。15�静态重定位和动态重定位的区别�【解答】�动态重定位,地址变换过程是在程序执行期间,随着对每条指令和数据的访问而自动进行的,而静态重定位则是在程序执行前装入程序在内存中的起始地址。这是两者的最显著区别。16�什么是虚拟存储器�它的大小受什么限制�【解答】�所谓虚拟存储器�是指仅把作业的一部分装入内存便可运行作业的存储器系统具体地说�就是指具有请求调入功能和置换功能�能从逻辑上对内存容量进行扩充的一种存储器系统。其逻辑容量由内存和外存容量之和所决定。17�在页式虚拟存储管理中�调页是如何实现的�【解答】�为了管理分散于内外存的页�页式虚拟存储管器对页表进行了修改�增加了标志位和磁盘上的位置两个数据项。在作业的执行过程中�在采访某页时�若该页的标志位1�则进行相应的地址转换�得到绝对地址�处理过程同简单的页式存储管理一样�若标志为0�说明该页不在主存中由硬件发出一个“缺页中断”�在缺页中断中�首先在主存中找到空闲块�其次按该页在磁盘中的位置把该页调入主存�然后在页表中填入该页所占的主存号�并把标准位改为1�最后退出缺页中断��继续执行被中断的程序。18�在页式虚拟存储管理中�淘汰页的算法主要有那几种�【解答】�在页式虚拟存储管理中�淘汰页的算法主要有�1�先进先出算法FIFO�First-InFirst-Out�23 2�最近最久未用算法LRU�LeastRecentlyUsed�3�最久最少使用算法LFU�LeastFrequentlyUsed�19�段式系统中的“段”是以什么来划分的�它与页式系统中的“页”有什么区别�【解答】�段是信息的逻辑单位�它含有一组其意义相对完整的信息�逻辑信息组的长度决定了段的长度。分段的目的是为了能更好地满足用户的需要。段的长度是不固定的。页是信息的物理单位�分页是为实现离散分配方式�提高内存的利用率�或者说�分页仅仅是由于系统管理的需要�页的大小固定且由系统决定。此外�分页的作业地址空间是一维的�而分段的作业地址空间是二维的�在标识一个地址时�既须给出段名�又需给出段内地址。20�86系列CPU的工作模式有几种�DOS是工作在那种模式�【解答】�8086/88只有一种模式—实地址模式�80286则有两种模式�实地址模式和保护模式�80486及其后续机型还增加了另一种模式—虚拟86模式。DOS是工作在实地址模式下。21�内存控制块的作用是什么�它提供了什么信息�【解答】�系统运行时�每当加载一个命令程序或者某个进程申请内存空间时�DOS要为它们申请的内存空间建立一个内存块供申请者使用�并在该内存块的头部设置16字节的区域头�称之为内存控制块。它提供了�标志�内存块拥有者�内存块长度�程序名等信息。22�什么是文件�文件怎样划分�【解答】�文件是一个逻辑上具有完全意义的一组相关信息的有序的集合。其通常的划分有�1�按文件的性质和用途可分�系统文件�库文件和用户文件2�按文件的保存期限可分�临时文件�永久文件和档案文件3�按文件的保护级别可分�执行文件�只读文件�读写文件和无保护文件4�按文件的的逻辑结构可分�记录式文件和流式文件5�按文件的的物理结构可分�顺序文件�链接文件和索引文件6)按文件的的存取方式可分�顺序存取文件和随机读取文件23�文件系统为用户提供了哪些功能�【解答】�有�1�实现文件从名字空间到外存地址空间的转换2�管理文件的储存空间�即外存�3�建立文件目录4)实现对文件的控制操作和存取操作5)实现文件的共享、保护和保密24�文件的存取方法主要有那些�各有什么特点�【解答】�有�1�顺序存取。其特点是按照文件的逻辑地址顺序进行�每次存取都是在上次存取的基础上进行的。24 2�随机存取。随机存取允许用户以任意的次序读写文件25�文件的物理组织形式主要有哪几种�比较他们的优缺点�【解答】�文件的物理组织形式主要有三种�连续结构、链接结构和索引结构。连续结构的优点是简单只要记住存取信息的当前位置�则后续信息一定在下一位置上�但要在文件中加载信息时就十分费事了。链接结构的优点是允许用户扩充或缩小文件�只要调整文件的链接指针就很容易插入或删除物理块�其缺点是一般只宜顺序存取。索引结构除具有链接结构的优点外�还克服了其缺点�即也能随机存取�其缺点是由于有了索引表而增加了存储空间的开销�另外在存取文件要两次访问存储器�也增加了文件存取的时间。26�文件系统中磁盘空闲空间管理技术主要有那几种�【解答】�一般有以下三种�1�位示图。位示图是由若干字节组成的一张表�字节的每一位对应一个物理块�用该位置的值是“0”和“1”表示对应的物理块是空闲块还是已分配。2�空闲区表。将存储空间的所有的空闲块按索引文件的方式组织�产生一个空闲区表�该表记有空闲物理块的位置及其它连续块的个数。3�空闲块链。系统将所有的空闲块链接在一起�系统设置一个空闲块链的头指针以指向第一个空闲块�每一个空闲块均有一个链接指针指向下一个空闲块�最后一个空闲块设有链尾标志。27�文件目录的作用�为什么要建立多级目录�【解答】�文件目录的作用是在文件系统上实现按名存取�在文件符号名与文件的物理地址之间建立联系。之所以建立多级目录是因为其实现了不同的用户可以用相同的文件名去命名文件�而且实现了同一个用户在自己的不同的子目录中使用相同的文件名。28�什么是簇号�DOS系统是如何了解某个文件所占有的存储位置的�【解答】�簇号是描述磁盘空间的一种单位�也是DOS为文件分配磁盘空间的最小单位�一个簇是一组连续的扇区。同时簇号也是文件分配表�FAT�的表目号�簇号又与磁盘上的扇区的位置对应�这样知道了文件分配到的簇号�也就知道了具体的扇区的物理位置。在DOS中上用一条“簇号链”把一个文件分配到的簇号连接起来。29�设备管理的任务是什么�【解答】�主要有�1�使用实现对外围设备的分配和回收2�实现外围设备的启动3)处理外围设备的中断事件4)实现虚拟设备30�简述通道技术和缓冲技术�【解答】�通道技术是指采用了专用的I/O处理机来管理外设与内存之间的信息交换�可以把通道看成一个比DMA控制器功能更强的接口。缓冲技术是指在内存中开25 辟专门用于数据传输过程中暂存数据的缓冲区。缓冲区的引入�减少了I/O操作占用通道的时间�缓解了因通道数比设备少而产生的“瓶颈”。31�什么是独占设备、共享设备以及虚拟设备�【解答】�独占设备是指一个作业在整个执行期间都占用的设备�共享设备是指可以由几个作业同时使用的设备�虚拟设备是利用高速的直接存储设备来模拟低速的独占设备�使独占设备转化为逻辑上的共享设备。32�什么是假脱机技术�【解答】�假脱机技术的实现的基本思想是�1�将原来使用独占设备的输入过程分为两步�第一步是将作业所需要的数据通过物理输入设备送入外存的一个专门的区域�输入井�中�这一工作由SPOOLing系统这预输入程序来完成。第二步是当作业执行的过程这需要输入数据时�由SPOOLing系统井管理程序负责从输入井中读出有关数据。2�在输出时也分为两步�作业在执行过程需要输出数据时�第一步是由SPOOLing系统井管理程序把要输出的数据暂存于外存的另一个区域�输出井�中�各进程的数据文件形成一个输出队列�由SPOOLing系统中井的管理程序把输出数据文件输出到具体的物理输出设备上。33�什么是系统设备表�它包含了那些必要的信息�【解答】�系统设备表是系统范围内的数据结构�它记录来系统中全部的�/O设备�每一个设备一个表目�表目中列出来该设备的型号�设备的标识符等信息�指明了已分配到此设备的进程�还可从表目中找到该设备的设备控制表的位置。34�什么是DOS的设备链�如何在设备链中增加新的设备驱动程序�【解答】�设备链是由设备头链接而成�设备头中所标识的设备名是逻辑设备名�CON所对应的是键盘和显示器两个物理设备�而PRN和LPT1对应系统的第一个并行打印机�AUX和COM1都是系统的第一个串行通信口。设备链中增加新的设备驱动程序只要在系统配置文件config.sys中以device命令的形式说明驱动程序的文件路径的全名即可。35�什么是作业和作业步�【解答】�作业是用户在一次算题过程中�或一次事务处理过程中�要求计算机系统所作工作的集合。一个作业可以划分成多个作业步�每个作业步相对独立又相互关联�完成�汇编、连接、运行�的集合中一个特定的工作。36�用户如何组织自己的作业和控制作业的运行�【解答】�操作系统提供的作业级的用户接口为用户提供了各种操作命令�用户就是利用这些操作命令来组织自己的作业和控制作业的运行。作业级的用户接口分为两类�联机接口和脱机接口。联机用户在终端或控制台上输入联机操作命令�向系统提出要求�控制作业运行。脱机用户不能直接干预作业的运行�而是事先用作业控制命令写成一份作业说明书�连同作业的程序和数据一起提交给系统。37�作业有那几种状态�它们之间如何转换�26 【解答】�作业有以下几种状态�进入状态、后备状态、执行状态、完成状态�就绪状态和等待状态。其转换如图�运行进程调度完成进入后备就绪等待作业调度38�作业调度的任务是什么�它与进程调度之间是什么关系�【解答】�作业调度是从进入系统等待处理的用户作业中按一定的规则选区若干个作业�为他们分配必要的资源�让他们进入主存储器�使他们能够有机会去占有处理器以便运行。作业调度的任务�完成作业从后备状态到执行状态以及刀完成状态的转换。它是按照莫种调度算法�从后备作业队列中选取一些作业进入执行状态�为选中的座也分配内存和外部资源�并为其建立有关的进程�在作业执行结束时�进入完成状态时�做好释放资源等善后处理工作。作业调度的目标�使作业运行最大限度的发挥各种资源的利用率和保持系统内各种活动的充分并行。他和进程调度不同的是�前者调度的是作业�后者是进程�每个作业可以多个进程�所以两者还是又必然的联系的。39�作业的交互控制方式主要有那几种�各自的特点�【解答】�不同的操作系统提供的交互控制方式是不同的�但一般提供以下的一种或几种�命令驱动方式�菜单驱动方式�命令文件方式。命令驱动方式是用户通过终端或控制台输入一条命令来控制作业的执行。命令驱动方式的优点是用户可以灵活的控制作业的执行�但其众多的命令给初学者带来来不便�而菜单驱动方式使用户按照菜单的提示来控制作业的完成。命令驱动方式是把键盘命令按作业顺序组成一个命令文件�执行此文件就可以自动控制作业的执行。40�DOS系统为用户提供了那些作业管理的接口�【解答】�dos向用户提供了两类接口�即程序级接口和作业控制级接口。在程序级接口中�dos提供了软中断及系统功能调用程序员使用�在作业控制级接口中�提供了一组错作命令共用户使用。Dos下作业管理只有作业控制的功能�没有作业调度的作用。41�Windows的用户界面采用了那些技术�【解答】�在windows用户界面中采用了一下技术�1多窗口技术�支持在桌面上大27 开关闭窗口�改变窗口的活动或非活动状态�窗口的放大、缩小和任意移动�允许窗口的重叠合拼接。2菜单技术�能够减轻用户的记忆负担�简化用户的操作�减少键入的字符。3联机帮助技术�主要是在系统运行中�随时接受用户的查询�同时也对用户的操作主动进行引导�它一般用help软件或者对话框的形式来提供联机帮助。28 第4章数据库系统基础复习题答案1�数据管理技术的发展经历了哪几个阶段�【解答】�人工管理阶段、文件系统阶段和数据库阶段。2�数据库技术的主要特点是什么�【解答】��1�采用复杂的结构化的数据模型��2�最低的冗余度��3�有较高的数据独立性��4�保证数据的完整性。3�数据的物理独立性的含义是什么�数据的逻辑独立性的含义是什么�【解答】�数据的物理独立性�概念模式和内模式之间的映像是数据的全局逻辑结构和数据的存储结构之间的映像�当数据库的存储结构发生了变化时�内模式将发生改变�但数据的逻辑结构可以保持不变�由此应用程序可以不必修改。数据的逻辑独立性�概念模式和外模式之间的映像是数据的全局逻辑结构和数据的局部逻辑结构之间的映像�当数据的全局逻辑结构发生了变化时�对不受该全局变化影响的那些局部而言�局部逻辑结构不必改变�因此根据这些局部逻辑结构所开发的应用程序也不必修改。4�根据所用数据模型的不同�比较流行的数据库系统可以分为哪三类�【解答】�层次数据库系统、网状数据库系统和关系数据库系统。5�什么是数据库系统�什么是数据库管理系统�它们之间是什么关系�【解答】�数据库系统由三部分组成�应用程序、数据库管理系统和数据库。数据库管理系统是管理数据的软件系统�它为用户或应用程序提供访问数据库的方法。它们之间的关系如下图所示�应用程序1应用程序2数据库数管理系统据┋库应用程序n6�解释外模式、内模式和概念模式。【解答】�外模式�又称子模式�是由用户视图中各种记录类型的相应定义所组成的�是用户允许使用的那部分数据的逻辑结构。概念模式�又称模式�是对数据库中全体数据的整体逻辑结构的描述�是所有用户的公共数据视图。它与具体的应用程序以及使用的程序设计语言无关。它除了定义数据的逻辑结构以外�还要定义与数据有关的安全性、完整性要求。内模式�又称存储模式�是最接近物理存储的一层�是数据库中最低一级的表达。29 7�举例分别说明实体集之间是1�1�1�n�m�n的联系。【解答】�机票与座位的联系是1�1。每一张机票对应一个座位�每一个座位对应一张机票。11机票座位学生与成绩的联系是1�n。每个学生有多个成绩�每个成绩对应一个学生。1n学生成绩学生与课程的联系是m�n。每个学生可以选修多门课程�每门课程可以被多个学生选修。mn学生课程8�关系是一个二维表�任意一个二维表是否就是一个关系�为什么�【解答】�不是。如果二维表中出现相同的行或同一列的值不是相同的数据类型就不是一个关系。9�举例说明传统的集合运算�并、差、交和笛卡尔积。【解答】�假设有两个关系�R和S。R商品编号商品名称生产厂家1001奶粉北京1005酱油天津1010饼干青岛S商品编号商品名称生产厂家1001奶粉北京1006醋天津1011曲奇青岛1022酒河北30 R∪S商品编号商品名称生产厂家1001奶粉北京1005酱油天津1010饼干青岛1006醋天津1011曲奇青岛1022酒河北R�S商品编号商品名称生产厂家1005酱油天津1010饼干青岛R∩S商品编号商品名称生产厂家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酒河北10�已知如下关系M�N�求M∪N�M�N�M∩N。【解答】�31 关系MABCa1b1c2a1b2c3a2b1c3关系NABCa1b2c3a2b1c2a1b3c2M∪NABCa1b1c1a1b2c3a2b1c3a2b1c2a1b3c2M�NABCa1b1c1a2b1c3M∩NABCa1b2c311�已知两个关系R、S。试求出RS的结果。B>D【解答】�RABCa4cb6dSDEF5e98d632 结果ABCDEFb6D5e912�已知两个关系G�H。试求出RS的结果。【解答】�GABCa6db3cd8ac4dHBD374849结果ABCDb3c7c4d8c4d913�对于表4-12�请用关系代数运算�查找��1�陈中金老师所教的学生的姓名。�2�选修英语的学生的年龄和成绩。�3�魏立同学选修的课程的名称和教师姓名。【解答】�教师情况关系T教师号教师姓名所属系T#TNTD203王朝阳数学301刘子咏物理411张梅外语504陈中金计算机507洪文源计算机33 课程关系C课程号课程名教师号C#CNT#21高等数学20331普通物理30141英语41151微机原理50452软件基础507学生情况关系S学生号学生姓名年龄T#SNSA9031林强199032高峰209033孙锺209034黄殷199035陆伟199036魏立209037蔡军20学生成绩关系SC学生号课程号成绩S#CNG903121A903141B903151B903221B903241A903251B903321B903331B903341A903431B903451A903452B903541A903551B903552B903621A34 903631B903652A903741B903751A903752A�1�①对T进行选择运算�条件是TN=陈中金�得到新的关系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。35 关系GSN林强黄殷陆伟蔡军�2�①对C进行选择运算�条件是CN=英语�得到新的关系A。关系AC#CNT#41英语411②把关系A和SC进行自然连接�得到关系B。关系BC#CNS#G41英语9031B41英语9032A41英语9033A41英语9035A41英语9037B③关系B在S#和G上投影�得到关系E。关系ES#G9031B9032A9033A9035A9037B④关系E和关系S进行自然连接�得到关系F。关系FS#GSNSA9031B林强199032A高峰209033A孙锺209035A陆伟199037B蔡军20⑤关系F在SA和G上进行投影的关系G。36 关系GSAG19B20A20A19A20B�3�①对S进行选择运算�条件是SN=魏立�得到新的关系A。关系AS#SNSA9036魏立20②把关系A和SC进行自然连接�得到关系B。关系BS#SNSAC#G9036魏立2021A9036魏立2031B9036魏立2052A③关系B在C#上投影�得到关系C1。关系C1C#213152④关系C1和关系C进行自然连接�得到关系D。关系DC#GNT#21高等数学20331普通物理30152软件基础507⑤关系D和关系T进行自然连接�得关系E。关系EC#CNT#TNTD21高等数学203王朝阳数学31普通物理301刘子咏物理52软件基础507洪文源计算机37 ⑥关系E在CN和TN上进行投影�得关系F。关系FCNTN高等数学王朝阳普通物理刘子咏软件基础洪文源14�FoxPro数据库文件中的字段有哪几种类型�【解答】�字符型�C�、数值型�N�、浮点型�F�、日期型�D�、逻辑型�L�和备注型�M�。15�建立数据库通常包含那些步骤�【解答】��1�建立数据库的结构�包括字段名、数据类型、宽度、小数位数�。具体操作如下�在命令窗口输入以下命令�create数据库名.dbf�并回车�待出现输入字段的窗口后�依次输入全部字段的有关内容。然后按下Ctrl+W�将库结构存盘。�2�输入数据库记录。具体操作如下�在命令窗口输入Insert命令或Appe命令插入记录或增加记录。16�在FoxPro中�DISPLAY和LIST命令有何异同�【解答】�两个命令都能显示数据库中的记录。DISPLAY命令如果不指定范围�则只能显示当前记录�LIST命令如果不指定范围�则显示全部记录。DISPLAY命令是逐屏显示�需按任意键再显示下一屏信息�而LIST命令没有周期性的暂停。17�在FoxPro中�SKIP和GO命令有何异同�【解答】�GO是绝对定位命令。它的作用是将当前的记录指针移到第N条记录。SKIP[]是相对定位命令。它的作用是将当前记录指针向前或向后移动N条记录。未加入任何参数的SKIP命令是把指针往末端移动一条记录。18�在FoxPro中�数据库的记录如何被删除�能否恢复被删除的记录�【解答】�首先用DELETE命令对想要删除的记录作上删除标记�然后用PACK命令将打上删除标记的记录删除。在没有用PACK命令之前�可用RECALL命令将打上删除标记的记录恢复�即去除删除标记。19�索引文件和排序文件有什么区别�【解答】�排序文件是将原数据库文件中的记录按指定关键字的升序或降序排序后的一个新的数据库文件。索引文件不是数据库文件�是建立一种“数据信息表格”�告诉Foxpro在以某种顺序进行索引时�记录之间的顺序是怎样的。20�在FoxPro中�索引文件有哪几类�它们是如何被打开的�38 【解答】�在FoxPro中�索引文件有两类�一类是扩展名为.IDX的索引文件。它可用三种方法打开。�1�索引文件在被建立的同时�它也就处于打开的状态了。�2�在打开数据库的同时打开索引文件。�3�用SETINDEXTO[<索引文件名表>|?][ADDITIVE]命令打开索引文件。另一类是扩展名为.CDX的复合索引文件。它是随着数据库文件的打开而自动打开的。21�在FoxPro中�查询记录有哪几种方法�分别是用在何种场合�【解答】�有两种方法�一是对单个记录的非索引查询。用在未索引的数据库中查找记录。二是对单个记录的索引查询。用在已建立索引的数据库中查找记录。22�在FoxPro中�两个数据库之间的关联性连接有几种�它们是如何建立的�【解答】�有两种。�1�“一对一”的关联性连接。用如下命令实现。SETRELATIONTO[<表达式>INTO<工作区>[�<表达式>INTO<工作区>…]][ADDITIVE]�2�“一对多”的关联性连接。用如下命令实现。SETSKIPTO[<工作区>[�<工作区>]…]上述两种关联性连接也可在View窗口中实现。23�什么是FoxPro中的范例关系查询�【解答】�范例关系查询不用打开多重数据库和建立关系等操作就可以对多个数据库中的数据做各种查询�查询结果可以显示在Browse窗口也可以送到一个指定的DBF文件�也可以送到打印机�也可以送到报表或标签。可用SELECT命令实现或通过RQBE对话框进行选择生成SELECT命令实现。39 第5章软件工程基础1�什么是软件危机�它和软件工程学是什么关系�【解答】�软件危机是指在计算机软件的开发和维护过程中遇到的一系列严重的问题。随着计算机硬件技术的进步�要求软件能与之相适应。然而�软件技术的进步一直未能满足形势发展提出的要求�最终导致了软件危机。软件危机所表现出的主要的问题有�(1)由于缺乏软件开发的经验和有关开发数据的积累�使得开发工作的计划很难制定�以致经常超出经费预算�进度计划无法遵循�完成开发的期限一再拖延。(2)软件需求在开发初期阶段不够明确�或未能得到确切的表达。开发工作开始后�软件人员和用户又未能及时交换意见�造成矛盾在开发后期集中暴露。(3)开发过程没有统一的、公认的方法论和规范进行指导�参加开发的人员各行其是。设计和实现过程的资料很不完整�使得软件很难维护。(4)未能在测试阶段充分做好检测工作�提交给用户的软件质量差�在运行中暴露出大量的问题。人们在认真地分析了软件危机的原因后�开始探索用工程的方法进行软件生产的可能性�即用现代工程的概念、原理、技术和方法进行计算机软件的开发、管理、维护和更新。于是�计算机科学技术的一个新领域——软件工程学诞生了。它在软件开发方法、工具、管理等方面的应用大大缓解了软件危机造成的被动局面。2�简述软件工程的定义和原理�【解答】�“软件工程学”是采用工程的概念、原理、技术和方法来研制、维护计算机软件的有关技术及管理方法。“软件工程学”的原理是��1�严格按照计划进行管理��2�坚持进行阶段评审��3�实行严格的产品控制��4�采用现代化的程序设计技术��5�结果要能清晰地审查��6�开发小组成员的素质要好�数量却不宜多��7�要承认不断改善软件工程实践的必要性。3�什么是软件生命期�它可以分为哪几个阶段�【解答】�同其他事物一样�软件也有孕育、诞生、成长、成熟、衰亡的生存过程�称为计算机软件的生命期。软件的生命期可分为6个阶段��1�制定计划阶段��2�需求分析阶段��3�软件设计阶段��4�编码阶段��5�测试阶段��6�运行和维护阶段�4�结构化分析方法怎样控制系统的复杂性�举例说明。40 【解答】�结构化分析方法控制系统复杂性的基本手段是“分解”和“抽象”�即“自顶向下�逐层分解”。先把分析对象抽象成为一个系统�然后自顶向下层层分解�使复杂的系统分解成足够简单、能够清楚地被理解和表达的若干子系统�然后分别理解系统的每一个细节、前后顺序和相互关系�找出各部分之间的数据接口。例如采用分层的数据流图的方法分析一个系统�顶层抽象地描述整个系统�底层具体地画出了系统的每一个细部�而中层则是从抽象到具体的逐步过度,就体现了分解和抽象的原则。5�结构化分析方法产生的系统说明书由哪几部分组成�【解答】�结构化分析方法产生的系统说明书由以下四部分组成��1�一套分层的数据流图�用以描述系统的组成和各部分之间的关系。�2�一本数据字典�用以描述系统的每一个数据。�3�一组小说明�用以描述系统的每一个细部。�4�补充材料。6�画出你所熟悉的一个系统的数据流图�并写出相应的数据词典和小说明。�1�考务系统简单的数据流图�1�顶层数据流图统计分析表不合格报名单报名单合格标准考生处理成绩清单考生系统考试中心准考证错误成绩清单考生通知单考生名单2�0层数据流图试题得分清单考生通知单报名单统计分析表不合12格报名登记报名统计单错误成绩清单单成绩准考证成绩清单考生名单考生名册合格标准3�1层数据流图之一41 准考证报名单1.11.2正式报1.3合格报名单登记报编准考名单登记名单证号考生不合格考生名单报名单考生名册4�1层数据流图之二成绩清单2.12.2正确成绩清单合格标准检查成审定合绩单格者错误成绩单正式成试题得分清单绩单考生通2.32.52.4知单制作通分析试分类统知单题难度计成绩考生名册难度分析表分类统计表�2�考务系统简单的数据字典�1�报名单=地区+序号+姓名+性别+文化程度+职业+考试级别+通信地址2�正式报名单=报名单+准考证号3�准考证=地区+序号+姓名+准考证号+考试级别4�考生名单={准考证号+考试级别}5�统计分析表=分类统计表+难度分析表6�考生通知单=考试级别+准考证号+姓名+合格标志+通信地址�3�考务系统简单的加工小说明�1�检查报名单——对考生的报名单进行有效性检查�打印出不合格报名单�产生合格报名单。2�考证号码——对合格的报名单编号�产生正式报名单。3�登记考生——打印准考证和考生名单�并将考生名单存入考生名册文件。4�检查成绩清单——检查成绩清单�打印错误成绩清单�产生正确成绩清单�并将考生成绩存入试题得分清单。5�审定合格者——输入正确成绩清单和合格标准�产生正式成绩清单。6�制作通知单——输入正式成绩清单�打印考生通知单。42 7�分类统计成绩——输入试题得分清单�进行成绩分类统计�按地区、年龄、文化程度、职业、考试级别等分类��产生分类统计表。8�分析试题难度——输入试题得分清单�分析试题难度�产生难度分析表。7�画出图书预订系统的数据流图�并写出相应的数据词典和小说明。���简单的图书预订系统的数据流图出版社档案文件图书目录文件书目、地址书名、出版社、价格对出版按出版社订单社订单检验汇总统计出版社顾客订单不合格订单正确订单订货存根用户信一批订单用状况顾客档案文件待处理订单文件订货存根文件图书预订系统的顶层数据流图���简单的数据字典:订单=用户名+书名+作者+出版社+数量+单价正确订单=订单+总价+支付方式一批书单={正确书单}对出版社订单=出版社名+{用户名+书名+作者+数量+单价+总价}+合计���小说明�1�验证订单正确性:读取订单信息和用户信用状况,如果用户信用状况良好,则核对图书目录文件,如果订单正确,则生成正确订单,并存入待处理订单文件;否则返回给用户不合格订单信息。2�出版社分类统计�读入一批订单和出版社档案文件�按出版社分类统计�生成各出版社的订单。8�对于写小说明的三种方式�在实际使用的时候�哪种情况下选用哪种方式�试举例说明。【解答】�除自然语言外�结构化分析方法写小说明的常用方法还有�结构化英语、判定表和判定树。在表达一个基本加工逻辑时�结构化英语、判定表和判定树常常被交叉使用�互相补充。判定树易学易懂且表达的是直观的图形表示�一目了然�易于同用户讨论。判定表最易进行逻辑验证�因为它考虑了全部可能的情况。结构化英语最易作为文档表示�且便于修改。在实际使用的时候�对于不太复杂的判断条件�或用判定表有困难时�使用判定树较好。对于较复杂的判定�组合条件较多�则使用判定表较好。而在一个加工逻辑中�如同时存在顺序、判定和循环时�使用结构化英语较好。下面就以商店业务处理系统中“检查发货单”为例�分别用三种方式表示。�1�结构化英语43 IFtheinvoiceexceeds$500THENIFtheaccounthasanyinvoicemorethan60daysoverdueTHENtheconfirmationpendingresolutionofthedebtELSEissueconfirmationandinvoiceENDIFELSEIFtheaccounthasanyinvoicemorethan60daysoverdueTHENissueconfirmation,invoiceandwritemessageoncreditactionreportELSEissueconfirmationandinvoiceENDIFENDIF�2�判定表1234发货单金额>$500>$500≤$500≥$500条件赊欠情况>60天≤60天>60天≤60天不发出批准书√作操发出批准书√√√发出发货单√√√发出赊欠报告√�3�判定树欠款>60天不发批准书金额>$500检查欠款≤60天发批准书,发货单发货单欠款>60天发批准书,发货单和欠款报告金额≤$500欠款≤60天发批准书,发货单9�软件设计的目的是什么�设计阶段产生的主要工作结果是什么�【解答】�软件设计是一个把软件需求变换成软件表示的过程。它主要确定系统“怎样做”,即将用户的要求转换成一个具体的软件系统的设计方案。设计阶段产生的主要工作结果是概要设计说明书和详细设计说明书�采用结构化设计方法时主要包括模块结构图和模块的功能说明。采用面向对象设计方法时�设计阶段产生的主要工作结果是一组相关的类。每个类都是一个独立的模块�既包含完整的数据结构�又包含完整的控制结构。这些类模块通过层次结构和类组合结构组成完整的应用框架。10�总体设计和详细设计有什么不同�为什么设计要分两步完成�44 【解答】:从工程管理的角度看�软件设计分为总体设计和详细设计�每一步骤考虑的详细程度有所不同。总体设计是在软件需求说明书的基础上建立软件的系统结构�包括数据结构和模块结构。而详细设计是过程设计�通过对结构表示进行细化�得到软件的详细的数据结构和算法。将软件设计分为总体设计和详细设计两个步骤�体现了软件设计中“抽象”的原则。总体设计建立起整个系统的体系结构框架和系统中的全局数据结构�它从系统全局的角度�考虑处理方式、运行方式、以及系统维护等方面的问题�奠定了整个系统实现的基础。没有总体设计�直接考虑程序设计�就不能全局把握软件系统的结构和质量�造成实现活动处于一种无序状态�程序划分不合理�导致系统处于一种不稳定的状态。11�模块化的优点是什么�从块内联系和块间联系的角度出发�应该选取怎样的模块结构。【解答】�软件系统的层次结构正是模块化的具体体现。将整个软件设计成若干功能单一、结构清晰、相对独立的模块�其优点是��1�简化程序设计的复杂度��2�提高系统的可靠性�使错误发生在模块内部�而不易扩散。�3�提高系统的开发效率。�4�提高系统的可维护性。�5�减少系统开发的工作量�对相同的功能可以通过模块调用实现。模块的设计应具有强内聚、弱耦合的特点。在软件系统结构中�模块的作用范围应在控制范围之内。尽可能减少高扇出结构。模块的大小要适中�功能要单一�并且模块的功能应是可预测的。模块的接口要简单、清晰�传递的参数数量不能太多�类型不要太复杂。12�确定下列模块之间的连接形式�指出它们的块间联系的类型和紧凑性。�1�打开文件�打印表头。�2�修改文件中的记录�并读取下一个记录。�3�编制各种报表�日报表、月报表、年报表。�4�检索一个文件并读出某个记录。�5�读出A之后�把A写入C�把A加到B中并验证B。【解答】�1�设根据打印表头的控制信息决定打印报表的种类�则模块�1�和模块�3�之间是控制耦合。连接程度高。2)设读出文件中的某个记录中包含A数据项�则模块�4�和模块�5�之间是数据耦合。连接程度低。3)其余模块之间为非直接耦合�无连接。13�现有模块A和B�其中A用于紧急处理�主要功能是�保留现场�关闭文件�中断程序运行�而B模块用来求解一个线性方程组�并对求得的各未知量求平均值�主要功能是�建立系数矩阵�矩阵求逆�解出未知量�求出平均值。试问模块A与模块B相比较�哪个模块的块内联系更紧密�为什么�【解答】�B模块的块内联系更紧密。因为B模块是一种顺序内聚�而A模块是一种时间内聚�所以B模块的块内联系比A模块更紧密。14�完成图书预订系统的数据流图的设计工作。45 图书预订系统输入分类统计订单输出对出版社订单检验订单输出不合格订单15�软件测试有哪些基本原则�【解答】�软件测试的基本原则是��1�最好由一个独立的部门或组织来测试软件系统。�2�测试用例应该由输入数据和预期的输出结果两部分组成。�3�不仅要选用合理的输入数据�还应该选用不合理的输入数据作为测试用例。�4�除了检查程序是否做了它应该做的工作外�还要检查程序是否做了它不应该做的事情。�5�长期保留所有测试用例�直到这个软件系统被废弃不用为止。�6�在对程序做了修改之后要进行再测试。�7�重点测试容易出错的程序段。16�白盒法和黑盒法有什么不同�它们各用于什么地方�【解答】�白盒测试法把程序看成是装在一个透明的白盒子中�既完全了解程序的结构和处理过程�并以此为基础设计测试用例�检查程序中的每条路径是否都能按照预定的要求正确工作。模块测试以白盒测试为主�辅之以黑盒测试�同时白盒测试也适用于对软件详细设计阶段的软件文档进行测试。黑盒法把程序看成一个黑盒子�即完全不考虑程序的内部结构和处理过程�只检查程序的功能是否能按照规格说明书正常使用�程序是否能够适当的接受输入数据�产生正确的输出信息�并且保持外部信息的完整性。黑盒测试主要用于联合测试和验收测试�除了测试程序外�还适用于对需求分析阶段的软件文档进行测试。17�设一个要被测试的源程序如下�floatsolut(x,y,z)floatx,y,z;{if(x>3&&y==2)z=1;if(x==4||z>3)z=z+1;returnz;}试设计测试用例�满足条件组合覆盖标准。46 【解答】�本题共有八中可能的条件组合�它们是�(1)x<3,y≠2(5)x≠4,z<3(2)x<3,y==2(6)x≠4,z>3(3)x>3,y≠2(7)x==4,z<3(4)x>3,y==2(8)x==4,z>3可以选择以下四组测试数据�使得上述八种组合至少出现一次�输入输出覆盖标准x=2,y=1,z=2x=2,y=1,z=2覆盖(1)(5)两种组合x=2,y=2,z=4x=2,y=2,z=5覆盖(2)(6)两种组合x=4,y=1,z=4x=4,y=1,z=5覆盖(3)(8)两种组合x=4,y=2,z=2x=4,y=2,z=2覆盖(4)(7)两种组合18�软件测试有哪几个步骤�简述每一步的目标和特点。【解答】�软件测试可分为以下三个步骤进行�模块测试、联合测试、验收测试。模块测试的目标是发现模块内部可能的各种错误�这些错误通常是在编码阶段产生的错误�因此为模块测试设计测试用例时多以白盒测试为主。联合测试是把各模块连接起来进行测试�测试的依据是模块说明书。联合测试可以查找与接口有关的错误�这一步的目标是发现设计阶段产生的错误。验收测试是把软件系统当作单一的实体进行的测试�验收测试的过程和结果应当是客观的且符合实际。因此验收测试应在软件投入后的实际环境下进行�并由用户主持进行�测试用例应为实际数据。验收的依据是系统说明书�这一步的目标是发现分析阶段的错误。19�软件维护的含义是什么�有哪几种类型的维护�【解答】�软件维护是指软件投入运行后�解决发生的各种故障�错误��增加其功能�使之适应新的环境等软件工程活动。主要分为以下四种类型的维护��1�改正性维护�为排除故障�使系统能正常运行�需要进行诊断和改正错误�这样的维护工作称为改正性维护.�2�适应性维护�为适应各种环境的变化而修改软件的维护工作�称之为适应性维护。�3�完善性维护�为满足用户的新需要�而对软件进行的修改和扩充�这样的维护工作称之为完善性维护。�4�预防性维护�为了改进软件未来的易维护性和可靠性�或者为了给未来的改进提供更好的基础而对软件进行的修改�称之为预防性维护。20�什么是“易维护性”�为什么“易维护性”是软件的一个重要的质量标准�【解答】�软件的易维护性是指软件易阅读、易发现和纠正错误、易修改扩充的能力。软件的易维护性是衡量软件的一个重要标准�这是因为随着软件规模的扩充和复杂性的增加�用于软件维护的成本不断的上升�同时由于合理的改错和修改要求不能及时满足而引起用户的不满�由于维护的副作用�在软件中引入新的错误而降低软件的可靠性等等�这些都说明软件维护的问题显得越来越重要。软件易维护性的三个特性�可测试性、可理解性和可修改性都是衡量软件质量的基本特性�因此软件的易维护性是软件的一个重要的质量标准�47 实验一至实验四的实验环境要求�TURBOC2.0上机步骤�以WINDOWS98为例�1�进入WINDOWS98�2�进入MSDOS方式�3�执行命令PDOS95�进入汉字系统�4�进入TURBOC2.0的集成环境。实验一�一�实验名称线性表的插入和删除�二�实验目的与要求掌握线性表在链接存储结构下的插入与删除运算�其数据是用随机数的方法来得到随机数。�三�程序清单#include#includetypedefstructss{intx;structss*next;}node;/*插入一个结点*/node*insert(node*head,inta){node*p1,*new;p1=head->next;new=(node*)malloc(sizeof(node));new->x=a;new->next=NULL;head->next=new;new->next=p1;returnhead;}/*删除一个结点*/node*dele(node*head,inta){node*p1,*p2;p1=head->next;p2=head;if(head->next==NULL){printf("shibai!");returnhead;}else{while(a!=p1->x&&p1->next!=NULL){p2=p1;p1=p1->next;}if(a==p1->x&&p1->next!=NULL){p2->next=p1->next;free(p1);}if(a==p1->x&&p1->next==NULL){p2->next=NULL;free(p1);}}returnhead;}/*显示链表*/voiddisplay(node*head){node*p1;printf(“链表如下�n”);p1=head->next;while(p1){printf("%d",p1->x);p1=p1->next;}printf("n");}/*主函数*/main()48 {intw,n,i;node*head;head=(node*)malloc(sizeof(node));head->next=NULL;printf("输入数据的个数:");scanf("%d",&n);for(i=1;i<=n;i++){w=rand();/*用函数rand()随机产生一个整数*/head=insert(head,w);}display(head);printf("插入一个数:");scanf("%d",&w);head=insert(head,w);display(head);printf("删除一个数�");scanf("%d",&w);head=dele(head,w);display(head);getch();}实验二�一�实验名称二叉排序树�二�实验目的与要求掌握二叉树的链式存储结构�二叉树的遍历方法和二叉排序树的查找方法。�三�程序清单#includetypedefstructnode{intkey;structnode*lchild,*rchild;}BSTNode;/*插入一个结点*/BSTNode*insertBST(BSTNode*Tptr,intkey){BSTNode*f,*p=Tptr;while(p){if(p->key==key)returnTptr;f=p;p=(keykey)?p->lchild:p->rchild;}p=(BSTNode*)malloc(sizeof(BSTNode));p->key=key;p->lchild=p->rchild=NULL;if(Tptr==NULL)Tptr=p;elseif(keykey)f->lchild=p;elsef->rchild=p;returnTptr;}49 /*建立二叉排序树*/BSTNode*CreateBST(){BSTNode*T=NULL;intkey;scanf("%d",&key);while(key){T=insertBST(T,key);scanf("%d",&key);}returnT;}/*遍历二叉排序树*/voidinorder(BSTNode*T){if(T){inorder(T->lchild);printf("%d",T->key);inorder(T->rchild);}}/*查找*/BSTNode*serchBST(BSTNode*T,intkey){if(T==NULL||key==T->key)returnT;if(keykey)returnserchBST(T->lchild,key);elsereturnserchBST(T->rchild,key);}/*主函数*/main(){BSTNode*BSTree,*p;inta;BSTree=CreateBST();inorder(BSTree);printf("n");printf(“输入待查找的关键字�”);scanf(“%d”,&a);p=serchBST(BSTree,a);if(p==NULL)printf("Nofind!n");elseprintf("%dn",p->key);}实验三�一�实验名称排序�二�实验目的与要求掌握选择排序法、冒泡排序法和快速排序法。�三�程序清单/*选择排序*/voidxzsort(intp[],intn){inti,j,min,t;for(i=0;ip[j])min=j;50 if(i!=min){t=p[min];p[min]=p[i];p[i]=t;}}}/*冒泡排序*/voidmpsort(intp[],intn){inti,j,t;for(i=0;ip[j+1]){t=p[j];p[j+1]=p[j];p[j]=t;}}}/*快速排序*/voidkssort(intp[],intlow,inthigh){intpivotpos;if(lowpivot)j--;if(ikey)high=mid-1;elselow=mid+1;}printf("NoFind!n");}/*主函数*/main(){intp[10]={1,2,4,5,7,9,10,25,34,78};intx;seqsearch(p,10,x);binsearch(p,10,x);printf(“输入待查找的数�”);scanf(“%d”,&x);printf(“线性查找的结果�”);seqsearch(p,10,x);printf(“二分查找的结果�”);binsearch(p,10,x);}实验五�一�实验名称数据库的建立�二�实验目的与要求52 设计一个职工情况的数据库�其内容要包括职工的工号、姓名、性别、出生年月、婚姻状况、工资、职工和简历。输入若干记录。�三�实验步骤1�进入foxpro的集成环境2�在命令窗口�command窗口�中执行命令modicomm.Jianku.prg出现程序文件的编辑窗口�然后依序键入如下命令Createtable职工(工号char(4),姓名char(8),性别char(2),出生年月date,婚姻状况Logical,工资Numeric(8,2),职称char(12),简历Memo)appeappeappeappeappeappecloseall3�存盘4�在命令窗口�command窗口�中执行命令dojianku.prg实验六�一�实验名称数据库的索引�二�实验目的与要求对职工情况的数据库�分别建立按“工号”、“年龄”、“职称”、“工资”的索引文件。�三�实验步骤1�进入foxpro的集成环境2�在命令窗口�command窗口�中执行命令modicomm.Jiansy.prg出现程序文件的编辑窗口�然后依序键入如下命令use职工indexon工号toghlistindexon出生年月tonllistindexon职称tozclistindexon工资togzlistcloseall3�存盘4�在命令窗口�command窗口�中执行命令doJiansy.prg53'