国家计算机二级公共基础知识复习要点.pdf

《国家计算机二级公共基础知识复习要点.pdf》由会员分享，可在线阅读，更多相关《国家计算机二级公共基础知识复习要点.pdf（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二级公共基础附2 2 0 题祥解二级公共基础知识新大纲基本要求1,掌握算法的基本概念.2,掌握基本数据结构及其操作.3,掌握基本排序和查找算法.4 掌握逐步求精的结构化程序设计方法.5,掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力.考试内容一,基本数据结构与算法1,算法的基本概念;算法复杂度的概念和意义（时间复杂度与空间复杂度）.2,数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念.3,线性表的定义;线性表的顺序存储结构及其插入与除运算.4,栈和队列的定义;栈和队列的顺序存储结构及其基本运算.5,线性单链表，双向链表与循环链表的结构及其

2、基本运算.6,树的基本概念;二*树的定义及其存储结构;二*树的前序，中序和后序遍历.7,顺序查找与二分法查找算法;基本排序算法（交换类排序，选择类排序，插入类排序）.程序设计基础1,程序设计方法与风格.2,结构化程序设计.3,面向对象的程序设计方法，对象，方法，属性及继承与多态性.三,软件工程基础1,软件工程基本概念，软件声明周期概念，软件工具与软件开发环境.2,结构化分析方法，数据流图，数据字典，软件需求规格说明书.3,结构化程序设计方法，总体设计与详细设计.4,软件测试的方法，白盒测试与黑盒测试,测试用例设计，软件测试的实施，单元测试，集成测试和系统测试.5,程序的调试，静态调试与动态调试

3、.四,数据库设计基础1,数据库的基本概念:数据库，数据库管理系统,数据库系统.数据模型，实体练习模型及E-R图，从 E-R图导出关系数据模型.2,关系代数运算，包括几何运算及选择，投影，连接运算,数据库规范化理论.数据库设计方法和步骤:需求分析，概念设计,逻辑设计和物理设计的相关策略.公共基础知识总结第一章数据结构与算法1.1 算法算法:是指解题方案的准确而完整的描述.算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计.算法的基本特征:是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止.特征包括：可行性；(2)确定性，算法中每一步骤都必须有

4、明确定义，不充许有模棱两可的解释，不允许有多义性;(3)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止,包括合理的执行时间的含义；(4)拥有足够的情报.算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构.指令系统:一个计算机系统能执行的所有指令的集合.基本运算和操作包括:算术运算，逻辑运算，关系运算，数据传输.算法的控制结构:顺序结构，选择结构，循环结构.算法基本设计方法:列举法，归纳法，递推，递归，减斗递推技术，回溯法.算法复杂度:算法时间复杂度和算法空间复杂度.算法时间复杂度是指执行算法所需要的计算工作量.(1)平均性态分析(2)最坏情况复杂性算法空间复杂度是

