大学生计算机考试二级公共基础知识总结.docVIP

二级公共基础知识总结 第一章 数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法的基本特征： （1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性。算法中每一步骤都必须有明确的定义，不允许有模棱两可的解释，不允许有多义性。 （3）有穷性。算法必须在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。 （4）拥有足够的情报。 *：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 算法复杂度包括：时间复杂度和空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。可以用执行算法的过程中所需基本运算的执行次数来度量。 算法空间复杂度是指执行算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构是指相互有关联的数据元素的集合。数据的存储结构有顺序、链接、索引等线性结构条件：1）有且只有一个根结点；2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。 1.4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”或“后进先出”组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算： （1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进行插入，而在另一端（队头）进行删除的线性表。 rear指针指向队尾，front指针指向队头。 队列是“先进先出”或“后进后出”的线性表。 队列运算包括： （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 循环队列：对象的基本特点：类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。计算机软件是包括程序、数据及相关文档的完整集合。软件危机成本、质量、生产率等问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期软件定义、软件开发运行维护软件工程的目标和与原则目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开发，及时交付使用原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。）3.2 结构化分析方法结构化方法的核心和基础是结构化程序设计理论。需求分析方法有1）结构化需求分析方法；2）面向对象的分析方法。结构化分析的常用工具1）数据流图；2）数据字典3）判定树；4）判定表。数据流图数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。数据字典是结构化分析的核心。软件需求规格说明书3.3 结构化设计方法详细设计3.4 软件测试软件测试的目的：发现错误。软件测试方法：静态测试和动态测试。静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试：是基计算机的测试，主要包括白盒测试方法和黑盒测试方法。 软件测试过程一般按4个步骤进行：单元测试、集成测试、确认测试和系统测试。3.5 程序的调试程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行程序调试的基本步骤：（1）错误定位；（2）；（3）回归测试。4.1 数据库系统的基本概念数据：实际上就是描述事物的符号记录数据的特点：有一定的结构，有型与值之分如整型、实型、字符型等。而数据的值给出了符合定型的值，如整型值15。数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据库管理员：对数据库进行规划、设计、维护