二级VFP公共基础知识

1、第1章数据结构和算法1.1算法算法：指对解决方案的准确而完整的描述。算法并不等同于程序或计算机方法，因此编程不能优于算法的设计。该算法的基本特征是：它是一组严格定义操作顺序的规则，每条规则都是有效的和清晰的，并且该顺序将在有限的次数内终止。功能包括：(1)可行性；(2)确定性，算法中的每一步都必须定义清楚，没有含糊不清的解释和含糊不清的地方；(3)由于是有限的，算法必须在有限的时间内完成，也就是说，它可以在执行有限的步骤后终止，包括合理执行时间的含义；(四)信息充分。算法的基本要素：第一，数据对象的计算和操作；第二是算法的控制结构。指令系统：计算机系统可以执行的所有指令的集合。基本运算包括算术

2、运算、逻辑运算、关系运算和数据传输。算法的控制结构：序列结构、选择结构和循环结构。算法的基本设计方法：枚举、归纳、递归、递归、桶约简递归技术和回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需的计算工作量。算法空间复杂度是指执行该算法所需的内存空间。1.2数据结构的基本概念数据结构研究的三个方面：(1)数据集中数据元素之间固有的逻辑关系，即数据的逻辑结构；(2)处理数据时，计算机中各数据元素的存储关系，即数据的存储结构；(3)对各种数据结构的操作。数据结构是相互关联的数据元素的集合。数据的逻辑结构包括：(1)表示数据元素的信息；(2)表示数据元素之间的先行关系。

3、数据的存储结构包括序列、链接、索引等。线性结构条件：(1)只有一个根节点；(2)每个节点最多有一个前部和一个后部。非线性结构：不满足线性结构条件的数据结构。1.3线性表及其顺序存储结构线性表由一组数据元素组成，这些数据元素的位置仅取决于它们自己的序列号，并且这些元素之间的相对位置是线性的。在复杂的线性表中，由多个数据元素组成的数据元素称为记录，而由多个记录组成的线性表也称为文件。非空线性表格的结构特征；(1)只有一个根节点a1，它没有先行节点；(2)只有一个终端节点an，没有后续部分；(3)除根节点和终端节点外，所有其他节点只有一个前部和一个后部。节点数n称为线性表的长度，当n=0时，称为空表

4、。线性表的顺序存储结构具有以下两个基本特征：(1)线性表中所有元素占用的存储空间是连续的；(2)线性表中的每个数据元素以逻辑顺序存储在存储空间中。ai的存储器地址是ADR(ai)=ADR(a1) (i-1)k，其中ADR(a1)是第一个元素的地址，k表示每个元素占用的字节数。序列表的操作：插入和删除。1.4堆栈和队列堆栈是一个线性表，限制在一端插入和删除。允许插入和删除的一端称为栈顶，不允许插入和删除的另一端称为栈底。堆栈根据“FILO”或“LIFO”组织数据。堆栈具有存储功能。使用顶部作为堆栈的顶部，底部作为堆栈的底部。堆栈的基本操作：(1)插入元素称为堆栈操作；(2)删除元素称为堆栈回操作

5、；(3)读取栈顶元素就是将栈顶元素分配给一个指定的变量，此时指针没有变化。队列是指一个线性表，允许在一端(队列的末端)插入，在另一端(队列的头部)删除。后指针指向队列的末端，前指针指向队列的头部。队列是先进先出或后进先出的线性表。队列操作包括(1)队列操作：从队列末尾插入一个元素；(2)退出队列：从队列头删除一个元素。循环队列：s=0表示队列为空，s=1，前=后表示队列已满1.5线性链表数据结构中的每个节点对应一个存储单元，简称为存储节点。该节点由两部分组成：(1)用于存储数据元素值，称为数据字段；(2)用于存储指针，称为指针字段，用于指向上一个或下一个节点。在链式存储结构中，用于存储数据结构

6、的存储空间可以是不连续的，并且每个数据节点的存储顺序可以与由指针字段确定的数据元素之间的逻辑关系不一致。链式存储可以用来表示线性和非线性结构。线性链表，头称为头指针，头=空(或0)称为空表。如果有两个指针，左指针(Llink)指向前一个节点，右指针(Rlink)指向后一个节点。线性链表的基本操作：搜索、插入和删除。1.6树和二叉树树是一个简单的非线性结构，所有元素都有明显的层次特征。在树结构中，每个节点只有一个先行词，称为父节点，只有一个没有先行词的节点，称为树的根节点。每个节点可以有多个后件，这些后件被称为节点的子节点。没有后缀的节点称为叶节点。在树形结构中，一个节点所拥有的后继数称为该节点