5、指执行这个算法所需要的内存空间.如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。1.2 数据结构的基本基本概念数据结构研究的三个方面：(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构；(2)在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构；(3)对各种数据结构进行的运算.数据结构是指相互有关联的数据元素的集合.(数据的逻辑结构、数据的存储结构、对各种数据结构的运算)数据的逻辑结构包含：表示数据元素的信息；(2)表示各数据元素之间的前后件关系.数据的存储结构有顺序，链接，索引等.线性结构条件：(1)有且只有一个根结点；(2)每一个结点最多有一个

6、前件，也最多有一个后件.非线性结构:不满足线性结构条件的数据结构.1.3线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的.在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件.非空线性表的结构特征：(1)且只有一个根结点a1,它无前件；(2)有且只有一个终端结点a.它无后件；(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件.结点个数 n 称为线性表的长度，当 n=0 时，称为空表.线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有元素的所占的存储空间是连续的；

7、(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的.a i的存储地址为:ADR(ai尸ADR(al)+(i-l)k”ADR(al)为第一个元素的地址,k代表每个元素占的字节数.顺序表的运算:插入，删除，查找，排序，分解，复制和逆转等操作.(详 见14-16页)1.4 栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底.栈按照 先进后出”(FILO)或“后进先出”(L1FO)组织数据，栈具有记忆作用用top表示栈顶位置，用bottom表示栈底.栈的基本运算：(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是

8、将栈顶元素赋给一个指定的变量，此时指针无变化.队列是指允许在一端(队尾)进入插入，而在另一端(队头)进行删除的线性表.Rear指针指向队尾,front指针指向队头.队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表.队列运算包括(1)入队运算:从队尾插入一个元素；(2)退队运算:从队头删除一个元素.循环队列:s=0表示队列空,s=l且front=rear表示队列满1.5 线性链表数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点，简称结点.结点由两部分组成:(1)用于存储数据元素值，称为数据域;(2)用于存放指针，称为指针域，用于指向前一个或后一个结点.在链式存储

9、结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的.链式存储方式即可用于表示线性结构,也可用于表示非线性结构.线性链表,HEAD称为头指针,HEAD=NULL(或0)称为空表，如果是两指针:左指针(Llink)指向前件结点，右指针(Rlink)指向后件结点.线性链表的基本运算:查找，插入，删除.1.6树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根.每一个结点可以有多个后件，称为该结点的子

10、结点.没有后件的结点称为叶子结点.在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度.树的最大层次称为树的深度.二叉树的特点：(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树.二叉树的基本性质：(1)在二叉树的第k层上,最多有2(贮1)个结点；(2)深度为m的二叉树最多有2m-l个结点；度 为0的结点(即叶子结点)总是比度为2的结点多一个;N=NO+N1+N2N0=N2+l(4)具 有n个结点的二叉树,其深度至少为|log21+l,其中 logZ表示取login的整数部分；(5)具 有n个结点的完全二叉树的深度为|

11、log21+l;(6)设完全二叉树共有n个结点.如果从根结点开始，按层序(每一层从左到右)用自然数1,2,.n给结点进行编号(k=l,2.n),有以下结论：若k=l,则该结点为根结点，它没有父结点;若kl,则该结点的父结点编号为lNT(k/2);若2kWn,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点)；若2k+lSn,则编号为k的结点的右子结点编号为2k+l;否则该结点无右子结点.满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有型-1个结点.完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上

12、只缺少右边的若干结点.二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储.二叉树的遍历：AB C(1)前序遍历(DLR),首先访问根结点，然后遍历左子树，最后遍历右子树；(2)中序遍历(LDR),首先遍历左子树，然后访问根结点，最后遍历右子树；(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树，最后访问根结点.1.7 查找技术顺序查找的使用情况：(1)线性表为无序表；(2)表采用链式存储结构.二分法查找只适用于顺序存储的有序表，对 于 长 度 为n的有序线性表，最坏情况只需比较10g2n 次.1.8 排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有

13、序序列.交换类排序法：(1)冒泡排序法，需要比较的次数为n(n-l)/2;(2)快速排序法.插入类排序法：(1)简单插入排序法,最坏情况需要n(n-l)/2次比较；(2)希尔排序法,最坏情况需要O(i?6)次比较.选择类排序法：(1)简单选择排序法，最坏情况需要n(n-l)/2次比较;(2)堆排序法,最坏情况需要O(nlog2 次比较.第二章程序设计基础2.1 程序设计设计方法和风格HRBJGD163.C O M如何形成良好的程序设计风格1,源程序文档化;2,数据说明的方法;3,语句的结构;4,输入和输出.注释序言性注释和功能性注释，语句结构清晰第一，效率第二.2.2 结构化程序设计结构化程序

14、设计方法的四条原则是：1.自顶向下；2.逐步求精;3.模块化;4.限制使用goto语句.结构化程序的基本结构和特点：(1)顺序结构:一种简单的程序设计，最基本,最常用的结构；(2)选择结构:又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；(3)重复结构:又称循环结构，可根据给定条件,判断是否需要重复执行某一相同程序段.2.3 面向对象的程序设计面向对象的程序设计:以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志.面向对象方法的优点：(1)与人类习惯的思维方法一致；(2)稳定性好；(3)可重用性好；(4)易于开发大型软件产

15、品；(5)可维护性好.对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象.面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成.属性即对象所包含的信息,操作描述了对象执行的功能，操作也称为方法或服务.对象的基本特点：标识惟一性;(2)分类性;(3)多态性;(4)封装性;模块独立性好.类是指具有共同属性，共同方法的对象的集合.所以类是对象的抽象,对象是对应类的一个实例.消息是一个实例与另一个实例之间传递的信息.消息的组成包括(1)接收消息的对象的名称;(2)消息标识符,也称

16、消息名;(3)零个或多个参数.继承是指能够直接获得已有的性质和特征，而不必重复定义他们.继承分单继承和多重继承.单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类.多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象.第三章软件工程基础3.1软件工程基本概念计算机软件是包括程序，数据及相关文档的完整集合.软件的特点包括：(1)软件是一种逻辑实体；(2)软件的生产与硬件不同，它没有明显的制作过程；(3)软件在运行,使用期间不存在磨损，老化问题；(4)软件的开发，运行对计算机系统具有依赖性，受计算机系统的限制,这导致了软件移植的问题；(5)软件复杂性高，成本昂贵；(6)软件

17、开发涉及诸多的社会因素.软件按功能分为应用软件，系统软件，支撑软件(或工具软件).软件危机主要表现在成本，质量，生产率等问题.软件工程是应用于计算机软件的定义，开发和维护的一整套方法，工具，文档，实践标准和工序.软件工程包括3个要素:方法，工具和过程.软件工程过程是把软件转化为输出的一组彼此相关的资源和活动，包 含4种基本活动：(1)P软件规格说明；(2)D软件开发；(3)C软件确认；(4)A软件演进.软件周期:软件产品从提出，实现，使用维护到停止使用退役的过程.软件生命周期三个阶段:软件定义，软件开发，运行维护，主要活动阶段是：可行性研究与计划制定;(2)需求分析;软件设计;(4)软件实现;

18、(5)软件测试;(6)运行和维护.软件工程的目标和与原则：目标:在给定成本,进度的前提下，开发出具有有效性，可靠性，可理解性，可维护性，可重用性,可适应性，可移植性,可追踪性和可互操作性且满足用户需求的产品.基本目标:付出较低的开发成本;达到要求的软件功能;取得较好的软件性能;开发软件易于移植;需要较低的费用;能按时完成开发，及时交付使用.软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理.软件开发技术包括:软件开发方法学，开发过程,开发工具和软件工程环境.软件工程管理包括:软件管理学，软件工程经济学,软件心理学等内容.软件管理学包括人员组织，进度安排，质量保证，配置管理，项

19、目计划等.软件工程原则包括抽象，信息隐蔽,模块化，局部化,确定性，一致性,完备性和可验证性.3.2 结构化分析方法结构化方法的核心和基础是结构化程序设计理论.需求分析方法有(1)结构化需求分析方法;(2)面向对象的分析的方法.从需求分析建立的模型的特性来分:静态分析和动态分析.结构化分析方法的实质:着眼于数据流，自顶向下，逐层分解,建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型.结构化分析的常用工具(1)数据流图；(2)数据字典;(3)判 定 树;(4)判定表.数据流图:描述数据处理过程的工具,是需求理解的逻辑模型的图形表示，它直接支持系统功能建模.数据字典:对所有与系

20、统相关的数据元素的一个有组织的列表，以及精确的，严格的定义，使得用户和系统分析员对于输入，输出，存储成分和中间计算结果有共同的理解.判定树:从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系，并列关系，选择关系，根据它们构造判定树.判定表:与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值,即完成该加工的一组动作是由于某一组条件取值的组合而引发的,使用判定表描述比较适宜.数据字典是结构化分析的核心.软件需求规格说明书的特点：(1)正确性;(2)无岐义性;(3)完整性;(4)可验证性;一致性;可理解性;可追踪性.3.3结构化设计

21、方法软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型.软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径.从技术观点来看,软件设计包括软件结构设计，数据设计，接口设计，过程设计.结构设计:定义软件系统各主要部件之间的关系.数据设计:将分析时创建的模型转化为数据结构的定义.接口设计:描述软件内部，软件和协作系统之间以及软件与人之间如何通信.过程设计:把系统结构部件转换成软件的过程描述.从工程管理角度来看:概要设计和详细设计.软件设计的一般过程:软件设计是一个迭代的过程;先进行高层次的结构设计;后进行低层次的过程设

22、计;穿插进行数据设计和接口设计.衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准.在程序结构中各模块的内聚性越强，则耦合性越弱.优秀软件应高内聚，低耦合.软件概要设计的基本任务是：(1)设计软件系统结构；数据结构及数据库设计；编写概要设计文档；(4)概要设计文档评审.模块用一个矩形表示，箭头表示模块间的调用关系.在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息.还可用带实心圆的箭头表示传递的是控制信息，空心圆箭头表示传递的是数据.结构图的基本形式:顺序形式，重复形式，选择形式.结构图有四种模块类型:传入模块，传出模块，变换模块和协调模块.典型的数据流类型有两种:变换型和事务

23、型.变换型系统结构图由输入，中心变换，输出三部分组成.事务型数据流的特点是:接受一项事务，根据事务处理的特点和性质,选择分派一个适当的处理单元，然后给出结果.详细设计:是为软件结构图中的每一个模块确定实现算法和局部数据结构,用某种选定的表达工具表示算法和数据结构的细节.常见的过程设计工具有:图形工具（程序流程图、N S、P A D、H IPO）,表格工具（判定表）,语言工具（P D L）.程序流程图是一种传统的、应用广泛的软件过程设计表示工具，也称程序框图。I I控制流 next=NULL B)p=NULLC)p-next=head D)p=head解 析：循 环 链 表 就 是 将 链 表

24、的 最 后 一 个 结 点 指 向 链 表 头 结 点(或 第 一 个 结 点)，即p-next=head.(3)已知数据表A 中每个元素距其最终位置不远，为节省时间，应采用的算法是A)堆 排 序 B)直接插入排序C)快 速 排 序 D)直接选择排序解析：当数据表A 中每个元素距其最终位置不远，说明数据表A 按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少,故答案为选项B).(4)对建立良好的程序设计风格，下面描述正确的是A)程序应简单，清晰，可读性好B)符号名的命名只要符合语法C)充分考虑程序的执行效率D)程序的注释可有可无解析：程序设计应该简单易懂，语句构造应该简

