全国VFP计算机二级公共基础知识

公共基础知识 内容：

? 考试大纲

? 数据结构与算法 ? 程序设计基础 ? 软件工程基础 ? 数据库设计基础 考试大纲 考试内容

一、基本数据结构与算法

1、算法的基本概念；算法复杂度的概念和意义(空间复杂度与时间复杂度)。

2、数据结构的定义；数据的逻辑结构和存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3、线性表的定义；线性表的顺序存储结构及其插入删除运算。 4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5、线性单链表，双向链表与循环链表的结构及其基本运算。

6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7、顺序查找与二分查找算法；基本排序算法(交换类排序、选择类排序、插入类排序)。 二、程序设计基础

1、程序设计方法与风格。 2、结构化程序设计。

3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础

1、软件工程的基本概念；软件生命周期概念；软件工具与软件开发环境。 2、结构化分析方法；数据流图，数据字典，软件需求规格说明书。 3、结构化设计方法； 总体设计，详细设计。

4、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实施；单元测试，集成测试，系统测试。

5、程序的调试，静态调试与动态调试。 四、数据库设计基础

1、数据库的基本概念；数据库，数据库管理系统，数据库系统。 2、数据模型；实体联系模型及E-R图，从E-R图导出关系数据模型。

3、关系代数运算，包括集合运算及选择、投影、连接运算；数据库规范化理论。 4、数据库设计方法和步骤；需求分析、概念设计、逻辑设计和物理设计的相关策略。 数据结构与算法 关键考点

? 算法基本概念及算法复杂度 ? 数据的存储结构 ? 栈和队列 ? 线性链表

? 二叉树基本概念及其特性 ? 查找技术 算法的基本概念 1、算法

算法是指解题方案的准确而完整的描述。

注意：算法与数学上的计算方法不是同一个概念。算法要考虑计算机的特点，要考虑计算方法的可行性。

算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时，总是先设计算法，然后进行编程。 2、算法的基本特征 可行性 确定性 有穷性

拥有足够的情报

算法是一个动态概念，强调实际的执行过程。

数学上的计算方法是一个静态概念，注重理论上的正确性。 数学上的计算方法是设计算法的基础。 例题：A

1. 算法的有穷性是指

A．算法程序的运行时间是有限的 B．算法程序所处理的数据量是有限的 C．算法程序的长度

D．算法只能被有限的用户使用 3、算法的基本要素

算法中对数据的运算和操作

基本的运算和操作有：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构

控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。 4、算法设计基本方法

列举法 列举所有可能情况，检测其中符合条件的结果。 归纳法 列举若干特殊情况，分析归纳出一般规律。

递推 从已知初始条件出发，逐步推导出中间及最后结果。

递归 将复杂问题归结为简单问题，在归结为更简单问题，… 。 减半递推技术 将问题规模“减半”，并重复该“减半” 的过程。

回溯法 分析问题，找出某些线索，沿线索逐步试探。若试探成功，则继续，若试探失败，则回退。直至问题解决。 5、算法的时间复杂度

指执行算法所需要的计算工作量

算法工作量的度量应与计算机、编程语言、编程细节等无关。 算法的工作量用算法所执行的基本运算次数衡量。 算法工作量是问题规模的函数：算法的工作量= f (n) 度量方法有： 平均性态分析 计算其加权平均值 最坏情况分析 计算其基本运算的最大次数 6、算法的空间复杂度

指执行算法所需要的存储空间 包括：算法程序所占据的存储空间 待处理数据所占据的存储空间

算法程序执行中所需要的额外存储空间

如果额外存储空间大小不随问题规模变化，则称之为算法原地工作。 降低算法的空间复杂度，应从数据的存储空间和额外空间入手。 例题：

2. 下列叙述中正确的是

A．算法的效率只与问题的规模有关，而与数据的存储结构无关 B．算法的时间复杂度是指执行算法所需要的计算工作量 C．数据的逻辑结构与存储结构是一一对应的 D．算法的时间复杂度与空间复杂度一定相关 3. 算法的空间复杂度是指

A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量

C.算法程序中的语句货指令条数

D.算法在纸箱过程中所需要的临时工作单元数 4.算法的时间复杂度是指

A.算法的执行时间 B.算法所处理的数据量 C.算法程序中的语句或指令条数

D.算法在执行过程中所需要的基本运算次数 第2节 数据结构的基本概念

? 计算机处理数据，主要考虑两个方面：

? 一 、提高数据处理的速度？ ? 二 、节省存储空间？

? 数据结构主要研究三个方面的问题：

? （1）数据的逻辑结构：各数据元素间所固有的逻辑关系 ? （2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系 ? （3）对各种数据结构进行的运算。

根据数据元素间关系的基本特性，有四种基本数据结构

（集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图