7、的度，所有节点的最大度称为该树的度。树的最大高度叫做树的深度。二叉树的特点如下：(1)非空二叉树只有一个根节点；(2)每个节点最多有两个子树，分别称为节点的左子树和右子树。二叉树的基本性质：(1)在二叉树的第k级上最多有2k-1(k1)个节点；(2)深度为m的二叉树最多有2m-1个节点；(3)0度节点(即叶节点)总是比2度节点多一个；(4)具有n个节点的二叉树，其深度至少为log2n 1，其中log2n表示log2n的整数部分；(5)具有n个节点的完全二叉树的深度是log2n1；(6)让完整的二叉树有n个节点。如果从根节点开始，节点用自然数1，2，n根据顺序(从每层的左到右)(k=1，2.n)

8、，可以得出以下结论：(1)如果k=1，则该节点是根节点，并且它没有父节点；如果为k1，则该节点的父节点号为int(k/2)；(2)如果2kn，编号为k的节点的左子节点的数目为2k；否则，该节点没有左子节点(也没有右子节点)；如果2k 1n，编号为k的节点的右子节点号为2k1否则，该节点没有正确的子节点。全二叉树意味着除了最后一层之外，每层上的所有节点都有两个子节点，那么k层上有2k-1个节点，深度为m的全二叉树有2m-1个节点。完整的二叉树意味着除了最后一层之外，每一层上的节点数达到最大值，并且只有右边的几个节点在最后一层上丢失。二叉树存储结构采用链式存储结构，全二叉树和全二叉树可以顺序存储。

9、二叉树的遍历；(1)序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树；(2)中间顺序遍历(LDR)，首先遍历左子树，然后访问根节点，最后遍历右子树；(3)后顺序遍历(LRD)首先遍历左子树，然后访问右子树，最后访问根节点。1.7搜索技术顺序搜索的用法：(1)线性表是无序表；(2)桌子采用链式存放结构。二进制搜索仅适用于按顺序存储的有序表。对于长度为n的有序线性表，最坏的情况只需要比较log2n次。1.8分拣技术排序指的是将一个无序序列排序为一个有序序列，该有序序列按值的非递减顺序排列。交换排序法：(1)冒泡排序法，比较次数为n(n-1)/2；(2)快速排序法。插入类排序方法：(1)简单的

10、插入排序方法，最坏的情况需要n(n-1)/2次比较；(2)希尔排序法，最坏的情况需要O(n1.5)比较。选择类排序方法：(1)简单的选择排序方法，最坏的情况需要n(n-1)/2次比较；(2)堆排序方法，最坏的情况需要O(nlog2n)比较。第二章是程序设计的基础2.1编程设计方法和风格如何形成良好的编程风格1.源程序文档；2.数据描述方法；3.语句的结构；4.输入和输出。注释分为前言注释和功能注释。句子结构清晰第一，效率第二。2.2结构化编程结构化编程方法的四个原则是：1 .自上而下；2.逐渐完善；3.模块化；4.限制goto语句的使用。结构化程序的基本结构和特征；(1)序列结构：简单的程序设

11、计，最基本和最常用的结构；(2)选择结构：也称为分支结构，包括简单选择和多分支选择结构，根据条件选择哪个分支执行相应的语句序列；(3)循环结构：可以根据给定的条件判断同一程序段是否需要重复执行。2.3面向对象编程面向对象编程：以奥斯陆大学和挪威计算机中心在20世纪60年代后期开发的SIMULA语言为标志。面向对象方法的优点：(1)符合人类习惯的思维方法；(2)稳定性好；(3)可重用性好；(4)易于开发大型软件产品；(5)良好的可维护性。对象是面向对象方法中最基本的概念，它可以用来表示客观世界中的任何实体。面向对象编程方法中的对象是用来描述系统中客观事物的实体，它是系统的基本单元，由一组表示其静