25、单直接，不应该为提高效率而把语句复杂化.(5)下列不属于结构化分析的常用工具的是A)数据流图B)数据字典C)判定树D)PAD图解析：结构化分析的常用工具有数据流图，数据字典，判定树和判定表.而PAD图是常见的过程设计工具中的图形设计.(6)在软件生产过程中，需求信息的给出是A)程序员B)项目管理者C)软件分析设计人员D)软件用户解析：软件需求是指用户对目标软件系统在功能，行为，性能，设计约束等方面的期望.(7)下列工具中为需求分析常用工具的是A)PAD B)PFD C)N-S D)DFD解析：需求分析中的常用工具有PAD,PFD及 N-S等，而 DFD(数据流图)为结构化分析工具.(8)NUL

26、L 是指A)0 B)空格 C)未知的值或无任何值 D)空字符串解析：此题属于记忆性的题目,NULL是指未知的值或无任何值.(9)数据库的故障恢复一般是由A)数据流图完成的B)数据字典完成的C)DBA完成的D)PAD图完成的解析：一旦数据库中的数据遭受破坏,需要及时进行恢复,RDBMS 一般都提供此种功能，并由DBA负责执行故障恢复功能.(10)下列说法中,不属于数据模型所描述的内容的是A)数 据 结 构B)数 据 操 作C)数 据 查 询D)数据约束解析：数据模型所描述的内容有3个部分，它们是数据结构,数据操作和数据约束.其中，数据模型中的数据结构主要描述数据的类型，内容，性质，以及数据库的联

