二级VF公共 基础知识.doc

第一章数据结构与算法
算法 
算法:是指解题方案的准确而完整的描述。
算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。
算法的基本要素:一是对数据对象的运算和操作,二是算法的控制结构。
算法的运算和操作:算术运算、逻辑运算、关系运算、数据传输四类。
算法的控制结构:顺序、选择、循环三种基本结构。
算法的复杂度:包括时间复杂度和空间复杂度。所谓时间复杂度是指执行算法需要的工作量。而空间复杂度是指执行这个算法所需要的内存空间。
数据结构及其操作
数据结构:包括数据的逻辑结构、数据的存储结构及各种数据结构进行的运算。
数据的逻辑结构:是指反映数据元素之间逻辑关系的数据结构。
数据的存储结构:是指数据的逻辑结构在计算机存储空间中的存放形式,也称数据的物理结构。常用的存储结构有顺序、链接、索引。
线性结构:一个非空的数据结构有且只有一个根结点,每一个结点最多有一个前件,也最多有一个后件。没有前件的结点称为根结点;没有后件的结点的称为终端结点(叶子结点)
线性表:是最简单最常用的线性结构。
线性表的顺序存储结构的特点:一是线性表中所有元素所占空间是连续的,二是各数据元素在存储空间中是按逻辑顺序依次存放的。
栈:是限定在一端进行插入与删除的顺序存储线性表,栈是按照先进后出或后进先出的原则组织数据的。
栈的基本运算:入栈、退栈、读栈。当栈已满,不能进行入栈操作,这种情况称“上溢”,当栈已空,不能退栈,称为“下溢”
队列:是指允许在一端进行插入、而在另一端进行删除的顺序存储线性表。队列是按照先进先出或后进后出的原则组织数据的。
10、队列的基本运算:入队、退队。不能进行入队操作,这种情况称为“上溢”,当队列为空,不能退队,称为“下溢”。
11、线性链表:线性表的链式存储结构。它克服了顺序存储结构的缺点,它的结点空间可以动态申请与释放。它的数据元素的逻辑次序靠结点指针指示,不需要移动数据。便于插入和删除操作。
12、链式存储结构的缺点:一是每个结点指针域需占用存储空间,二是一种非随机存储结构。
数与二叉树
树:一种简单的非线性结构。
根:没有前件的结点只有一个,称为树的根结点,简称根。
叶子结点:没有后件的结点称为叶子结点。
度:一个结点所拥有的后件个数称为该结点的度。所有结点中最大的度称为该树的度。
深度:树的最大层次称为树的深度。
二叉树:一种非线性结构。
二叉树的特点:一是二叉树只有一个根结点,二是每个结点最多有两棵子树,分别为左子树与右子树。
二叉树的基本特征:
<1>在二叉树的第K层上,最多有2k-1个结点。
<2>深度为M的二叉树最多有2M-1个结点。
<3>在任意一棵二叉树中,度为0的结点总是比度为2的结点多一个。
<4>具有N个结点的二叉树,其深度至少为[log2N]+1
<5>具有N个结点的完全二叉树的深度为[log2N]+1
二叉树的存储结构:一般采用链式存储结构。
10、二叉树的遍历:
<1>前序遍序:先访问根结点,前序遍历左子树,前序遍历右子树。
<中序遍历>:中序遍历左子树,访问根结点,中序遍历右子树。
<后序遍历>:后序遍历左子树,后序遍历右子树,访问根结点。
查找技术与排序技术
顺序查找:如线性表为无序表,或采用链式存储结构,只能用顺序查找。
二分法