计算机等级考试vfp复习纲要(必备)[].docVIP

2011年计算机等级考试VFP复习纲要 第 1 章 数据结构与算法 考点1:算法具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报。 确定性:是指算法中每一个步骤都必须是有明确定义的,不允许模棱两可的定义 有穷性:是指算法必须能在有限的时间内做完 一个算法由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构 考点2:算法复杂度包括时间复杂度和空间复杂度 时间复杂度 执行算法所需要的计算工作量 空间复杂度 执行这个算法所需要的内存空间 考点3:数据结构 一:讨论的问题:1.数据元素之间的逻辑关系,即数据的逻辑结构 2.数据元素在计算机中的存储关系,即数据的存储结构 3.对各种数据结构进行的运算 考点4:数据结构分为两大类型：线性结构与非线性结构。 （1）如果一个非空的数据结构满足下列两个条件： ① 有且只有一个根结点； ② 每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。 考点5:线性表 特点: (1) 线性表中所有元素所占的存储空间是连续的 (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 考点5: 栈的基本概念 栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。 栈是按照“先进后出”或“后进先出”的原则组织数据的。 考点6:队列的基本概念 队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。当表中没有元素时称为空队列。即先进先出表。循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用 考点7: 链表 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。 考点8:二叉树性质 (1) 在树结构中,每一个结点只有一个前件,称为父结点,没有父结点的只有一个,成为根结点 (2) 没有后件的结点成为叶子结点 (3) 一个结点所拥有的后件个数称为该结点的度,在树中,所有结点中最大的度称为树的度 (4) 树的最大层次称为树的深度 (5) 在二叉树的第k层上,最多有2^(k-1)个结点 (6) 深度为m的二叉树最多有2^m-1个结点 (7) 任意一棵二叉树,度为0的结点(即叶子结点)总是比度为2的结点多一个 (8) 满二叉树:除最后一层外,每一层上的所有结点都有两个子节点 (9) 完全二叉树:除最后一层外,每一层上的结点数都达到最大值,在最后一层上只缺少右边的若干结点 考点9: 二叉树的遍历 根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。 （1）前序遍历 先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树 时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。 （2）中序遍历 先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子 树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图 1-1 中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列） （3）后序遍历 先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子 树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 考点10:各种排序的复杂度 (1)顺序查找需要比较n 次 (2)冒泡排序在最坏的情况下需要比较次数为n(n-1)/2 。 (3)简单插入排序法，最坏情况需要n(n-1)/2 次比较； (4)希尔排序法，最坏情况需要O(n1.5)次比较。 (5) 简单选择排序法，最坏情况需要n(n-1)/2 次比较； (6)堆排序法，最坏情况需要O(nlog2n)次比较。 第二章:程序设计基础 考点1:结构化程序设计的原则 (1) 自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标； (2) 逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化； (3) 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 (4) 限制使用goto 语句：在程序开发过程中要限制使用goto 语句。 考点2:结构化程序的基本结构 结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。 考点3: 面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 对象是面向对象方法中最基本的概念,主要特点: (1)标识惟一型 (2)分类性（3）多态性 (4)封装性 (5)模块独立性好 考点4:消息:对象间