二级vf公共笔必考点.doc

第一章：数据结构与算法
第一节算法的基本概念
1、算法：是一组严谨地定义运算的规则，并且每一个规则都有效的，且是明确的，此顺序将在有限的次数下终止。解题方案的准确而完整的描述（算法是一个操作序列、有线长度、目的是解决某类问题）
（算法不等于程序，当然也可以作为算法的描述，但程序还需考虑很多与方法和分析无关的细节问题）
算法的基本特征
可能性确定性有穷性拥有足够的情报（输入和输出）
算法的基本要素
一、对数据对象的运算和操作（算术、关系、逻辑运算和数据传输（赋值、输入、输出））
二、算法的控制结构（控制结构一般分为顺序、选择、循环三种基本结构）
描述算法有传统流程图N-S结构化了流程图、算法描述语言等
算法的复杂度
时间复杂度（次数）：运算的次数
空间复杂度（内存空间）执行算法需要的内存空间（包括：程序所占空间、输入的数据所占空间、运算所需的空间）
算法设计的基本方法
列举法（列举所有的解决方案）
归纳法（特殊）一般）
递推法（已知）未知）
递归法（逐层分解）
减半递推法（对问题分而治之）
回溯法（查找错误）
注意：1、算法优先于程序
第二节数据库结构的基本概念
计算机处理数据，主要靠考虑两方面：
一是数据处理的速度
二是节省存储空间
数据结构主要研究三方面的问题：
一是数据的逻辑结构（线性结构、非线性结构）：个数据元素间所固有的逻辑关系（独立于计算机）
二是数据的存储结构（物理结构）（顺序存储、链式存储）：个数据元素在计算机中的存储关系（数据逻辑结构在计算机中的表示）
三是对各种数据结构进行的运算（检索、排序、删除、修改）
数据结构的概念
数据——需要处理的数据元素的集合
结构——关系，是集合中各个数据元素之间存在的关系
数据结构：反映数据元素之间逻辑关系的数据元素集合的表示
逻辑结构：反映数据元素之间逻辑关系的数据结构
存储结构：在计算机存储空间的存放形式
数据结构的图形表示
结点前件结点后件结点根结点
线性结构和非线性结构
空的数据结构：一个数据结构中一个数据元素都没有
线性结构和非线性结构：数据元素之间前后件关系的复杂程度，将数据结构分
线性结构：（线性式、栈、队列）
有且只有一个根结点
每个结点最多有一个前件，也最多有一个后件
非线性结构：不必满足以上两个条件（树形结构、图形结构）
第三节线性表和顺序存储结构
线性表：线由一组数据元素组成。是最简单、最常用的一种数据结构
非空线性表有以下特征：
有且只有一个根结点
有且只有一个终结点
除以上二姐店外，每个结点有且只有一个前件，也有且只有一个后件
线性表的顺序存储结构（逻辑相临，物理相临）
线性表中所有元素所占的存储空间是连续的
数据元素在存储空间中是按逻辑顺序依次存放的（线性表的顺序存储结构是一种随机存取的存储结构。可随机访问任意一个结点）
３、线性表的插入运算（最坏的情况N）
４、线性表的删除运算(最坏的情况N-1)
第四节栈和队列（不需要移动元素）
栈及其运算（既可以是顺序存储也可以是链式存储）
栈：限定在一段进行插入与删除的线性表（垃圾桶）
入栈原则：先进后出，后进先出
栈的特点
栈顶元素总是最后被插入元素，也是最早被删除的元素
栈底元素总是最早被插入的元素，也是最晚被删除的元素
栈具有记忆作用
在顺序存储结构下，栈的插入与删除运算不需要移动表中其他数据
栈顶指针，TOP动态反映了栈中元素的变化情况
栈和线性表实现方法类似——顺序和链接
注意：先进行读栈、删栈（出栈）、插入（入栈）
尾大于头，则尾减头尾小于头，则容量加（尾减头）
2、队列及其运算（入列，尾指针加1；退列，头指针加1）
允许在一端进行插入、而在另一端进行删除的线性表，即“先进选出，后进后出”的原则
第五节线性链表
注意：线性链表在插入和删除过程中均不发生数据元素移动的现象，只需改变有关结点的指针即可

插入和删除时要移动大量的数据元素
分配空间后，如果存储空间已满，会出现“上溢”错误
多个线性表同时工作时，需要大量的连续空间
假设每个数据结点对应一个存储单元，这种存储单元称为存储结点，简称结点

在链式存储结构中，存储空间可以不连续。链式存储方式既可以用于线性结构，也可以用与非线性结构。再用非线性结构时，其指针的个数要多一些
链式存储方法
链式存储结构不要求逻辑上相邻的数据物理上也相邻，结点间的关系有附加的地址（指针）为实现
在链存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称数据区；另一部分用于存放指针，称指针区
优点：
在逻辑上相邻的元素在物理可以不相邻
存储时不用事先准备，这样会节约存储空间
对增加、删除接点操作简单，不必移动结点，只要改结点中指针值
缺点：除存储本身信息外，还有表示其直接后继信息的指针域，因此其密度小、存储空间利用率低
插入元素、
删除元素
第六节树和二叉树