27、系等;数据操作主要是描述在相应数据结构上的操作类型与操作方式.填空题(1)冒泡排序算法在最好的情况下的元素交换次数为【1】.解析：根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较,且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排序算法在最好的情况下的元素交换次数为0.在最坏情况下，堆排序需要比较的次数为【2】.(3)若 串s=MathTypes”,则 其 子 串 的 数 目 是13】.解析：串s中共有9个字符，由于串中字符各不相同，则其子串中有0个字符的1个(空串),1个字符的9个,2个字符的8个,3个字符的7个,

28、4个字符的6个,5个字符的5个,6个字符的4个,7个字符的3个,8个字符的2个,9个字符的1个，共 有1+2+3+4+5+6+7+8+9+1=46.(4)软件开发环境是全面支持软件开发全过程的14】集合.关系数据库的关系演算语言是以【5】为基础的DML语言.解析：关系数据库中的关系演算包括元组关系演算和域关系演算.二者都是由原子公式组成的公式.而这些关系演算都是以数理逻辑中的谓词演算为基础的.答案:ACBAA DDCCC0 O(nlog2n)4 6软件工具 谓词演算第八套：(1)循环链表的主要优点是A)不再需要头指针了B)从表中任一结点出发都能访问到整个链表C)在进行插入，删除运算时，能更好的

