二级Access笔试知识点105条.doc

算法与数据结构1、算法：是对一个问题求解步骤的一种描述（问题处理方案正确而完整的描述）。其5个主要特性:有穷性，确定性，可行性，拥有足够的情报。有穷性是指算法必须在有限的时间内做完，即算法必须在有限个步骤之后执行终止。2、在算法正确的前提下，评价一个算法的两个标准是即算法复杂度包括时间复杂度和空间复杂度。其中时间复杂度是指执行算法所需要的计算工作量。空间复杂度是算法所需的内存空间。3、算法分析的目的在于选择合适的算法和改进算法。4、数据项是数据的最小单位。数据的最小访问单位是字段数据结构是指相互有关联的数据元素的集合。5、数据结构研究的3个方面： 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； 对各种数据结构进行的运算。6、数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，反映了数据元素之间的前后件关系（线性、非线性），通常记为R。一个数据结构可以表示成：B=(D,R)7、数据的存储结构是指数据的逻辑结构在计算机存储空间的存储形式。在数据的存储结构中，不仅需要存储各数据元素的信息，还要存放各元素之间前后件的信息。一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。常见的存储结构有顺序、链接、等。8、顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的额存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储方式就是在每一个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。9、线性结构又称线性表，在一个线性结构中插入或删除任何一个结点后还是线性结构。常用的线性结构有：栈、队列、串等。常用的非线性结构有：数组、广义表、树和图等。10、线性表中的元素之间具有一对一的关系，除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后驱。顺序存储是线性表的一种最常用的存储方式。线性表的链式存储结构所需要的存储空间一般要大于顺序存储结构。11、栈的基本运算有三种：入栈、退栈和读栈（将栈顶元素赋给一个指定的变量）。12、栈是限定仅在一端进行插入和删除操作的线性表。允许插入和删除的一端叫做“栈顶”，另一端叫做“栈底”。栈的修改只能在栈顶进行，按照后进先出的原则，具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。13、队列只允许在表的一端进行插入操作（队尾，rear），而在另外一端进行删除操作（队头,front），队列的修改按照先进先出的原则。14、循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间实质上还是顺序存储结构。由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。所以队头指针可以大于队尾指针也可以小于队尾指针。循环链表的主要优点是从表中任一结点出发都能访问到整个链表。 运算：s=0表示队列空 s=1，且front=rear表示队列满 元素个数=尾指针-头指针（若为负，再加其容量即可）15、数据结构中，每个数据存储在一个存储单元中，这个存储单元称为结点。每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。16、线性链表即线性表的链式存储结构，HEAD称为头指针，HEAD=NULL（0）称为空表。双向链表即每个结点设置两个指针，一个为左指针（Llink），用以指向其前件结点；另一个为右指针（Rlink），指向后件结点。在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入于删除，不需要移动链表中的元素。循环链表：增加了一个表头结点；最后一个结点的指针域指向表头结点17、树形结构是一类重要的非线性数据结构，其中以二叉树最为常用。树是结点的集合，非空树的根结点数目是只有一个。18、父节点（根）：在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为根结点。子结点（叶子结点）：在树结构中，每一个结构可以有多个后件，称为子结点。没有后件的结点称为叶子结点。度：一个结点所拥有的后件的个数称为结点的度，结点中最大的度称为树的度。深度：树的最大层次称为树的深度。根结点所在的层次为1.19、二叉树的每一个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。性质：（一）在二叉树的第i层上至多有2i-1个结点；（二）深度为k的二叉树至多有2k- 1个结点；（三）对任何一棵二叉树T，如果其叶子结点数为n1，度为2的结点数为n2，则n1=n2+1。（四）具有n个结点的完全二叉树的深度为int(log2n)+1。（五）设完全二叉树有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，3，n给结点进行编号，则：当k1时，该结点的父结点为int（k/2）当2k=n时，编号为k的结点的左子结点的编号为2k,否则该结点无左子结点当2k+1连接运算符逻辑运算符。29、要使程序具有良好的风格，概括起来可以分成4各部分：（1）源程序的文档化符号名的命名应具有一定的实际含义，以便于对程序功能的理解； 在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释。语句结构清晰第一、效率第二； 通过在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。（2）数据说明方法为使程序中的数据易于理解和维护，可采用下列数据说明的风格：次序规范化；变量安排有序化；使用注释（3）语句结构简单直接（4）输入输出方法30、结构化程序设计的原则是自顶向下、逐步求精、模块化和避免滥用goto语句，一个程序只有一个入口和一个出口。软件设计模块化的目的是降低复杂性。即把源代码按照功能划分为低耦合、高内聚的模块。31、结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。*32、注释分为序言性概述和功能性概述。参照完整性是在输入或或删除记录时，为维持表之间已定义关系而必须遵循的规则。*33、控件是窗体上用于显示数据、执行操作、装饰窗体的对象。控件的类型可分为结合型、非结合型和计算型34、对象：用来表示客观世界中的任何实体。面向对象的程序设计方法中涉及的对象是系统用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。对象的基本特点包括标识唯一性、分类性、多态性、封装性和模块独立性。类和实例：具有共同属性、共同方法的对象的集合，一个具体对象称为类的实例。消息：消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。继承：使用已有类作为基础（直接获得已有的性质和特征）建立新类的定义技术。已有的类可以当作基类引用，新类则可当作派生类引用。继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。继承是类之间共享属性和操作的机制。多态性：对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。35、面向对象程序设计的三个主要特征是：封装性、继承性和多态性。软件工程基础36、软件是包括程序、数据与相关文档的完整集合，在计算机系统中与硬件相互依存的部分。根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）37、软件危机主要表现在成本、质量、生产率等问题。为了摆脱软件危机，提出了软件工程的概念。所谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。38、软件工程包括3个要素：方法、工具和过程.方法是完成软件工程项目的技术手段; 工具支持软件的开发、管理、文档生成; 过程支持软件开发的各个环节的控制、管理.39、软件生命周期可分为3个时期共8个阶段：软件定义期：包括问题定义、可行性研究和需求分析3 个阶段； 软件开发期：包括概要设计、详细设计、编码实现和测试4 个阶段； 运行维护期：即使用、维护、退役。软件开发环境是全面支持软件开发全过程的软件工具集合。40、需求分析是对待开发软件提出的需求进行分析并给出详细的定义。，其任务是导出目标系统的逻辑模型，解决“做什么”的问题。需求分析分为四个阶段：需求获取、需求分析、编写需求规格说明书，需求评审。软件需求规格说明书（SRS），是需求分析阶段的最后成果，是软件开发的重要文档之一。其特点是：正确性、无歧义性（最重要）、完整性、可验证性、一致性、可理解性、可追踪性。需求分析的方法：（1）结构化分析方法：面向数据流(SA)：变换型和事务性 面向数据结构Jackson方法（JSD） 面向数据结构的结构化数据系统开发方法 （2）面向对象的分析的方法(OOA):静态分析、动态分析41、结构化分析的常用工具包括数据流图（DFD）、数据字典（核心）、判定树、判定表。数据流图（DFD）的主要图形元素：椭圆：代表加工（转换）。输入数据经加工变换产生输出。箭头：代表数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。双横线：代表存储文件（数据）。表示处理工程中存入各种数据的文件。矩形：代表源、谭。表示系统和环境的接口，属系统之外的实体。数据字典是对DFD中出现的被命名的图形元素进行确切解释。数据字典可分为4个条目：数据流、数据项、数据存储和数据加工。42、软件设计的分类：从技术观点上，可分为结构设计、数据设计、接口设计和过程设计。 结构设计定义软件系统各主要部件之间的关系； 数据设计将分析时创建的模型转化为数据结构的定义； 接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何 通信； 过程设计则是把系统结构部件转换为软件的过程性描述。从工程管理角度来看，分分为概要设计和详细设计。概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库模型。结构图（SC）是概要设计阶段的工具。其图形元素为：矩形：一般模块箭头：模块间的调用关系。带注释的箭头表示模块调用过程中来回传递的信息。实心圆的箭头：表示传递的是控制信息。空心圆箭头：表示传递的是数据。 详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。常见过程设计工具有： 图形工具：程序流程图（PDF）、盒图（N-S）、问题分析图（PAD）、HIPO表格工具：判定表语言工具：PDL（伪码）43、软件设计中应该遵循的基本原理和与软件设计有关的概念（1）抽象：就是把事物本质的共同特征提取出来而不考虑其他细节。软件设计中考虑模块化解决方案时，可以定出多个抽象级别。抽象的层次从概要设计到详细设计逐步降低。（2）模块化：模块是指把一个待开发的软件分解成若干小的简单的部分。模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。（3）信息隐蔽：信息隐蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。（4）模块独立性：模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。44、衡量软件模块独立性的度量标准：内聚性描述的是一个模块内各元素间彼此结合的紧密程度的度量，从功能角度来度量模块内的联系。耦合性是模块之间互相连接的紧密程度的度量。耦合性取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口。 在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。45、软件测试的目的是发现程序中的错误而执行程序的过程。软件测试的准则（1）所有测试都应追溯到用户需求； （2）在测试之前制定测试计划，并严格执行； （3）充分注意测试中的群集现象；（4）避免由程序的编写者测试自己的程序； （5）不可能进行穷举测试； （6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提46、软件测试依据软件是否需要被执行可分为静态测试和动态测试。（1）静态测试不实际运行软件，主要通过人工进行分析。包括代码检查、静态结构分析、代码质量度量。其中代码检查分为代码审查、代码走查、桌面检查、静态分析等具体形式；（2）动态测试就是通常所说的上机测试，是通过运行软件来检验软件中的动态行为和运行结果的正确性。动态测试的关键是使用设计高效、合理的测试用例（为测试设计的数据，由测试输入数据和预期的输出结果两部份组成）。测试用例的设计方法一般分为两类：黑盒测试方法和白盒测试方法。白盒测试：白盒测试是把程序看成装在一只透明的白盒子里，测试者完全了解程序的结构和处理过程。它根据程序的内部逻辑来设计测试用例，检查程序中的逻辑通路是否都按预定的要求正确地工作；主要方法有逻辑覆盖、基本路径测试。黑盒测试：黑盒测试是把程序看成一只黑盒子，测试者完全不了解，或不考虑程序的结构和处理过程。它根据规格说明书的功能来设计测试用例，检查程序的功能是否符合规格说明的要求。常用的黑盒测试有等价分类法、边值分析法、因果图法和错误推测。47、在两种基本测试方法中，白盒测试的原则之一是保证所测模块中每一个独立路径至少要执行一次。48、软件测试过程分4 个步骤，即单元测试、集成测试、验收测试和系统测试。（1）单元测试是对软件设计的最小单位模块（程序单元）进行正确性检验测试。依据详细设计说明书和源程序。单元测试的技