13．二分法查找及其特点
重点掌握二分法查找的适用对象、查找的方法与查找效率。
二分法查找只适用于顺序存储的有序表。此处的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相信元素值相等）。
设有序线性表的长度为n，被查元素为x，则二分查找的方法如下所述。
将x与线性表的中间项进行比较：
若中间项的值等于x，则说明查到，查找结束；
若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；
若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0（说明线性没有这个元素）为止。
显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。
14．排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常见的排序方法主要有交换类排序、插入类排序和选择类排序。各种排序方法的特点以及在最坏情况下的排序效率是考试的重点。
（1）交换类排序法
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。
快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。
（2）插入类排序法
插入类排序法主要有简单插入排序法和希尔排序法。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。
希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。
（3）选择类排序
选择类排序主要有简单选择类排序法和堆排序法。
简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。
(责任编辑：计算机基础知识 www.dxs89.com) www.dxs89.com
堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, …, hn），当且仅当满足条件：
或
(i=1, 2, …, n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。
堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。
1.3.2 程序设计基础
1．程序设计方法与风格
除了好的程序设计方法和技术外，程序设计风格也是很重要的内容。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。要形成良好的程序设计风格，主要应注重和考虑下述一些因素。
（1）源程序文档化
符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。
程序注释：注释一般分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分，它给出程序的整体说明；而功能性注释的位置一般嵌在源程序体中，主要描述其后的语句或程序做什么。
视觉组织：可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。
（2）数据说明的方法
主要包括数据说明的次序规范化、说明语句中变量安排有序化和使用注释来说明复杂数据结构等。
（3）语句的结构
语句构造应该简单直接，不应该为提高效率而把语句复杂化。
（4）输入和输出
输入和输出方式和格式应尽可能方便用户的使用。
2．结构化程序设计
结构化程序设计的主要原则、设计要素应是重点掌握的内容。
由于软件危机的出现，人们开始研究程序设计方法，其中最受关注的是结构化程序设计方法。结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化、限制使用goto语句。
在结构化程序设计的具体实施中，要注意把握如下要素。
（1）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。
（2）使用的控制结构只准许有一个入口和一个出口。
（3）程序语句组成容易识别的块，每块只有一个入口和一个出口。
（4）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。
（5）语言中所没有的控制结构，应该采用前后一致的方法来模拟。
（6）严格控制goto语句的使用。
3．面向对象的程序设计及其重要概念
面向对象的程序设计方法及其有关概念是重点掌握的内容，也是考试的重点。
面向对象的程序方法主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。它具有与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好等优点。
在面向对象的程序方法中，有如下重要的概念。
（1）对象
用来表示客观世界中的任何实体，即应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象。它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。
操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。
（2）类和实例
将属性、操作相似的对象归为类，即是具有共同属性、共同方法的对象的集合。因此，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。
（3）消息
面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息，它请示对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。一个消息由接收消息的对象的名称、消息标识符（即消息名）、零个或多个参数组成。
（4）继承
继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当做基类来引用，则新类相应地可当做派生类来引用。一个类的上层可以有父类，下层可以有子类。一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。
（5）多态性
对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。
1.3.3 软件工程基础
1．软件定义与软件特点
软件的定义是重点掌握的内容。
计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。它具有以下特点：
（1）软件是一种逻辑实体，而不是物理实体，具有抽象性。
（2）软件的生产与硬件不同，它没有明显的制作过程。
（3）软件在运行、使用期间不存在磨损、老化问题。
（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。
（5）软件复杂性高，成本昂贵。
（6）软件开发涉及诸多的社会因素。
(责任编辑：计算机基础知识 www.dxs89.com)
www.dxs89.com
2．软件危机与软件工程
重点掌握软件危机与软件工程的概念，软件工程产生的背景、研究目标与研究内容。
软件工程概念的出现源自软件危机。
软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。主要表现在：软件需求的增长得不到满足、软件开发成本和进度无法控制、软件质量难以保证、软件不可维护或维护程度非常低、软件的成本不断提高、软件开发生产率的提高赶不上硬件的发展和应用需求的增长等。
为了消除软件危机，逐步形成了软件工程的概念，软件工程是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。其主要思想是强调在软件开发过程中需要应用工程化原则。
软件工程具有方法、工具和过程三个要素。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。
软件工程的目标是，在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。