29、保证链表不断开D)已知某个结点的位置后，能够容易的找到它的直接前件解析：循环链表就是将单向链表中最后一个结点的指针指向头结点,使整个链表构成一个环形,这样的结构使得从表中的任一结点出发都能访问到整个链表.(2)栈底至栈顶依次存放元素A,B,C,D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是A)ABCED B)DCBEA C)DBCEA D)CDABE解析：栈操作原则上“后进先出“，栈底至栈顶依次存放元素A,B,C,D,则表明这4个元素中D是最后进栈,B,C处于中间,A最早进栈.所以出栈时一定是先出D,再 出C,最后出A.(3)n个顶点的强连通图的边数至少有A)n-1 B)n(n-

30、l)C)n D)n+1解析：在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状,因而至少应有n条边.(4)在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的A)安全性 B)一 致 性C)可理解性 D)合理性(5)模块独立性是软件模块化所提出的要求，衡量模块独立性的度量标准则是模块的A)抽 象 和 信 息 隐 蔽B)局部化和封装化C)内聚性和耦合性D)激活机制和控制方法解析：模块的独立程序是评价设计好坏的重要度量标准.衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准.(6)软件开发的结构化生命周期方法将软件生命

31、周期划分成A)定义，开发，运 行 维 护B)设计阶段，编程阶段，测试阶段C)总体设计，详细设计，编 程 调 试D)需求分析，功能定义，系统设计解析：通常，将软件产品从提出，实现，使用维护到停止使用退役的过程称为软件生命周期.它可以分为软件定义，软件开发及软件运行维护3个阶段.在软件工程中，白箱测试法可用于测试程序的内部结构.此方法将程序看做是A）路径的集合B）循环的集合C）目标的集合D）地址的集合解析：软件的白盒测试方法是把测试对象看做一个打开的盒子，它允许测试人员利用程序内部的逻辑结构及有关信息，设计或选择测试用例，对程序所有逻辑路径进行测试.（8）在数据管理技术发展过程中，文件系统与数据库

32、系统的主要区别是数据库系统具有A）特定的数据模型B）数据无冗余。数据可共享D）专门的数据管理软件解析：在文件系统中，相互独立的记录其内部结构的最简单形式是等长同格式记录的集合,易造成存储空间大量浪费，不方便使用.而在数据库系统中，数据是结构化的,这种结构化要求在描述数据时不仅描述数据本身，还要描述数据间的关系,这正是通过采用特定的数据模型来实现的.（9）数据库设计包括两个方面的设计内容,它们是A）概念设计和逻辑设计B）模式设计和内模式设计C）内模式设计和物理设计D）结构特性设计和行为特性设计（10）实体是信息世界中广泛使用的一个术语，它用于表示A）有生命的事物B）无生命的事物C）实际存在的事物

