严飞_《软件技术基础》沈被娜习题解答.doc 31页

'第二章2.1什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法。所以算法是程序的一个要素。2.3何谓频度，时间复杂度，空间复杂度？说明其含义。频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。2.4试编写一个求多项式Pn=anxn+an-1xn-1+a1x+a0的值Pn(x0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。A=(a0,a1……an)mul＝1//sum=a0fori=1tonmul＝mul*x//xsum=A[i]*mul+sum//求和end(i)进行了n次时间复杂度为：2n2.5计算下列各片段程序中X←X+1执行次数(1)fori=1tonforj=1toifork=1tojx←x+1end(k)end(j)end(i)执行次数：n*n*n (2)i←1whilei=c//找到第1个大于等于c的元素s=iift==-1andL[i]>d//找到第1个大于d的元素t=i;end(i)ifs!=-1andt!=-1i=swhileinthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A，B两个线性表的元素个数为m，nIf(m<=n)then{return}Fori=0ton-1a=A[i]forj=0tom-1if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B为A的子集}return 2.11写一个将向量L（a1，a2，an）倒置的算法。a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15对L(a1，a2,......,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，n-5交换7，8交换7，n-6交换8，7交换？8，n-7交换？停止！！！！小结：n个元素倒置的算法是，i=1while(ilchild)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=newBiTNode;T->data=item;T->lchild=lptr;T->rchild=rptr;returnT;}//GetTreeNode(2)在这里要对一种情况进行说明当root1的左子树与root2的左子树相同，root1的右子树与root2的右子树相同时，这两颗二叉树相同。当root1的左子树与root2的右子树相同，root1的右子树与root2的左子树相同时，这两颗二叉树同样相同。 以下是实现代码bool IsBSTEqual(BNode* root1,BNode* root2)  {        if (root1==NULL && root2==NULL)        {             return true;        }        else if (root1==NULL || root2==NULL)        {             return false;        }        else        {              if (root1->data != root2->data)              {                    return false;              }                bool is_left = IsBSTEqual(root1->left,root2->left);              bool is_right = IsBSTEqual(root1->right,root2->right);                if (is_left&&is_right)                   return true;                else              {                    is_right = IsBSTEqual(root1->right,root2->left);                    is_left = IsBSTEqual(root1->left,root2->right);                      if (is_left&&is_right)                         return true;                    else                         return false;              }        }    }  3）4） 计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加1，空树返回-1.structTree{ ElementTypeElement; Tree*left; Tree*right;};intCountLeaf(Tree*T){ staticintcount=0; if(T!=NULL) {  CountLeaf(T->left);  CountLeaf(T->right);  if(T->left==NULL&&T->right==NULL)   count++; } returncount;} intDepth(Tree*T){ intdepthLeft,depthRight,depth; if(T==NULL)  return-1; else {  depthLeft=Depth(T->left);  depthRight=Depth(T->right);  depth=1+(depthLeft>depthRight?depthLeft:depthRight); } returndepth;}2.32.给定一组元素{17,28,36,54,30,27,94,15,21,83,40},画出由此生成的二叉排序树。83283040219454361517解： 272.33．给定一组权值W={8,2,5,3,2,17,4},画出由此生成的哈夫曼树。223451782.34.有一图如题图2.4所示：（1）写出此图的邻接表与邻接矩阵；（2）由给点V1作深度优先搜索和广度优先搜索；（3）试说明上述搜索的用途。2 101820191716151314121197846531解：（1） ^8521^10312^12243^14534^6415^15756^171867^157118^181089^119210 ^19121011^1311312^20141213^1513414^1614615^20171516^1816717^1917918^20181119^19161320（2）V1作深度优先搜索:V1作广度优先搜索:(3)为了避免同一顶点被多次访问。2.35.有一又向图如题图2.5所示：51624 3（1）写出每一结点的入度和出度各为多少；（2）写出上图的邻接矩阵和邻接表。解：V1:入度=3出度=0V2:入度=2出度=2V3:入度=1出度=2V4:入度=2出度=2V5:入度=2出度=1V6:入度=0出度=4^1^53123456^14^2^45^216^3.36求题图2.6中结点a到各结点之间最短路径。hfgedcba2222 1233141解：2.37求题图2.7中所示AOV网所有可能的拓扑顺序结果。解:21738546 V1V2V3V4V5V600000138^68^4^8^V70V800^^8^4^拓扑排序：V7->V5->V2->V4->V6->V3->V1->V82.38题图2.8所示AOE网，求:(1).每一事件最早开始时间和最晚开始时间;(2).该计划最早完成时间为多少。解:活动最早最迟开始时间a1a2a3a4a5a6a7a8a9a10a11a12a13a14E00566121212191916202325L409616121916191923202325L-E404010074007000事件最早最迟开始时间V1V2V3V4V5V6V7V8V9V10VE05612191620232527VL096121923202325272.39画出进行分块查找的数据组织形式。解:设将数据分成4块，每块中记录个数5，先查找索引值97451975179752897543第1块23497321,97421,97451,97241,9711897250,97407,97239,97227,9751797438,97102,9752897136,0733897543,97309 2.40画一棵对20个记录进行对分查找的判定树,并求等概率情况下的平均查找长度。ASL=(1+2*2+3*4+4*8+5*5)/20=3.72.6数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。2.5试比较顺序表和链表的优缺点。1.线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。2.线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。3.采用的算法语言：线性链表要求所使用的语言工具提供指针类型变量。2.6试比较单向链表与双向链表的优缺点。1.单向链表只能单方向地寻找表中的结点，双向链表具有对称性，从表中某一给定的结点可随意向前或向后查找。2.在作插入、删除运算时，双向链表需同时修改两个方向上的指针，单向链表则简便些。2.7试说明树与二叉树有何不同？为何要将一般树转换为二叉树？树与二叉树区别：树是由n个（n>=0）结点组成的有限集合T，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。 二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。2.8若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。解：二叉排序树为：806100901072582.9对于关键字序列{49，38，65，97，76，13}，回答下述问题。（共12分）（1）写出一趟冒泡排序的结果。（6分）（2）写出一趟快速排序的结果。参考答案如下：（1）写出一趟冒泡排序的结果。（6分）{38,49,65,76,13,97}（2）写出一趟快速排序的结果。（6分）{13,38,49,97,76,65}2.10请给出图1的所有最小生成树。（10分）aebdfc1238665图1 答：共有两颗：aebdfc12365aebdfc1236652.11请给出图2的所有拓扑排序序列。（16）图2abdfgceh答案如下：仅有两个第一个：abcdefgh第二个：abcdegfh2.12已知某二叉树的前序遍历序列为：ABCDEFG和中序遍历序列为：CBEDAFG。请画出该二叉树。答案如下： 2.13构造该图的最小生成树。aefgdbhc21111222243图的最小生成树如下aefgdbhc2111122 第三章3.1操作系统的基本功能是什么？它包括哪些部分？基本功能：操作系统应该具有处理器管理，存储管理，设备管理和文件管理功能，同时，为了使用户能方便地使用机器，操作系统还应提供用户接口功能。构成部分：（1）.对CPU的使用进行管理的进程调度程序。（2）.对内存分配进行管理的内存管理程序。（3）.对输入输出设备进行管理的设备驱动程序。（4）.对外存中信息进行管理的文件系统。3.2试说明虚拟机的概念以及实现的方法。在裸机外面每增加一个软件层后就会变成一台功能更强的机器，我们通常把这种计算机系统称为虚拟机。虚拟机的实现方法：在裸机上装上操作系统对机器进行首次扩展，再在操作系统的基础上增加其他软件，这样就可以实现“虚拟机”。3.3通常操作系统有哪几种基本类型？各有什么特点及适用于何种场合？三大类：（1）多道批处理系统：计算机内存中同时可以存放多道作业，用户与作业之间没有交互作用，用户不能直接控制作业的运行。此类系统一般用于计算中心等较大型的计算机系统中。（2）分时系统：多个用户通过终端分享同一台计算机，并通过终端直接控制程序运行，进行人与机器之间的交互。此类系统适用于程序的开发。（3）实时系统：对外部发生的随机事件作出及时的响应，并对它进行处理。此类系统一般用于工业控制系统或事物处理系统。3.4试说明你所使用过的操作系统的类型和特点。Windows系统：多用户多任务操作系统。特点：全新的、友善的用户界面。提供了功能强大的应用程序。具有多任务并行处理能力，各种应用程序之间可以方便地进行切换和交换信息。具有强大的内存管理能力，支持扩展内存功能，提高系统运行效率。3.5解释名空间、作业地址空间和存储空间的关系以及逻辑地址和物理地址的区别。存放源程序的空间称为名空间。当汇编或编译程序将源程序转换成目标程序后，一个目标程序所占有的地址范围称为地址空间，这些地址的编号是相对于起始地址而定的，一般定起始位零，称为逻辑地址或相对地址。存储空间是指当目标程序装入主存后占用的一系列物理单元的集合，这些单元编号称为物理地址或绝对地址。3.6什么是重定位？静态重定位和动态重定位的区别是什么？各举一例说明。 当用户程序要调入内存时，必须把相对地址转换为绝对地址，同时要包括对程序中与地址有关的指令进行修改，这一过程称为重定位。静态重定位是在程序装入时进行，一般通过处理机中一对界地址寄存器来实现。动态重定位是在程序执行过程中进行的，当处理器访问主存指令时由动态变换机构自动进行地址转换。3.7存储管理器的功能是什么？为什么要引入虚拟存储器的概念？虚存的容量由什么决定？存储管理的功能主要分为：内存分配、地址转换、存储保护和内存扩充。虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。虚存的容量受两个条件约束：指令中地址场长度的限制、外存储器容量的限制。3.10什么是作业、作业步和进程？作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做的集合。一个作业是由一系列有序的作业步所组成。一个作业步运行的结果产生下一个作业步所需的文件。进程可以看成是程序的一次执行，即是在指定内存区域的一组指令序列的执行过程。3.11处理器管理主要解决什么问题？在大型通用系统中，可能数百个批处理作业存放在磁盘中，又有数百个终端用户与主机联接，如何从这些作业中挑选一些作业进入主存运行，又如何在主存各进程间分配处理器，是操作系统资源管理的一个重要问题，处理器管理就是用来解决此问题的。3.12什么是进程的同步和互斥？什么是临界区？“同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们相互之间必须协调配合。“互斥”是指当多个进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排它性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。如果在两个进程P1、P2中加入P、V操作后，可以实现对公用变量count的互斥使用。其中P（s）、V（s）之间的程序段称为临界区。3.15进程间的通信可以由哪些方式进行？低级通信方式：P-V操作。高级通信方式：直接通信、信箱通信。3.16死锁产生的必要条件是什么？死锁的预防、避免和检测各有什么不同？各举一种相应的方法。死锁产生的必要条件有：1.所涉及的资源是非共享的；2.进程在等待新资源时，继续占用已分配到的资源；3.一个进程占有的资源不能被别的进程强行抢占；4.一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。死锁的预防是研究如何破坏产生死锁的必要条件之一，从而达到不使死锁发生地目的。死锁的避免与死锁的预防区别在于，死锁的 预防是严格破坏形成死锁的必要条件之一，使得死锁不在系统中出现。预防方法之一，采用假脱机技术将非共享设备变成共享设备来实现。而死锁的避免并不严格限制必要条件的存在，因为必要条件存在并不一定产生死锁。而进程推进顺序不当，也可以导致系统发生死锁，因此死锁的避免是考虑万一当死锁有可能出现时，就小心地避免这种情况的最终发生。避免方法有采用相应的银行算法和方法。死锁的检测和恢复，这是一种变通的方法，它允许死锁的发生，但能在适当时间检测出来，并设法进行恢复。利用化简进程-资源有向图的方法来检测系统在某一特定状态时是否处于死锁状态。3.17通道、控制器和设备的各种不同连接方式各有什么特点？第一种连接方式（书中图3.41（a））：控制器与设备是一一对应的，当系统对某设备提出申请时，CPU将设备号及有关操作要求传递给通道，由通道启动该设备，并完成对该设备的操作。第二种连接方式（书中图3.41（b））：是一个控制器控制若干个设备，只有当被申请的设备及相应的控制器均为空闲状态时才能启动。第三种连接方式（书中图3.41（c））：是同道、控制器与设备交叉连接，提高了控制的灵活性，但必须在相应的设备、控制器、同道均为空闲时才能工作。3.18什么是“瓶颈”问题？引入缓冲区为何可以解决这一问题？系统中的独占类型设备，只能由单个作业独占，这样使其他需要改设备的进程由于等待设备而被阻塞，称为系统的“瓶颈”。缓冲技术是指在内存中划出一个由n个单元组成的区域，称为缓冲区，作为外部设备在进行数据传输时的暂存区。引入缓冲技术的根本原因是CPU数据处理速度与设备传输数据速度不相匹配，利用缓冲区来缓解其间的速度矛盾，减少瓶颈现象。3.19设备管理的功能是什么？怎样把一台物理设备虚拟为多台设备？设备管理的功能：设备驱动程序；即插即用；通用即插即用；集中、同一管理；添加硬件。通过虚拟机软件，就可以在一台物理计算机上模拟出一台或多台虚拟的计算机。3.20什么是记录、文件、文件系统？记录：文件由若干个记录组成，每一个记录是一些相关信息的集合。文件：在逻辑上具有完整意义的数据或字符序列的集合。文件系统：负责存取和管理文件的机构，又称为文件管理系统。3.21文件的逻辑结构和物理结构有何区别？文件的存储方式与文件的存取有何关系？文件的逻辑结构是从用户的角度看到的文件面貌，也就是它的记录结构。文件的物理结构是指一个逻辑文件在外存储器上的存放形式。各种文件应用场合不同，对文件的存取要求也就不同，对应不同的存取方式，对文件的物理结构即存储方式有不同的要求3.22什么是文件目录？有几种目录结构形式？各有什么特点？ 为了便于对文件进行存取和管理，所有计算机系统都设置一个文件目录，每个文件目录中都有一个表目，存放描述该文件的有关信息。通常有一级目录、二级目录和多级目录结构。一级目录：把系统中所有文件都建立在一张目录表中，整个目录结构是一个线性表，所以查找的时间会增加，不允许用户对不同的文件取相同的名字，主要用于单用户的操作系统中。二级目录：在主目录文件中每一个用户有一个表目，指出各用户文件目录的所在位置，而各用户文件目录才指出其所属各具体文件的描述信息，不同用户的文件可以起相同的名字。多级目录：是树形结构，每一个结点出来的分支可以是文件，也可以是下一级，在一定时间内以某一级目录作为当前目录，用户只需从“当前目录”查看即可。3.23文件的共享与安全保密问题如何解决？共享的实现：通过文件路径实现共享；通过联接实现共享。保密问题的解决：采用存取控制矩阵方法；采用按用户分类的存取控制的方法；采用口令设置。3.24什么是文件操作指令？每个命令的具体功能是什么？文件操作指令：是指文件系统提供给用户的一系列操作使用命令，其中最基本的命令是查询文件目录。建立文件：当用户需要将其信息作为文件保存时，向系统提出建立文件指令，系统按照用户提供的参数为该文件建立一个表目，放入相应的文件目录中。打开文件：当用户需要访问文件中某个记录时，首先要进行打开文件操作，此时系统将欲访问的文件表目从目录文件调入活动文件表中。读文件：把文件中相关的记录从外存储器的文件区中读入主存用户工作区中。写文件：把用户要求插入、增加或删除的记录写入文件区相应位置。关闭文件：文件暂时不用时，必须将它3.253.26操作系统与用户的接口有几种？各有什么特点？试举例说明你所使用过的接口形式。通常操作系统为用户提供两种接口：一类是程序接口；另一类是作业控制方面的接口。程序一级接口是由一组系统调用命令组成，它是操作系统提供给用户的各种服务，以子程序的形式供用户在程序中调用。当程序执行该系统调用命令时便暂时中断当前执行的程序去执行该系统调用命令子程序，完成后自动返回当前执行程序。 作业控制方面的接口与操作系统的类型有关。在批处理系统中，当用户一旦提交了作业，就无法对作业的运行作更多的控制，因此用户必须事先用该操作系统提供的作业控制语言告诉操作系统对进程的运行意图、资源的需求以及一旦出现问题作何种选择等。对于分时系统，则提供一组操作命令，通常称为语言命令，它采用人机交互回话方式来控制作业的运行。我所使用的WindowsXP操作系统中，用户通过键盘操作，也可以在多窗口图形化环境中通过鼠标器选择各种操作。第六章6.1简要回答下列问题：（1）软件生命周期为什么要划分成阶段？应怎样来划分阶段？在软件开发过程中，为什么要强调文档编写？在运用工程的方法来进行软件开发时，必须遵守一些工程性的基本原则：分解、计划、规范。相应的软件工程的一些基本原则包括软件周期的划分，这要求在时间上进行分解，即将软件开发过程分解为一系列的分阶段的任务。这也有利于降低软件开发的难度。一般来说，软件从产生、发展到淘汰要经历定义、开发和维护三大阶段。具体地来说，即定义阶段的可行性论证与开发计划、需求分析，开发阶段的概要计、详细设计和编码，维护阶段的测试、运行维护。强调文档的编制是因为它有以下主要作用：a.作为开发人员在一定阶段内承担任务的工作结果和结束标志。b.向管理人员提供软件开发工作的进展情况，白软件开发过程中的一些“不可见”的事物转换成“可见”的文字资料，以便管理人员在各个阶段检查开发计划的实施情况，使之能够对工作结果进行清晰的审计。c.记录开发过程中的技术信息，以便协调工作，并作为下一阶段工作的基础。d.提供有关软件维护、培训、流通和运行信息，有助于管理人员、开发人员、操作人员和用户之间的工作了解。e.向未来用户介绍软件的功能和能力，使之能判断该软件能否适合使用者使用。（2）什么是模块的内聚和耦合？它们与软件的可移植性、软件结构有什么关系？内聚是对模块内各个元素彼此结合的紧密程度的度量。耦合是对一个软件结构内不同模块之间互联程度的度量。越松散的耦合越紧密的内聚越有利于软件的可移植，软件的结构性越好。（3）什么是黑盒测试和白盒测试？应该由软件开发者还是用户来进行确认测试？为什么？ 黑盒测试也称为功能测试或数据驱动测试。它把程序看成是一个黑盒子，完全不考虑程序的内部结构和处理过程，只对程序的接口进行测试，即检查程序是否能使当地接收输入数据并产生正确的输出数据。白盒测试是把程序看成是一个透明的盒子，也就是完全了解程序的结构和处理过程。软件测试工作不应有开发软件的个人或小组承担，用户可以参与，但更主要的是应该由其他懂软件工程的人员来测试。统计显示开发者发现自己错误的概率很小。（4）软件的可维护性与哪些因素有关？在软件开发过程中应采取什么措施才能提高软件产品的可维护性？通常影响软件可维护性的因素为系统的大小、系统的年龄、结构的合理性。措施：使用有可维护性的程序设计语言、及时更新文档、使用先进技术和工具、明确软件质量目标、明确质量保证工作。（5）软件质量与哪些因素有关？怎样保证软件产品质量？在高层模型中，质量因素由八个元素组成：正确性、可靠性、效率、安全性、可使用性、可维护性、灵活性、连接性。可采取以下措施来保证软件的质量：技术审查、管理复审、测试。（6）面向对象方法与结构化生命周期法有什么区别？面向对象方法的基本原则是什么？面向对象方法的本质是强调从客观世界中固有的事物出发来构造系统，即面向对象。结构化方法主要是面向过程的，也就是在分析设计时更多地从过程处理的角度进行。面向对象的基本原则：1.开闭原则2.依赖倒转原则3.里氏代换原则4.合成/聚合复用原则5.迪米特原则6.接口隔离原则6.2'