《二级基础知识教案.doc》由会员分享，可在线阅读，更多相关《二级基础知识教案.doc（5页珍藏版）》请在金锄头文库上搜索。
1、附: 二级基础知识 二级基础知识在笔试中占30的题量。其中：选择题10题，共20分；填空题5题，占10分。望读者能对这一部分知识引起足够的重视。1.1 学习目标与要求 考生在本章应该掌握的内容包括：1. 算法的基本概念，数据结构的基本概念及其定义，线性表及其基本运算，栈和队列及其基本运算，线性链表及其基本运算，二叉树的基本概念、存储结构及其遍历，最后还介绍了几种常用的查找与排序算法。2程序设计方法与风格，结构化程序设计，面向对象的程序设计方法，对象，方法，属性及继承与多态性。3软件工程基本概念，结构化分析方法，结构化设计方法，软件测试的基本方法，程序的调试方法。4数据库，数据库管理系统，数据库
2、系统的基本概念，数据模型，实体联系模型及ER图等基本概念，关系代数理论中的基本运算，数据库设计的基本方法和步骤。1.2 内 容 要 点第一章 数据结构与算法一、算法程序设计主要包括两个方面：一是行为特性的设计，二是结构特性的设计。前者是对程序中的每一个细节加以定义和描述，后者是指所确定的数据结构。算法的基本特征：可行性、确定性、有穷性等算法的基本要素：（1）数据对象的运算和操作。有算术运算、逻辑运算、关系运算和数据传输四类。 （2）算法的控制结构。有顺序、选择、循环三类。算法的基本方法：列举法、归纳法、递推法、递归法、回溯法等。算法的复杂度：包括时间复杂度和空间复杂度。l 时间复杂度执行算法所
3、需要的计算工作量f(n)(n指问题的规模)。 例如：在长度为n的一维数组中查找值为x的数组元素，则 平均时间复杂度为(n+1)/2,最坏时间复杂度为n。 在长度为n的一维数组中删除值为x的数组元素，则 平均时间复杂度为(n-1)/2,最坏时间复杂度为n-1，最佳时间复杂度为0。(1+2+。+n-1)/n(n-1)/2在长度为n的一维数组中插入值为x的数组元素，则最坏时间复杂度为n，最佳时间复杂度为0，平均时间复杂度为n/2,。(0+1+2+。+n)/（n+1）n/2在冒泡排序与选择排序中最坏情况下的时间复杂度为n(n-1)/2。l 空间复杂度执行这个算法所需要的辅助内存空间的大小。若算法所需要
4、的辅助内存空间的大小不随问题规模的增大而增大，则称该算法的空间复杂度为最小，即原地工作。t=aj;aj=aj+1;aj+1=t;二、数据结构数据结构所研究的内容：数据的逻辑结构（线性结构与非线性结构）、数据的存储结构（顺序存储与链式存储）和对数据结构的运算。其有数据的逻辑结构和数据的存储结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。常用的存储结构有：顺序、链接、索引等。数据结构中，没有前件的结点为根结点（起始结点），没有后件的结点为叶子结点（终止结点）。春夏秋冬数据逻辑结构通常分为两大类：线性结构和非线性结构。线性结构又称线性表，其特点是：有且只有一个根结点；每一个结点最
5、多有一个前件，也最多有一个后件。三、线性表及其顺序存储结构（数组）顺序存储的线性表（顺序表）的特点：（1）所有元素所占据的存储空间是连续的； （2）各数据元素在存储空间中是按逻辑顺序依次存放的。四、栈和队列是对插入与删除有特殊规定的线性表。栈(Stack)是限制在同一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶(top)。栈顶元素总是最后被插入的元素，也是最先能被删除的元素。因此，栈是按照“先进后出FILO”的原则组织数据，且具有记忆作用。栈顶是变化的（随入栈上升，随出栈下降），栈底是固定的。队列(Queue)是允许在一端插入、而在另一端进行删除的线性表。允许插入的一端称为队尾(re
6、ar)，删除的一端称为队头(front)。队尾元素总是最后被插入的元素，也是最后能被删除的元素。因此，队列是按照“先进先出FIFO”的原则组织数据。五、线性链表在链式存储方式中，每个结点有两部分组成：数据域和指针域。用一个专门的指针HEAD指向第一个结点，最后一个结点的指针域为空（NULL）。各数据结点的存储序号是不连续的。六、树与二叉树 树是简单的非线性结构。其每一个结点可以有多个后件。一个结点所拥有的后件个数称为该结点的度。所有结点中的最大的度称为树的度。树的层数称为树的深度。二叉树：每一个结点的度最大为2。满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的满二叉树结点总
7、数为2k-1深度为k的满二叉树中叶子结点总数为2k-1完全二叉树：在深度为n的二叉树中，1到n-2层上的每一个结点都有两个子结点，而第n-1层结点可以有两个子结点、也可以只有左分支结点或无子结点。n0=n2+1 n1=0或1完全二叉树n=1000双亲结点的编号为1000/2500 叶子结点的编号500 二叉树的遍历：不重复地访问二叉树中的所有结点。(1) 前序遍历（根左右）：首先访问根结点，然后先左树，后右树。左图中为： FCADBEGHP FCADBEGHP(2) 中序遍历(左根右)：首先遍历左子树，然后访问根结点，最后遍历右子树。为ACBDFEHGP ACBDFEHGP ABDCHPGEF
8、(3) 后序遍历(左右根)：首先遍历左子树，然后遍历右子树，最后访问根结点。为ABDCHPGEF 七、查找技术(1)顺序查找：最坏找n次。(2)二分法查找(前提：所有数据事先有序)：最坏找log2n次八、排序技术(1)冒泡排序法：时间复杂度为O(n(n-1)/2)； (2)简单插入排序法：时间复杂度为O(n(n-1)/2)；(3)希尔排序法：时间复杂度为O(n1.5)；(4)堆排序法：时间复杂度为O(nlog2n)。第二章 程序设计基础一、程序设计方法与风格程序设计方法的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。二、结构化程序设计设计原则：自顶而下、逐步求精、模块化、限制使用
9、goto语句。基本结构：顺序、选择、循环。每一种控制结构只允许有一个入口和一个出口。结构化程序设计主要强调程序的可读性。程序中可适当加一些注释，可分为序言性注释和功能性注释。三、面向对象的程序设计对象：客观世界中的任何实体。属性是指对象的状态、方法是指对象的操作。类：具有共同属性、共同方法的对象的集合。类是对象的模板、对象是类的实例。消息：对象间的相互合作的协助机制。即用来请求对象执行某一处理的要求。继承：表示类之间相似性的机制。类之间共享属性和操作的机制称为继承。封装：是一种信息隐蔽技术。信息隐蔽是通过对象的封装性来实现的。类具有继承性，对象具有封装性。第三章 软件工程基础软件三要素：程序、
10、文档和数据。软件危机：软件在开发和维护过程中所遇到的一些列严重问题。软件工程：软件定义、开发和维护的一整套方法。其核心思想是把软件当作一个工程产品来处理。其三要素：方法、工具和过程。 软件工程管理主要包括：软件开发技术和软件工程管理常见的需求分析方法有：结构化分析方法和面向对象的分析方法。其中，结构化分析方法主要包括：面向数据流的结构化分析方法和面向数据结构的Jackson方法。软件生命周期：软件定义、软件开发、软件的运行与维护。软件分析的重要工具是：数据流图(DFD)、数据字典(DD)等。数据流图(DFD)由数据流、加工、存储文件及源和潭组成。数据流图(DFD)有两种形式：变换型和事务型数据
11、字典(DD)用于描述系统中所用到的全部数据和文件的文档模块的内聚性：一个模块内部各个元素之间彼此结合的紧密程度。模块的耦合性：模块间相互连接的紧密程度。高内聚、低耦合。软件测试的目的：发现错误软件测试的实施：单元测试、集成测试、确认测试、系统测试软件测试的方法：(1)静态测试代码检查动态测试执行程序而发现错误 (2)白盒测试检查内部成分 黑盒测试检查外部成分第四章 数据库设计基础三级模式： 内模式 又称物理模式,反映了数据的物理存储结构.是真正存在的模式 模式 又称概念模式，反映了数据的全局逻辑结构。 外模式 又称用户模式,反映了数据的局部逻辑结构.是用户使用的模式三级模式之间的关系：内模式是模式的物理实现，模式是内模式的逻辑表示, 外模式是模式的部分抽取两级映射： 模式/内模式映射：当数据的物理存储结构发生变化时，只要修改该映射，而使数据的全局逻辑结构不发生变化，从而保证了数据的物理独立性； 外模式/模式映射：当数据的全局逻辑结构发生变化时，只要修改该映射，而使数据的局部逻辑结构不发生变化，从而保证了数据的逻辑独立性；E-R图 E-R图，即实体联系图（Entity-Relationship）,通过图形符号来表示实体及其相互联系，由美籍华人陈平山（P.P.Chen）于1976年提出； E-R图的三要素分别是：实体、联系、属性；在E-R图中依次用方框、菱形、椭圆来表示；
