打印本文 
关闭窗口 在二叉树的第K层上最多有2的K-1次方个结点
深度为M的二叉树最多有2的M次方-1个结点
具有N个结点的二叉树，其深度至少为[log2N]+1，其中对数部分取整数
满二叉树与完全二叉树
二叉树的遍历；前序，中序，后序遍历
遍历方法：可先按要求逐个遍历个子树，然后进行排序
顺序查找最坏需比较N次
二分法查找最坏需比较log2N次
冒泡排序法最坏需比较N（N-1）/2次
简单插入排序法最坏需比较N（N-1）/2次
希尔排序法最坏需比较O（N的1.5次方）次
简单选择排序法最坏需比较N（N-1）/2次
堆排序法最坏需比较O（Nlog2N）次
二 程序设计基础
程序设计方法主要经过了结构化程序设计和面向对象的程序设计阶段
注释分为序言性注释和功能性注释
结 程序的质量与GOTO语句的数量成反比
构
程 顺序结构
化 三种基本结构 选择结构 当型循环结构----先判断后执行
序 重复结构（循环结构）
设 直到型循环结构----先执行后判断
计
选用的控制结构只准许有一个入口和一个出口
面向对象的方法和技术以对象（类）为核心
面 1 创建该类的实例，从而直接使用
向
对 两种方法可以重复是用一个对象类 2 从它派生出一个满足当前需要的新类
象 对象的基本特点：标识惟一性、分类性、多态性、封装性，模块独立性好
的 对象是类的实例，消息是实例之间传递的信息
程 消息构成：接收消息的对象的名称，消息名，零个或多个参数
序 （例如：MyCircle.show(GREEN)） MyCircle是接收对象名称show是消息名GREEN是参数
设计 继承具有传递性，继承分单继承和多重继承
三 软件工程基础
计算机软件是包括程序，数据及相关文档的完整集合
计算机软件定义：与计算机系统的操作相关的计算机程序，规程，规则以及可能有的文件文档及数据
软件按功能可以分为；应用软件，系统软件，支撑软件（工具软件）
软件工程的三个要素：方法，工具，过程
软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程
软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件技术管理
软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性
软件开发环境是全面支持软件开发全过程的软件工具集合
结构化分析方法：
软件开发方法包括：分析方法，设计方法，程序设计方法
需求分析将创建所需的数据模型，功能模型，控制模型
需求分析阶段的工作：需求获取，需求分析，编写需求规格说明书，需求评审
需求分析方法：结构化分析方法（包括面向数据流的结构化分析方法、面向数据结构的Jackson方法、面向数据结构的结构化数据系统开发方法），面向对象的分析方法
结构化方法包括；结构化分析方法，结构化设计方法，结构化编程方法
结构化分析方法常用工具：数据流图（图符：加工，数据流，存储文件，源或潭），数据字典，判定树，判定表
数据字典是结构化分析方法的核心
数据字典的作用是对DFD中出现的被命名的图形元素的确切解释
判定表或判定树是以图形的形式描述数据流图的加工逻辑
结构化设计方法：
•软件设计是确定系统的物理模型
•软件设计包括软件结构设计，数据设计，接口设计，过程设计
•软件设计分两步：概要设计和详细设计
•衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准
•内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量
•耦合性是模块间相互连接的紧密程度的度量
1.概要设计
•常用的软件结构设计工具是结构图（图符：一般模块，数据信息，控制信息）
•经常使用的结构图有四种模块类型：传入模块，传出模块，变换模块，协调模块
•数据流类型：变换型，事务型
•变换型系统结构图由输入，中心变换，输出三部分组成
2.详细设计
•常见的过程设计工具有 图形类：程序流程图（图符：控制流，加工步骤，逻辑条件）
N-S图
PAD图
语言类：PDL
•型：顺序型，选择型，先判断重复型，后判断重复型，多分支选择型
打印本文 关闭窗口