33、D）一切事物解析：实体是客观存在且可以相互区别的事物.实体可以是具体的对象，如一个学生，也可以是一个抽象的事件，如一次出门旅游等.因此，实体既可以是有生命的事物,也可以是无生命的事物，但它必须是客观存在的,而且可以相互区别.填空题（1）常用的黑箱测试有等价分类法，【1】，因果图法和错误推测法4种.解析：黑箱测试方法完全不考虑程序的内部结构和内部特征,而只是根据程序功能导出测试用例.常用的黑箱测试有等价分类法，边值分析法，因果图法和错误推测法4种.（2）测试的目的是暴露错误,评价程序的可靠性;而【2】的目的是发现错误的位置并改正错误.解析：软件测试的目标是在精心控制的环境下执行程序，以发现程序中

34、的错误，给出程序可靠性的鉴定;调试也称排错，它是一个与测试有联系又有区别的概念.具体来说,测试的目的是暴露错误，评价程序的可靠性，而调试的目的是发现错误的位置，并改正错误.(3)软件维护活动包括以下几类:改正性维护，适应性维护，【3】维护和预防性维护.解析：软件维护活动包括以下几类:改正性维护，适应性维护，完善性维护和预防性维护.改正性维护是指在软件交付使用后，为了识别和纠正软件错误，改正软件性能上的缺陷，排除实施中的误使用，应当进行的诊断和改正错误的过程;适应性维护是指为了使软件适应变化，而去修改软件的过程;完善性维护是指为了满足用户对软件提出的新功能与性能要求,需要修改或再开发软件，以扩充

35、软件功能，增强软件性能,改进加工效率，提高软件的可维护性;预防性维护是为了提高软件的可维护性，可靠性等,为以后的进一步改进软件打下良好基础.(4)在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为【4】.解析：在面向对象技术中,主要用到对象(object),类(class),方法(method),消息(message),继承(inheritance),封装(encapsulation)等基本概念.其中消息是用来请求对象执行某一处理或回答某些信息的要求.关键字ASC和DESC分 别 表 示【5】的含义.解析：ASC表示升序排列,DESC表示降序排列，多用在索引定义和SELECT

36、语句中的ORDER子句中.答案：BBCCC AAAAC边值分析法调试完善性消息升序排序和降序排序第九套：(1)由两个栈共享一个存储空间的好处是A)减少存取时间，降低下溢发生的机率B)节省存储空间，降低上溢发生的机率C）减少存取时间，降低上溢发生的机率D）节省存储空间，降低下溢发生的机率解析：常常一个程序中要用到多个栈,为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间.但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张;若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补.（2）设有两个串p和q,求q在p中首次出现位置的运算称作A）

37、连 接B）模式匹配C）求 子 串D）求串长解析：子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是:从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功.（3）n个顶点的连通图中边的条数至少为A）0 B）1 C）n-1 D）n解析：在无向图（边没有方向性的图）中，若从顶点Vi到vj有路径，则 称vi和vj是连通的，若该图中任意两个顶点都是连通的，则称该图为连通图.（4）对象实现了数据和操作的结合，

38、是指对数据和数据的操作进行A）结合 B）隐 藏C）封装 D）抽象解析：对象是由数据及可以对这些数据施加的操作组成的统一体.对象的内部，即处理能力的实行和内部状态，对外是看不见的,这一特性称做对象的封装.下列叙述中，正确的是A）软件就是程序清单B）软件就是存放在计算机中的文件C）软件应包括程序清单及运行结果D）软件包括程序和文档解析：软件（software）是计算机系统中与硬件相互依存的另一部分，是包括程序，数据及相关文档的完整集合.（6）软件设计中，有利于提高模块独立性的一个准则是A）低内聚低耦合B）低内聚高耦合C）高内聚低耦合D）高内聚高耦合解析：模块的独立程度是评价设计好坏的重要度量标准.

