二级公共基础资料

《二级公共基础资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章数据结构与算法一、算法：指解决某个问题的方法1．特性：有穷性、确定性、可行性、有输入、有输出2．基本要素：1数据对象的运算和操作—算术运算、逻辑运算、关系运算、数据传输；2算法的控制结构—算法中各操作之间的执行顺序，一个算法一般用顺序、选择、循环三种基本控制结构组成。3．算法的复杂度1时间复杂度：执行算法所需要的计算工作量，用算法在执行过程中所需的基本运算次数来衡量2空间复杂度：执行这个算法所需要的内存空间。即算法程序所占空间、初始输入数据所占的存储空间、以及算法执行过程中所需的额外空间二、数据结构：反映数据元素之间关系的

2、数据集合的表示，即带有结构的数据之间的前后件关系（相互有关联的数据元素的集合）三方面问题：1数据的逻辑结构：从逻辑关系上描述数据，与数据在计算机中的存储位置无关2数据的存储结构：数据元素及其关系在计算机存储器内的表示。分为4种：顺序存储方式、链式存储方式、索引存储方式、散列式存储方式3数据运算：查找、读取、插入、删除、更新三、线性结构与非线性结构（非空数据结构）1．线性结构：有且仅有一个根结点；每一个结点最多有一个前件，也最多有一个后件。一个线性表中插入或删除任何一个结点后还是线性结构。2．线性表的链式存储结构称为线性链表（坐指

3、针指向前件结点，右指针指向后件结点称为双向链表）3．带链的栈可以用来收集计算机存储空间中所有空闲的存储点,称为可利用栈4．链式存储结构中，存储数据结构的存储空间可以不连续，个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系式由指针域来确定的四、栈是限定仅在表尾进行插入和删除操作的线性表。表尾端为栈顶，栈顶元素总是最后被插入的元素，也是最先能被删除的元素。栈的修改原则：‘先进后出’‘后进先出’栈的顺序存储结构：Top=0栈空栈的基本运算：入栈（有上溢错误）、出栈、读栈顶元素（栈顶指针不变，栈顶指针为0

4、说明栈空，读不到栈顶元素）、初始化、置空、判断栈是佛为空或满、提取栈顶元素等。五、队列是限定仅在表的一端进行插入，而在表的另一端删除数据元素的线性表。（先进先出）允许插入的一端——队尾基本运算：入队、退队队列的顺序存储结构：循环队列，初始状态为空六、查找顺序查找：在线性表中查找指定的元素二分法查找：只适用于顺序存储的有序表即要求线性表中的结点必须按照关键字值的递增或递减顺序排列七、树1．一种简单的非线性结构，所有数据元素之间的关系具有明显的层次性，是N个结点的集合2．特点：每层平均的结点数为树的度，每一个结点的度最大为2，当一个

5、结点既没有左子树也没有右子树时该结点为叶子结点。非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树3．第K层上最多有2k-1（k≥1）个结点；深度为m的二叉树最多有2m-1个结点；任意一棵二叉树，度为0的结点（叶子结点）总是比度为2的结点多一个具有n个结点的二叉树，其深度至少为［log2n］+14．父节点：每个结点最多只有一个直接前驱（前件）根结点：没有直接前驱的结点只有一个为树根子结点：每一个结点可以有多个后件5．满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树前序遍历：根结点、左子树、右

6、子树中序遍历：左子树、根结点、右子树后序遍历：左子树、右子树、根结点八、排序法1．冒泡排序法和快速排序法都属于交换类排序法2．冒泡排序法的平均执行时间为：n2快速排序法平均执行时间为：nlog2n第二章程序设计基础一、程序设计风格：（1）源程序文档化：标识符的命名、程序的注释—序言性注释与功能性注释、程序的视觉组织（2）数据说明（3）语句输出（4）输入输出二、结构化程序设计主要原则：自顶向下、逐步求精、模块化、严格控制goto语句三、面向对象的基本概念：对象、类和属性方法继承多态性消息1．对象：对象的操作也称为方法或服务；属性即

7、对象所包含的信息；操作描述了对象的功能。对象特性——标识唯一性、分类性、封装性、模块独立性2．类与实例：类是具有共同属性、共同方法的对象的集合，它描述了属于该对象类型的所有对象的性质，一个对象则是其对应类的一个实例。3．消息：是实例之间传递的信息4．同样的信息被不同对象接收时可导致完全不同的行动第三章软件工程基础一、软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序1．3个要素：方法、工具、过程2．基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性3．核心思想：把软件产品

8、看做是一个过程产品来处理4．软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程包括：可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行和维护软件设计——结构设计（定义软件系统各部件之间的关系）、数据设计（将分析时查创建的模型转化为数