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

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