湖南省二级新增知识点

1、公共基础知识（二级） 公共基础知识总复习 主讲人：高艳霞主讲人：高艳霞第一章 数据结构与算法n1、算法 基本特征、时间复杂度（会计算简单算法的）、空间复杂度2、基本概念 数据结构的研究内容、目的、定义、逻辑结构与存储结构n3、线性结构几个特例（线性表、栈、队列）的特征与操作比较： 顺序表不需要指针、栈和队列都有两个指针、指向位置的区别、满与空的判别n4、顺序存储和链式存储的区别、操作的异同，各有什么优缺点，注意同样存在链栈、链队，头指针与头结点的区别。链表的头指针与头结点图n头指针：指向第一个结点；n头结点：链表中为方便运算而设置的结点。a2a1anHead510270地址：5头结点头指针总结

2、：顺序表的优缺点n顺序表的优点：n1）无需为表示结点间的逻辑关系而增加额外的存储空间。n2）可以方便地随机存取表中的任一结点。n顺序表的缺点：n1）插入和删除运算不方便。须移动大量结点，效率较低。n2）存取空间要预先分配，动态扩充和分配都不方便。总结：链表的优缺点n链表的优点：n1）插入和删除很方便。n2）不需要实现估计“容量”，扩充和动态分配空间很容易。n链表的缺点：n1）为表示结点间的逻辑关系需要增加额外的空间。n2）不能实现随机访问。n5、树与二叉树 1）根、叶子、度、深度的概念 2）二叉树的五条性质：总个数、叶子数、高度的计算。 完全二叉树中，由总结点个数求叶子与非叶子结点的简单做法。

3、 3）三种遍历方法：由其中两种求另一种遍历的序列一定要知道。n6、查找技术n顺序查找适合于任何线性表，最坏情况需要比较n次n二分查找只适应于顺序存储的有序表，二分查找的结束直到查找成功或子表长度为0才停止，要会计算它的次数；最坏情况需要比较log2n二分查找举例n设有有序表（5，16，23，42，58，67，79，81）使用二分法查找元素23。元素地址123456789值51623354258677981第一次第二次第三次Low=1High=9Mid=5High=4Mid=2Low=3Mid=3Mid=(Low+High)/2n7、排序技术 排序的目的、分类、各种排序的思想与时间复杂度，冒泡、

4、简单插入、简单选择的比较次数要会计算。各种排序方法的性能比较排序方法最好情况/时间最坏情况/时间空间复杂度冒泡排序n-1n(n-1)/2O(1)快速排序nlog2nn(n-1)/2O(log2n)简单插入n-1n(n-1)/2O(1)希尔排序O(n1.5)特定增量序列O(1)简单选择n(n-1)/2n(n-1)/2O(1)堆排序O(nlog2n)O(nlog2n)O(1)二、程序设计方法与风格n程序设计发展的两个阶段、风格的定义、主导风格是什么？n结构化程序设计的主要原则、GOTO语句的使用问题n面向对象程序设计 1）著名的面向对象语言有哪些：Simula、SmallTalk、c+、java

5、n2）面向对象方法和技术以对象为核心。设计原理是模拟现实世界。主要优点是可重用性、可维护性、易扩展，这是符合软件工程要求的。n3）基本概念 对象及其组成、特点。类及其与对象关系。注意：对象没有继承性，类没有多态性。 4）消息 作用及组成、类的继承性和对象的多态性实现了软件的可重用性和可扩充性。三 软件工程n3.1.1、软件危机的表现与软件工程的定义及三要素n3.1.2 软件工程过程与PDCA、软件生命周期n3.1.3 软件工程研究内容3.2 结构化分析方法n1）需求分析的任务、目的（三大模型）、工作内容、方法n2）常用工具：四种（图字树表）兔子鼠标兔子鼠标n3）分析成果3.3 结构化设计n1）

6、概要设计与详细设计的任务划分n2）设计原则：抽象、模块化、信息隐蔽、 模块独立性（内聚与耦合） 3） 概要设计方法：采用结构图，面向数据流 4） 详细设计工具：三图一码3.4 测试与调试n测试涵盖整个软件过程、测试六准则、静态测试、动态测试需要测试用例、白盒测试与黑盒测试的区别、测试实施步骤（单集验系）n调试与测试的区别、方法、静态调试是主要的调试手段四 数据库设计基础n1、基本概念 DB、DBMS、DBS、DBAS的联系与区别 常见的DBMS:Oracle、PB、DB2、 SQLServer、VF（非严格） 数据一致性、物理独立性、逻辑独立性、三级模式与两级映射、存储结构属于内模式的范畴2、数据模型nE-R模型属于概念模型、层次、网状、关系模型属于逻辑模型及两类模型的表示、候选键、主键、关系与关系模式的区别、三类完整性约束的理解。n3、关系代数与关系演算是数据库的理论基础n4、数据库的设计 概要设计与逻辑设计应该都归于软件工程的概要设计、视图集成时应注意解决四类冲突、物理设计的内容二级考