公共基础知识(二级).pptVIP

4444444444444444444444公共基础知识总复习主讲人：杨亦第一章数据结构与算法1、算法基本特征、时间复杂度（会计算简单算法的）、空间复杂度2、基本概念数据结构的研究内容、目的、定义、逻辑结构与存储结构线性结构几个特例（线性表、栈、队列）的特征与操作比较：顺序表不需要指针、栈和队列都有两个指针、指向位置的区别、满与空的判别顺序存储和链式存储的区别、操作的异同，各有什么优缺点，注意同样存在链栈、链队，头指针与头结点的区别。头指针：指向第一个结点；头结点：链表中为方便运算而设置的结点。a2a1an^…Head510270地址：5头结点头指针总结：顺序表的优缺点21顺序表的优点：可以方便地随机存取表中的任一结点。存取空间要预先分配，动态扩充和分配都不方便。无需为表示结点间的逻辑关系而增加额外的存储空间。顺序表的缺点：插入和删除运算不方便。须移动大量结点，效率较低。4365总结：链表的优缺点链表的优点：01插入和删除很方便。02不需要实现估计“容量”，扩充和动态分配空间很容易。03链表的缺点：04为表示结点间的逻辑关系需要增加额外的空间。05不能实现随机访问。0601040203树与二叉树根、叶子、度、深度的概念二叉树的五条性质：总个数、叶子数、高度的计算。完全二叉树中，由总结点个数求叶子与非叶子结点的简单做法。三种遍历方法：由其中两种求另一种遍历的序列一定要知道。查找技术01二分查找只适应于顺序存储的有序表，二分查找的结束直到查找成功或子表长度为0才停止，要会计算它的次数；最坏情况需要比较log2n03顺序查找适合于任何线性表，最坏情况需要比较n次02010203元素地址123456789值51623354258677981第一次第二次第三次Low=1High=9Mid=5High=4Mid=2Low=3Mid=3Mid=[(Low+High)/2]排序技术排序的目的、分类、各种排序的思想与时间复杂度，冒泡、简单插入、简单选择的比较次数要会计算。排序方法最好情况/时间最坏情况/时间空间复杂度冒泡排序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)二、程序设计方法与风格程序设计发展的两个阶段、风格的定义、主导风格是什么？结构化程序设计的主要原则、GOTO语句的使用问题面向对象程序设计著名的面向对象语言有哪些：Simula、SmallTalk、c++、java面向对象方法和技术以对象为核心。设计原理是模拟现实世界。主要优点是可重用性、可维护性、易扩展，这是符合软件工程要求的。基本概念对象及其组成、特点。类及其与对象关系。注意：对象没有继承性，类没有多态性。消息作用及组成、类的继承性和对象的多态性实现了软件的可重用性和可扩充性。三软件工程01软件危机的表现与软件工程的定义及三要素02软件工程过程与PDCA、软件生命周期03软件工程研究内容3.2结构化分析方法213需求分析的任务、目的（三大模型）、工作内容、方法常用工具：四种（图字树表）兔子鼠标分析成果3.3结构化设计概要设计与详细设计的任务划分设计原则：抽象、模块化、信息隐蔽、模块独立性（内聚与耦合）概要设计方法：采用结构图，面向数据流详细设计工具：三图一码3.4测试与调试测试涵盖整个软件过程、测试六准则、静态测试、动态测试需要测试用例、白盒测试与黑盒测试的区别、测试实施步骤（单集验系）01调试与测试的区别、方法、静态调试是主要的调试手段02四数据库设计基础DB、DBMS、DBS、DBAS的联系与区别ADBC常见的DBMS:Oracle、PB、DB2、SQLServer、VF（非严格）数据一致性、物理独立性、逻辑独立性、三级模式与两级映射、存储结构属于内模式的范畴基本概念E-R模型属于概念模型、层次、网状、关系模型属于逻辑模型及两类模型的表示、候选键、主键、关系与关系模式的区别、三类完整性约束的理解。关系代数与关系演算是数据库的理论基础数据库的设计概要设计与逻辑设计应该都归于软件工程的概要设计、视图集成时应注意解决四类冲突、物理设计的内容二