全国VFP计算机二级公共基础知识概要.ppt

数据结构与算法 查找技术 1、顺序查找从线性表的第一个元素开始，依次与指定数据比较，若相等则查找成功，若比较的所有元素都不相等，则查找失败。最坏情况的比较次数为表长n，平均情况为n/2。无序顺序表的查找只能采用顺序查找的方法。线性表在链式存储时也只能采用顺序查找的方法。 2、二分法查找在顺序存储的线性表为有序的情况下，可以使用二分法查找。方法为：将待查数据与线性表的中间项比较： 若相等，则查找成功； 若小于，则在线性表的前半部分进行二分法查找； 若大于，则在线性表的后半部分进行二分法查找； 反复进行直到相等(查找成功)或子表长度为0(查找失败)。 数据结构与算法 排序技术 1、交换类排序起泡排序 最坏情况下的比较次数为 n(n-1)/2 。 快速排序 最坏情况下的比较次数为 n(n-1)/2 。 2、插入类排序简单插入排序 最坏情况下的比较次数为 n(n-1)/2 。 希尔排序 最坏情况下的比较次数为 O( n 1.5) 。 3、选择类排序简单选择排序 最坏情况下的比较次数为 n(n-1)/2 。堆排序 最坏情况下的比较次数为 O( n log2n) 。 数据结构与算法 本章重点 1、算法是问题处理方案正确而完整的描述，算法的效率与数据的存储结构有密切的关系。 2、数据的逻辑结构在计算机中的表示(存储方式)称为数据的存储结构(物理结构)。一种逻辑结构可以有多种存储结构。 3、在长度为 n 的顺序表中，插入或删除一个元素平均需要移动一半元素。 4、栈是特殊的线性表，具有记忆作用。特点是“先进后出(后进先出)”。栈顶指针动态反映了栈中元素的变化情况。 5、队列是特殊的线性表。特点是“先进先出(后进后出)”。队头和队尾指针动态地反映了队列中元素的变化情况。 6、线性链表是线性表的链式存储结构。在线性链表中，各元素节点的存储空间可以不连续，存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需要移动数据元素。 7、二叉树是一种非线性结构。主要性质有：第k层上最多有 2 k-1 个结点 深度为 m 时，最多有2 m –1 个结点度为0的结点比度为2的多一个 深度至少为[ log2n ]+1 数据结构与算法 本章重点 8、满二叉树是二叉树的特殊形态，满二叉树的各层结点都达到最大值，叶结点只出现在最后一层。 9、完全二叉树是二叉树的特殊形态，完全二叉树除最后一层外，各层结点都达到最大值，叶结点只出现在最后两层。满二叉树属于完全二叉树。 10、根据扫描根结点的顺序，按照先左后右的原则，遍历二叉树有三种方法：前序遍历、中序遍历、后序遍历。 11、在长度为 n 的线性表中进行顺序查找，最坏情况需要比较 n 次。 12、在长度为 n 的线性表中进行对分查找，最坏情况需要比较 log2n 次。但对分查找只适用于有序顺序表。 13、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况下需要比较的次数为 n(n-1)/2 。 程序设计基础 关键考点 结构化设计的原则 面向对象方法的基本概念 程序设计基础 程序设计方法与风格 1、程序设计方法就程序设计的方法和技术的发展而言 主要经历了结构化程序设计和面向对象程序设计两个阶段 2、程序设计风格程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序的结构清晰合理，使程序代码便于维护。程序设计风格的主导：“清晰第一，效率第二”。主要因素： 源程序文档化 数据说明的方法 语句的结构 输入和输出 程序设计基础 结构化程序设计 1、结构化程序设计要求把程序的结构限制为顺序、选择和循环三种基本结构。 2、结构化程序设计的原则自顶向下 先总体后细节，先全局后局部。逐步求精 对复杂问题设计子目标过度，逐步细化。模块化 将复杂问题分解为若干简单问题。限制使用GOTO语句 防止造成程序逻辑结构混乱。 3、三种基本结构顺序结构 选择结构 循环结构 4、特点所有控制结构由三种基本结构组成各个模块单入口单出口模块的内聚性强 模块间的偶合性低 程序设计基础 面向对象的程序设计 1、面向对象面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现实生活中常用的思维方法来描述客观事物，是系统中的对象及对象间的关系能如实反映事物及其关系。 2、主要优点与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好 3、基本概念对象 类和实例消息 继承多态性 程序设计基础 本章重点 1、程序设计并不等于编程，编程只是程序设计过程中的一小步。 2、结构化程序设计要求把程序的结构限制为顺序、选择、循环