比较。堆排序，最坏要O
乘以以2为底
的对数）次比较）。
三、程序设计基础
结构化程序设计四条原则：自顶向下；逐步求精；模块化；限制使用goto语句。基本结构及特点：顺序结构（简单程序设计最基本最常用的结构）；选择结构又称分支结构（包括简单选择和多分支选择结构）；重复结构又称循环结构（可根据给定条件判断是否重复执行某一相同程序段）。面向对象的程序设计对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息操作描述了对象执行的功能，操作也称为方法或服务。类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。（消息的组成包括：接受对象的名称；消息标识符，也称消息名；零个或多个参数）继承是指能够直接获获得已有的性质和特征，而不必重复定义他们。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。
3
f多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。
四、软件工程基础
软件工程概念软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。软件周期：软件产品从提出、实现、使用和维护到停止使用退役的过程。软件生命周期三个阶段：软件定义（可行性研究，需求分析）、软件开发（概念设计、详细设计、研究、测试）、运行维护（使用、维护、退役）。主要活动阶段：①可行性研究与计划的制定；②需求分析；③软件设计；④软件实现；⑤软件测试；⑥运行和维护。结构化分析方法结构化分析方法：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。结构化分析的常用工具：①数据流图；②数据字典；③判定树，判定表；④软件需求规格说明书。结构化设计方法软件设计包括：总体设计与详细设计在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。常见的过程设计工具有：图形工具（程序流程图，NS，PAD）表格工具；（判定表）；语言工具（PDL伪码）。软件测试目的：发现错误而执行程序的过程软件测试方法：静态测试：包括检查代码，静态结构分析、代码质量度量。不实r