考试大论坛：2011年计算机二级公共基础知识考点串讲汇总(2)

1.7查找技术

1.7.1顺序查找 (P33) 顺序查找又称顺序搜索。

对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：

(1) 线性表无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 (2) 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1.7.2二分法查找 (P33—P34)

二分法查找只适用于顺序存储的有序表。

显然，当有序线性表为顺序存储时都能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较次，而顺序查找需要比较n次。 1.8排充技术

1.8.1交换类排序法 (P34—P35) 1. 冒泡排序法

冒泡排序法是一种最简单的交换类排序方法。

假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为n(n-1)/2。 2. 快速排序法

快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。

1.8.2插入类排序法 (P35—P37) 1. 简单插入排序法

自以为插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

在简单插入排序法中，这种排序方法的效率与冒泡排序法相同。在最坏情况下，证券交易插入排序需要n(n-1)/2次比较。 2. 希尔排序法

希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。 1.8.3选择类排序法 (P37—P38) 1. 简单选择排序法

从中选出最小的元素，将它交换到表的最前面。 简单选择排序法在最坏情况下需要比较n(n-2)/2次。

log2n

2. 堆排序法

堆排序法属于选择类的排序方法。

堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的来说是很有效的。

分享到搜狐微博

第2章 程序设计基础 (P40—P45)

2.1程序设计方法与风格

程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。 源程序文档化应考虑如下几点：

(1) 符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。 (2) 程序注释：正确的注释能够帮助读者理解程序。注释一般分为序言性注释和功能性注释。 (3) 视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。

2.2结构化程序设计

2.2.1结构化程序设计的原则 (P41—P42)

结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。 2.2.2结构化程序的基本结构与特点 (P42—P43) 1. 顺序结构

2. 选择结构：选择结构又称为分支结构。 3. 重复结构：重复结构又称为循环结构。 2.3面向对象的程序设计

今天面向对象方法已经发展成为主流的软件开发方法。 一些著名的面向对象语言(如C++、Java) 2.3.2面向对象方法的基本概念 (P45—P48) 1. 对象

对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体。

面向对象的程序设计方法中涉及的对象由一组表示其静态特征的属性和它可执行的一组操作组成。

(4) 封装性。

2. 类(Class)和实例(Instance)

将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法方法的对象的集合。所以，类是对象的抽象，而一个对象则是其对应类的一个实例。 3. 消息

对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递的信息。 4. 继承

继承是面向对象的方法的一个主要特征。

第3 章 软件工程基础

3.1软件工程基本概念

3.1.1软件定义与软件特点 (P50)

计算机软件是包括程序、数据及相关文档的完整集合。

可见软件由两部分组成：一是机器可执行和程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。 软件的特点：

① 软件是一种逻辑实体，而不是物理实体，具有抽象性。 ② 软件的生产与硬件不同，它没有明显的制作过程。 ③ 软件在运行、使用期间不存在磨损、老化问题。

④ 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题。

⑤ 软件复杂性高，成本昂贵。 ⑥ 软件开发涉及诸多的社会因素。 3.1.2软件危机与软件工程 (P51—P52) 软件工程概念的出现源自软件危机。

20世纪60年代末以后，“软件危机”。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。

1968年在北大西洋公约组织会议(NATO会议)上，讨论摆脱软件危机的办法，软件工程作为一个概念首次被提出。

软件工程包括个要素，即方法、工具和过程。 3.1.3软件工程过程与软件生命周期 (P52—P53) 2.软件生命周期

通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。

3.1.4软件工程的目标与原则(P53—P54) 1. 软件工程的目标

软件工程内容主要包括：软件开发技术和软件工程管理。 3.1.5软件开发工具与软件开发环境 (P54) 1. 软件开发工具 (VB、VC++、VFP) 2. 软件开发环境

软件开发环境或称软件工程环境是全面支持软件开发全过程的软件工具集合。 计算机辅助软件工程(CASE) 3.2结构化分析方法

3.2.1需求分析与需求分析方法 (P53—P59) 1. 需求分析

(1) 需求分析阶段的工作

需求分析阶段的工作，可以概括为四个方面： ① 需求获取 ② 需求分析

③ 编写需求规格说明书 ④ 需求评审 2. 需求分析方法 常见的需求分析方法有：

① 结构化分析方法。主要包括：面向数据流的结构化分析方法(SA)面向数据结构的Jackson方法(JSD)面向数据结构的结构化数据系统开发方法(DSSD) ② 面向对象的分析方法(OOA) 3.2.2结构化分析方法 (P55—P59) 2.结构化分析的常用工具 (1) 数据流图(DFD) (2) 数据字典(DD)

数据字典是结构化分析方法的核心。 (3) 判定树 (4) 判定表

3.2.3软件需求规格说明书 (P59—P60)

软件规格说明书(SRS)是需求分析阶段的最后成果，是软件开发中的重要文档。 软件需求规格说明书的作用是：

① 便于用户、开发人员进行理解和交流。

② 反映出用户问题的结构，可以作为软件开发工作的基础和依据 ③ 作为确认测试和验收的依据。 3.3结构化设计方法

3.3.1软件设计基本概念 (P60—P62) 1.软件设计的基础

软件设计分两步完成：概要设计和详细设计。 2.软件设计的基本原理 (1) 抽象 (2) 模块化 (3) 信息隐蔽 (4) 模块独立性

模块独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立软件的模块独立性使用耦合性和内聚性两个定性的度量标准。

① 内聚性：内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。 ② 耦合性：耦合性是模块间互相连接的紧密程度的度量。

耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合。 3.3.3详细设计 (P67—P71) 几种主要的工具： 1. 程序流程图(PFD) 2. N-S (盒图)

3. PAD图 PAD图是问题分析图(Problem Analysis Diagram)的英文缩写。 4. PDL

过程设计语言(PDL)也称为结构化的英语和伪码。 3.4软件测试

软件测试的投入，通常其工作量、成本占软件开发总工作量、总成本的40%以上。 软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命期的过程。 3.4.1软件测试的目的 (P71)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库考试大论坛：2011年计算机二级公共基础知识考点串讲汇总(2)在线全文阅读。