12、态特征的属性和一组可以执行的操作组成。属性是包含在对象中的信息，操作描述对象执行的功能。操作也称为方法或服务。对象的基本特征：(1)识别的唯一性；(2)分类；(3)多态性；(4)封装；(5)良好的模块独立性。类是具有公共属性和方法的对象的集合。因此，类是对象的抽象，对象是相应类的实例。消息是在一个实例和另一个实例之间传递的信息。消息的组成包括(1)接收消息的对象的名称；(2)消息标识符，也称为消息名；(3)零个或多个参数。继承指的是直接获得现有属性和特性而不必重复定义它们的能力。继承分为单一继承和多重继承。单一继承意味着一个类只能有一个父类，而多重继承意味着一个类可以有多个父类。多态性是指当同

13、一条消息被不同的对象接受时，可能导致完全不同的行为的现象第三章是软件工程的基础3.1软件工程的基本概念计算机软件是一套完整的程序、数据和相关文件。该软件的功能包括：(1)软件是一个逻辑实体；(2)软件生产不同于硬件，没有明显的生产过程；(3)软件在运行和使用过程中没有磨损和老化问题；(4)软件的开发和运行依赖于计算机系统，受计算机系统的限制，导致软件移植的问题；(5)软件复杂度高，成本高；(6)软件开发涉及许多社会因素。软件按功能分为应用软件、系统软件和支持软件(或工具软件)。软件危机主要表现在成本、质量、生产率等问题上。软件工程是应用于计算机软件的定义、开发和维护的一套方法、工具、文档、实践

14、标准和程序。软件工程包括三个要素：方法、工具和过程。软件工程过程是一组将软件转化为输出的相互关联的资源和活动，包括四个基本活动：(1)P软件规范；(2)D软件开发；(3)C软件确认；(4)A软件进化。软件周期：从提出、实现、使用和维护到停止使用和淘汰软件产品的过程。软件生命周期有三个阶段：软件定义、软件开发、操作和维护。主要活动阶段是：(1)可行性研究和规划；(2)需求分析；(3)软件设计；(4)软件实现；(5)软件测试；(6)操作和维护。软件工程的目标和原则；目标：在给定成本和进度的前提下，开发具有有效性、可靠性、可理解性、可维护性、可重用性、适应性、可移植性、可追溯性和互操作性的产品，满足

15、用户需求。基本目标：支付更低的开发成本；满足所需的软件功能；获得更好的软件性能；开发软件易于移植；需要更低的成本；能够按时完成开发并及时交付。基本原则：抽象、信息隐藏、模块化、本地化、确定性、一致性、完整性和可验证性。软件工程的理论和技术研究内容主要包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法、开发过程、开发工具和软件工程环境。软件工程管理包括软件管理、软件工程经济学、软件心理学等。软件管理包括人员组织、进度安排、质量保证、配置管理、项目规划等。软件工程的原则包括抽象、信息隐藏、模块化、本地化、确定性、一致性、完整性和可验证性。3.2结构化方法结构化方法的核心和基础是结构化

16、编程理论。需求分析方法包括(1)结构化需求分析方法；(2)面向对象分析方法。从需求分析所建立的模型的特点来看，可以分为静态分析和动态分析。结构化方法的本质是：以数据流为中心，自上而下进行分解，建立系统的处理流程，以DFD和数据字典为主要工具建立系统的逻辑模型。结构化分析的常用工具(1)数据流图；(2)数据字典；(3)决策树；(4)决策表。数据流图：描述数据处理过程的工具，是需要理解的逻辑模型的图形表示，它直接支持系统功能建模。数据字典：与系统相关的所有数据元素的组织列表，具有精确和严格的定义，以便用户和系统分析师对输入、输出、存储组件和中间计算结果有共同的理解。判断树：从问题定义的文本描述中区

17、分判断哪些条件和判断哪些结论，根据描述材料中的连接词找出判断条件之间的从属关系、并列关系和选择关系，并据此构建判断树。决策表：类似于决策树，当数据流图中的处理依赖于多个逻辑条件的值时，即完成处理的一组动作是由某组条件的组合引起的，用决策表来描述它更合适。数据字典DD是结构化分析的核心。软件需求规范的特征：(1)正确性；(2)不含糊；(3)诚信；(4)可验证性；(5)一致性；(6)可理解性；(7)可追溯性。3.3结构化设计方法软件设计的基本目标是确定目标系统如何以更抽象的方式完成预定任务，软件设计是确定系统的物理模型。软件设计是开发阶段最重要的一步，也是将需求准确转化为完整软件产品或系统的唯一途径。从技术角度来看，软件设计包括软件结构设计、数据设计、界面设计和流程设计。结构设计：定义软件系统