软件基础题库(全)

精品教育第一章 软件工程1、填空1）软件包含_以及开发、使用和维护程序需要的所有文档。 （程序）2）为了解决软件危机问题，在1968年北大西洋公约组织会议上提出了_这个名词。（软件工程）3）软件工程的传统途径是_方法学。（生命周期）4）软件生命周期方法把软件开发划分为3个大阶段，软件开发，_，淘汰。（软件维护）5）瀑布模型从_角度对软件开发和维护的复杂问题进行分解，把软件生命的漫长周期划分为各个阶段。（时间）6）软件开发中经常使用_法 ，使用户通过实践获得关于未来的系统如何工作的更直接具体的概念，它类似于工程产品的开发中使用样机的思想。（快速原型法）7）_综合了生命周期模型和原型模型的特点，同时增加了风险分析环节来弥补两者的不足。（螺旋开发模式）8）OOA是_的缩写。（面向对象分析）9）_（组件）是一种能够提供某种服务的自包含的软件模块,它封装了一定的数据 （属性）和方法,并提供特定的接口，开发人员利用这一特定的接口来使用组件,并使其与其它组件交互通讯,以此来构造应用程序。 10）生命周期法中，问题定义阶段主要要搞清楚的是：_。（系统要解决的关键问题是什么）11）可行性研究的目的就是用最小的代价在尽可能短的时间内确定_。（问题是否可以解决）12）_和数据字典是描述数据系统逻辑模型的有力工具。（数据流图）13）ER模型包含“实体”、“联系”和_等三个基本成分。（属性）14）系统设计阶段的目标是把系统分析阶段确定的逻辑模型向_模型转化。（物理）15） 是将需求分析阶段获得的系统功能规格说明书转换成具体的计算机可实现的目标系统的一个过程，是软件开发设计的第一个阶段。它主要考虑软件的总体结构。（概要设计阶段）16）系统设计分概要设计和 设计两个阶段。 （详细）17）从对软件的可维护性、可靠性和可理解性等要求来看，模块应尽可能独立，模块之间的关联和依赖程度尽可能 ，使它们之间的接口尽量简单。（小）18）衡量模块独立性强弱的两个定性指标分别是耦合性和_性。 （内聚）19）_是指模块内部个成分之间联系的强弱。 （内聚）20）_表示模块间相互关联的程度，它表现了模块的外部特征。 （耦合）21）模块之间的耦合有数据耦合、控制耦合、公共耦合、内容耦合，其中_耦合的耦合程度最高。 （内容）22）概要设计阶段重要任务是设计_的模块。 （高内聚低耦合）23）_是按自顶向下进行软件系统总体设计的思想发展而来的，是以数据流为基础、自顶向下、逐步求精和模块化的一个过程。该方法也被称为面向数据流的设计方法。 （结构化程序设计）24）数据流图大致可分为两种类型：变换型和_。（事务型）25）文风良好的程序中_行占整个程序文件的三分之一到一半、甚至更多。（注释）26）文风良好的程序中不同的程序单元应用_行隔开。 （空）27）大型软件系统的测试阶段通常分为四个步骤进行，首先进行的是单元测试，然后依次进行集成测试、 和系统测试。（验收测试）28）静态测试方法包括计算机辅助静态分析方法和 测试方法。（人工）29）动态测试方法有白盒测试方法、黑盒测试方法和 等。（穷举测试）30）设计测试用例时，不但应包括对有效的和期望的输入条件进行测试，也应包括对 进行测试。（无效的和非期望的输入条件）31）常用的黑盒测试方法有等价划分法， ，错误推测法等3种。（边界值法）32）在进行单元测试时，须建立一个单元测试环境，即设置若干辅助测试模块，来模拟其他模块与被测试模块之间的关系。因此要设计两类辅助测试模块，他们是驱动模块和桩模块。驱动模块用以模拟被测试模块的 级调用模块。（上） 33）集成测试的方法主要有两种：非渐增式测试和 。（渐增式测试）34）验收测试通过一系列 测试以表明软件符合需求规格说明书要求。（黑盒）35）软件测试的目的是 。（尽可能多地发现程序中的错误）36）软件调试的目的是 。（定位错误的位置并改正）37）软件维护工作占到软件生命周期中开发人员所花费工作量的 左右。 （60%）38） 是指在软件交付使用后，为了改正错误或满足新的需求而修改软件的过程。（软件维护）39）为了满足用户新增功能或修改已有功能的建议而进行的维护称之为 。（完善性维护） 40）把诊断和改正软件错误的过程称为_。（改正性维护）2、简答1)、与传统生命周期相比，采用原型模型的主要理由是什么？2）什么是软件危机？软件危机出现后的具体表现有那些？3）概要设计阶段的主要任务有哪些? 4）大型软件系统的测试阶段的通常分为哪几个步骤进行？简述每个步骤所做的主要工作。5）简述软件生命周期法划分为几个阶段。6）简述结构化分析方法的基本思想。7）调试有什么方法和原则？8）选择测试数据的基本原则是什么？9）软件设计分那两步？每一步的任务是什么？10）有哪几种类型的软件维护工作？软件工程部分简答题答案6）简述结构化分析方法的基本思想。结构化分析方法（SA）的基本思想是：对于一个复杂的系统，按照其内部数据的流动和处理过程，采用“抽象”和“分解”的手段，首先“抽象”得到系统的高层逻辑模型，之后采用自顶向下逐步求精的方法，对系统逻辑模型逐层不断“分解”细化，直到不能再细化为止，即可得到系统最底层的详细逻辑模型。对系统结构化分析的成果通常采用数据流图和数据字典来表示。7）调试有什么方法和原则？软件调试的常用方法有：试探法、回溯法、对分查找法、归纳法和演绎法。试探法根据错误征兆猜想出错的位置并进行调试；回溯法根据错误征兆人工沿程序控制流逆向往回追踪源程序代码，直到找出错误或确定故障范围为止；对分查找法根据程序中关键变量在某些位置的正确值，将错误范围迅速缩小到该位置之前或之后的一半范围，重复此过程直到把错误范围缩小到易诊断或能够直接确定为止；归纳法根据错误征兆导出错误出处的假设并证明假设以得出结论；演绎法根据错误征兆设想所有可能的原因，之后通过数据分析排除矛盾的假设，最后证明剩余的假设以确定结论。调试的原则：最有效的调试方法是用头脑分析与错误征兆有关的信息；只把调试工具当做辅助手段来使用；避免使用试探法，只将其作为最后采用的手段；在出现一个错误的地方，很可能还有别的错误；当心修正一个错误的同时引入新的错误。8）选择测试数据的基本原则是什么？选择测试数据的总的原则是：用尽可能少的测试数据发现程序中尽可能多的错误。在白盒测试方法中选择数据的基本原则是：从用户角度只按照程序功能选择测试数据；不但应包括对有效的和期望的输入数据进行测试，也包括对无效和非期望的数据进行测试，以确定系统是否具有足够的健壮性。白盒测试方法中选择测试数据的基本原则是：根据被测试程序的逻辑结构选择测试数据，按照测试要求选择相应的覆盖技术以达到所需的覆盖强度。第二章 数据结构概述1、填空1）若一个算法的时间复杂度用T(n)表示，其中n的含义是_。2）将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为_。3）具有非线性结构的数据结构有_。4）在线性表的顺序存储结构上实现查找某个关键字X的平均时间复杂度,与在单链表结构上实现查找某个关键字X的平均时间复杂度比起来_。（高、低、相同）5）数据的逻辑结构是从逻辑关系上描述数据，它与数据的_无关，是独立于计算机的。6）_是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。7）算法是对特定问题求解步骤的一种描述，它是_的有限序列。8）算法的重要特性有_、确定性、可行性、输入和输出。9）算法的重要特性有穷性、_、可行性、输入和输出。10）算法的重要特性有穷性、确定性、_、输入和输出。11）算法的重要特性有穷性、确定性、可行性、_、和输出。12）算法的重要特性有穷性、确定性、可行性、输入和_。13）_是指所有能被输入到计算机并能被加工处理的信息的集合。14）数据元素是数据处理的_。数据项是数据处理的最小单位。15）_是指数据元素及其相互关系。16）（ ）是指数据处理的最小单位。17）_通常用来衡量算法的优劣，根据算法编制成程序后，是程序在计算机上运行时所消耗的时间。18）空间复杂度用来衡量程序在计算机上运行时所占的存储单元，其中主要考虑运行时所需要的_。19）程序for(i=1;i=n;i+) x=x+1； 时间复杂度是_。20）在数据结构中，经常采用的存储结构有线性存储结构和_。第三章 顺序表一、填空1若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用（ ）存储结构最节省运算时间。2顺序存储结构的线性表中所有元素的地址（ ）连续。 3顺序存储结构的线性表其物理结构与逻辑结构是（ ）的。4在具有n个元素的顺序存储结构的线性表任意一个位置中插入一个元素，在等概率条件下，平均需要移动（ ）个元素。5在具有n个元素的顺序存储结构的线性表任意一个位置中删除一个元素，在等概率条件下，平均需要移动（ ）个元素。6在具有n个元素的顺序存储结构的线性表中查找某个元素，平均需要比较（ ）次。7当线性表的元素基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中第i个元素时，应采用( )存储结构。8顺序存储结构的线性表中，插入或删除某个元素时，元素移动的次数与其位置（ ）关。（填有或无）。9顺序存储结构的线性表中，访问第i个元素与其位置（ ）关。（填有或无）。10在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（ ）。11在顺序表L中的i个位置插入某个元素x，正常插入时，i位置以及i位置以后的元素需要后移，首先后移的是（ ）个元素。12要删除顺序表L中的i位置的元素x，正常删除时，i位置以后的元素需要前移，首先前移的是（ ）元素。13若顺序表中的元素是从1位置开始存放的，要在具有n个元素的顺序表中插入一个元素，合法的插入位置是（ ）。14若顺序表中的元素是从1位置开始存放的，要删除具有n个元素的顺序表中某个元素，合法的删除位置是（ ）。15在具有n个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（ ）。16在具有n个元素的顺序存储结构的线性表中插入某个元素的时间复杂度是（ ）。17在具有n个元素的顺序存储结构的线性表中要访问第i个元素的后继结点的时间复杂度是（ ）。18在具有n个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（ ）。19在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是没找完且（ ）。20在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是（ ）且没找到。21如果要将两个升序排列的整型顺序表a中的元素合并到b中（b的空间足够大），合并后表中元素依然升序排列，可以通过多次调用查找函数查找插入位置，再调用（ ）函数来实现插入。22若要将一个整型的顺序表拆分为一个存放正数，另一个存放非正数的两个顺序表，存放正数的顺序表用原来的表，时间复杂度为（ ）。23顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度（ ）同。二、简答题1.下列算法完成在顺序表SeqL的第i个位置插入元素x，正常插入返回1，否则返回0或-1，请在空的下划线上填写合适的内容完成该算法。/表中最多可以放置MAXLEN个元素int seq_ins(SeqList *SeqL,int i, DataType x) int j; if ( ) /*表满*/ printf(the list is fulln); return 0; else if (i SeqL-len+1) /*位置不对*/ printf(the position is invalidn ); return -1; else /*正常插入*/ for (j=SeqL-len;j=i;j-) /*元素后移*/ /*插入元素*/ (SeqL-len)+; /*表长加1*/ 2.下列算法完成删除顺序表SeqL的第i个元素，元素类型为DataType，其值通过参数px返回，请在空的下划线上填写合适的内容完成该算法。 int seq_del (SeqList * SeqL,int i， ) int j ; if （SeqL-len=0) /*表空*/ printf(the list is emptyn);return 0; elseif( ) /*位置不对*/ printf(n the position is invalid); return -1; else /*正常删除*/ *px=SeqL-datai; /*删除元素通过参数px 返回*/ for (j=i+1;jlen;j+) ; /*元素前移*/ ; /*表长减1*/ return 1; 3.简述什么是顺序存储结构，顺序存储结构的优缺点都有哪些。4. 设有一整型顺序表L，元素从位置1开始存放，下列算法实现将以第一个元素为基准，将其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。请在空的下划线上填写合适的内容完成该算法。void part(SeqList *L) ; /*循环变量声明*/ int x; ; /*将第一个元素置入x中*/ for(i=2;ilen;i+) if( ) /*当前元素小于基准元素*/ L-data0=L-datai; /*当前元素暂存在0位置*/ for(j=i-1;j=1;j-) /*当前元素前面所有元素后移*/ L-dataj+1=L-dataj; /*当前元素从0位置移到最前面*/ 5. 设有一整型顺序表L，元素从位置1开始存放，下列算法实现将以第一个元素为基准，将其放置在表中合适的位置，使得其前面的元素都比它小，后面的元素均大于等于该元素。请在空的下划线上填写合适的内容完成该算法。void part(SeqList *L) int i,j; i=1; /*i指向第一个位置*/j=L-len; /*j指向最后一个位置*/ L-data0= L-data 1; /*将基准元素暂存在0位置*/ while( ) while(L-data j= L-data 0)&(ij) j-; /*j位置元素大于基准元素且ij 时j前移*/ if (idata i= L-data j;i+; while(L-data idata 0)&(ij) i+;/*i位置元素小于基准元素且ij 时i后移*/ if (inext=HL-next及( )操作。14设指针变量p指向单链表中某结点A，则删除结点A的后继结点需要的操作为（ ）（不考虑存储空间的释放）。15在单链表中，若给定某个结点的指针，要删除该结点的后继结点的时间复杂度为（ ）。16统计单链表中元素个数的时间复杂度是（ ）。17要访问具有n个结点的单链表中任意一个结点的时间复杂度是（ ）。18链式存储结构的线性表中，插入或删除某个元素所需的时间与其位置（ ）关。（填有或无）。19在单链表中，若给定某个结点的数据信息，要删除该结点的后继结点的时间复杂度为（ ）。20若指针p,q的值相同，则*p和*q的值（ ）相同。21若要将一个单链表中的元素倒置，可以借助（ ）建立单链表的思想将链表中的结点重新放置。22线性表用链式存储结构存储比用顺序存储结构存储所占的存储空间（ ）多。（填一定或不一定）二、简答题1下列算法完成用头插法为数组a中的n个元素建立一个带头结点的单链表，并返回其头指针，请在空的下划线上填写合适的内容完成该算法。NodeType* creatl2 (DataType a,int n) NodeType*head, *s； int i；head=(NodeType*)malloc(sizeof(NodeType)； /*为头结点申请空间*/if (head=NULL) return NULL; ; /*链表初始化为空*/ for (i=1；inext=head-next； /*新结点的指针域指向头的下一个元素*/ ; /*头结点指向新结点*/ ; /*返回头指针*/ 2.下列算法完成用尾接法为数组a中的n个元素建立一个带头结点的单链表，并返回其头指针，请在空的下划线上填写合适的内容完成该算法。NodeType* creatl1(DataType a,int n) NodeType *head,*tail,*s; /* head为头指针， tail为尾指针*/ int i; head=initl( ); /*链表初始化*/ if (head=NULL) return NULL; ; /*尾指针初始化为头指针*/ for (i=0;inext=NULL; / *给新结点的指针域赋值*/ tail-next=s; /*将新结点接到表尾*/ ; /*新结点为当前的表尾*/ return head; /*返回头指针*/ 3. 简述什么是链式存储结构，链式存储结构的优缺点有哪些。4. 请解释：结点，头结点，头指针，首元结点。5. 已知整型带头结点的单链表H，下列算法实现将该链表中的元素倒置，若原链表中的元素为1，2，3，4，5； 倒置后在则变成5，4，3，2，1. 请在空的下划线上填写合适的内容完成该算法。void reverse ( ) NodeType*p; p=H- next; /*p指向首元结点*/ H-next=NULL; /*头结点的指针域为空*/ while( ) /*当p结点不为空时*/ q=p; p=p-next; /*p指针后移*/ /*将q所指向的结点插入到头结点之后*/ 三、算法设计1.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中查找元素x，若找到，则返回其位置；否则返回一个空位置。2.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法查找带头结点的单链表L中第i个元素，若找到，则返回其位置；否则返回一个空位置。3.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法求带头结点的单链表L的长度。4.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法统计带头结点的单链表L中元素x的个数。5.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中查找元素x的前驱结点，若找到，则返回其位置；否则返回一个空位置。6.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法在带头结点的单链表L中，将新元素x插入到带头结点的单链表L中的元素elm之后，若不存在元素elm，则插入到最后。7.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法删除带头结点的单链表L中的元素x（元素x只有一个）。8.设单链表的结点类型定义如下：typedef struct node int data； struct node *next；NodeType；设计一算法删除带头结点的单链表L中所有的元素x(元素x可能有多个)。9. 设有一整型的带头结点的单链表，其元素值升序排列，请定义结点的类型并设计一算法实现：任意给定一个元素x将其插入到该表中，使得该链表中的数据依然有序。10. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next;nodetype;设计一算法，求该链表中值最大的结点并返回该结点的指针，若链表为空，则返回一个空指针。11. 已知一带头结点的单链表L，结点类型为： typedef struct nodeint data;struct node *next;nodetype;设计一算法，求该链表中值结点的平均值并返回。第三章 顺序表一、填空1.顺序2.一定3.一致4.n/25. n-1/26. n+1/27.顺序8.有9.无10.O（1）11.最后一12. i+1位置13.1n+114.1n15.O(n)16.O(n)17.O(1)18.O(n)19.没找到20.没找完21.插入22.O（n2）23.相同二、简答题1. SeqL-len=MAXLENSeqL-dataj+1= SeqL-dataj;SeqL-datai=x;return 1;2.DataType xi SeqL-len+1SeqL-dataj-1= SeqL-dataj;SeqL-len-;3. 顺序存储结构：用一片连续的存储空间将数据元素一个挨着一个存放起来，通常用“数组”实现。顺序表的优点：1）存储结构与逻辑关系一致；2）随机访问顺序表的第i个元素很方便；缺点： 顺序表的插入、删除操作要通过移动元