39、衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准.一般优秀的软件设计，应尽量做到高内聚，低耦合,即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性.软件生命周期中花费时间最多的阶段是A）详 细 设 计B）软件编码C）软 件 测 试D）软件维护解析：软件生命周期分为软件定义，软件开发及软件运行维护3个阶段.本题中，详细设计,软件编码和软件测试都属于软件开发阶段;维护是软件生命周期的最后一个阶段,也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性,降低维护的代价.（8）下 列4项中说法不正确的是A）数据库减少了数据冗余B）数据库中的数据可以

40、共享C）数据库避免了一切数据的重复D）数据库具有较高的数据独立性解析：数据库系统具有以下几个特点，一是数据的集成性，二是数据的高共享性与低冗余性,三是数据的独立性,四是数据统一管理与控制.（9）下列4项中，必须进行查询优化的是A）关系数据库B）网状数据库C）层次数据库D）非关系模型解析：关系数据模型诞生之后迅速发展,深受用户喜爱，但关系数据模型也有缺点，其最主要的缺点是由于存取路径对用户透明，查询效率往往不如非关系数据模型,因此为了提高性能，必须对用户的查询请求进行优化.（10）最常用的一种基本数据模型是关系数据模型，它的表示应采用A）树B）网络C）图D）二维表解析：关系数据模型用统一的二维表

41、结构表示实体及实体之间的联系(即关系).填空题(1)当线性表采用顺序存储结构实现存储时,其主要特点是1 1】.解析：顺序存储结构的主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中.在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的.(2)软件工程的出现是由于 2 .解析：从 2 0 世纪6 0 年代中期到7 0 年代中期，随着计算机应用的日益普及，软件数量急剧膨胀，在程序运行时发现的错误必须设法改正，用户有了新的需求时必须相应的修改程序以适应新的环境.种种软件维护工作耗费惊人的资源，更严重的是许多程序个体化使得程序最终无法维护，”软件危机”就这样出现了.

42、为了更有效的开发与维护软件，新兴了一门软件工程学即软件工程.(3)单元测试又称模块测试，一 般 采 用【3】测试.解析：软件测试过程一般按4个步骤进行，即单元测试，集成测试,验收测试和系统测试.单元测试的技术可以采用静态分析和动态测试.对动态测试多采用白盒动态测试为主，辅之以黑盒测试.(4)数据库恢复是将数据库从【4】状态恢复到某一已知的正确状态.解析：数据库恢复是将数据库中的数据从错误状态中恢复到某种逻辑一致的状态.如果数据库中包含成功事务提交的结果，则称数据库处于一致性状态.数 据 的 基 本 单 位 是 1 5】.答案；B B C C D C D C A D逻辑结构中相邻的结点在存储结构

43、中仍相邻软件危机的出现白盒测试法错误数据元素第十套：（1）线性表若采用链式存储结构时，要求内存中可用存储单元的地址A）必须是连续的B）部分地址必须是连续的C）一定是不连续的D）连续不连续都可以解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致.（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是A）冒 泡 排 序B）选 择 排 序C）快 速 排 序D）归并排序解析：从平均时间性能而言，快速排序最佳，其所需时间最少,但快速排序在最坏情况下的时间性能不如堆排序和归并排序.当序列中的记录基本有序或元素个数较少

44、时，冒泡排序和简单选择排序为最佳排序方法，故本题答案应该为选项A）.（3）下列叙述中，错误的是A）数据的存储结构与数据处理的效率密切相关B）数据的存储结构与数据处理的效率无关C）数据的存储结构在计算机中所占的空间不一定是连续的D）一种数据的逻辑结构可以有多种存储结构解析：一般来说,一种数据结构根据需要可以表示成多种存储结构.常用的存储结构有顺序,链接,索引等，而采用不同的存储结构，其数据处理的效率是不同的;一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的.（4）希尔排序属于A）交 换 排 序B）归并排序C）选 择 排 序D）插入排序解析：希尔排序的基本思想是把记录

45、按下标的一定增量分组，对每组记录使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时,整个数据合成一组，构成一组有序记录，故其属于插入排序方法.（5）下列叙述中,不属于结构化分析方法的是A）面向数据流的结构化分析方法B）面向数据结构的Jackson方法C）面向数据结构的结构化数据系统开发方法D）面向对象的分析方法解析：常见的需求分析方法有结构化分析方法和面向对象的分析方法两类.其中结构化分析方法又包括面向数据流的结构化分析方法（SA-Structured analysis）,面向数据结构的Jackson方法（JSD-Jackson system developme

46、nt method）和面向数据结构的结构化数据系统开发方法（DSSD-Data structured system development method）.（6）详细设计的结果基本决定了最终程序的A）代码的规模B）运行速度C）质 量D）可维护性解析：详细设计阶段的根本目标是确定应该怎样具体的实现所要求的系统,但详细设计阶段的任务还不是具体的编写程序,而是要设计出程序的“蓝图”，以后程序员将根据这个蓝图写出实际的程序代码，因此，详细设计阶段的结果基本上就决定了最终的程序代码的质量.（7）下列不属于静态测试方法的是A）代 码 检 查B）白盒法C）静态结构分析D）代码质量度量解析：静态测试包括代码检

47、查，静态结构分析和代码质量度量等.其中白盒测试属于动态测试.（8）公司中有多个部门和多名职员，每个职员只能属于一个部门,一个部门可以有多名职员,从职员到部门的联系类型是A）多 对 多B）一对一 C）多对一 D）一对多解析：现实世界中事物之间的联系在信息世界中反映为实体集之间的联系,实体集间的联系个数不仅可以是单个的也可以是多个的，这种关系可以有下面几种对应:一对一，一对多（多对一）多对多.两个实体集间的联系可以用下图表示：（9）下列关系运算的叙述中，正确的是A）投影，选择，连接是从二维表行的方向进行的运算B）并，交，差是从二维表的列的方向来进行运算C）投影，选择，连接是从二维表列的方向进行的运

48、算D）以上3种说法都不对解析：在关系模型的数据语言中，一般除了运用常规的集合运算（并，交，差,笛卡尔积等），还定义了一些专门的关系运算，如投影，选择，连接等.前者是将关系（即二维表）看成是元组的集合，这些运算主要是从二维表的行的方向来进行的.后者是从二维表的列的方向来进行运算的.（1 0）关系数据库管理系统应能实现的专门的关系运算包括A）排序，索引，统 计 B）选择，投影，连接C）关联，更新，排 序 D）显示，打印，制表解析：关系数据库建立在关系数据模型基础上，具有严格的数学理论基础.关系数据库对数据的操作除了包括集合代数的并,差等运算之外，更定义了一组专门的关系运算:连接，选择和投影.关系运

49、算的特点是运算的对象都是表.填空题用链表表示线性表的突出优点是1 1】.解析：为了克服顺序表中插入和删除时需要移动大量数据元素的缺点，引入了链式存储结构.链表表示线性表的突出优点是插入和删除操作方便，不必移动数据元素，执行效率高.（2）子程序通常分为两类：【2】和函数，前者是命令的抽象，后者是为了求值.解析：当程序之间发生调用关系时，调用命令所在的代码段被称为主程序，被调用的代码段被称为子程序.子程序是对功能的抽象，可分为过程和函数两类，两者的区别是函数是通过函数名来返回值的，而过程只能通过形式参数或对全局变量进行修改以返回值.（3）软 件 的【3】设计又称为总体结构设计,其主要任务是建立软件

50、系统的总体结构.（4）对软件是否能达到用户所期望的要求的测试称为【4】.（5）实体之间的联系可以归结为一对一联系,一对多（或多对多）的联系与多对多联系.如果一个学校有许多教师，而一个教师只归属于一个学校，则实体集学校与实体集教师之间的联系 属 于【5】的联系.答案;DABDD CBCCB便于插入与删除操作过程概要有效性测试一对多或1:N(1)下面叙述正确的是 OA.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令(或语句)的条数C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对 答案 C 考点I程序设计基础 评析时间复杂度：在运行算法时所耗费的