VF 全国二级公共基础知识(浓缩版NCRE).doc

第1章 数据结构与算法 1.算法特征：可行性、确定性、有穷性、拥有足够的情报（足够的输入信息和初始化信息） 2.算法的描述工具有：传统流程图；N-S结构化流程图；算法描述语言 2.算法的控制结构有：顺序；选择（也叫分支）；循环（也叫重复） 4.算法的设计方法： 1）列举法； 2）归纳法；3）递推法4）递归法5）减半递推6）回溯法， 5.递归分为直接递归（直接调用自己）和间接递归（A调用B，B再调用A） 6.算法的复杂度：时间复杂度和空间复杂度O(n) 7.数据处理：包括插入、删除、查找、更新等运算； 8.数据结构：数据元素及其关系。分为逻辑结构和物理结构 9.数据的逻辑结构：是指数据元素之间的逻辑关系的描述,包括集合、线性结构、树形结构和网状结构四种。 10.数据的存储结构也称物理结构，是数据在存储空间中的存放形式。同一种逻辑结构的数据可以有多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。 11.线性结构与非线性结构 12.线性结构：非空数据结构有且只有一个根结点；每个结点最多只有一个前驱，最多只有一个后继，该结构称为线性结构或线性表。 14.线性表的定义：（n≥0）各元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前驱；除最后一个元素外，有且只有一个后继。线性表要么是一个空表，要么可以表示为（a1,a2,a3,…,an） 15. 线性表的顺序存储结构：利用连续的存储单元依次存储线性表的数据的方式。 16..线性表的顺序存储结构的基本特征：线性表中所有元素所占的存储空间是连续的；线性表中各元素在存储空间中是按逻辑顺序依次存放的。 17.栈是逻辑结构上一种特殊的线性表，只能在栈顶删除或插入元素。操作特征：先进后出，出栈顺序。 18.线性链表：也叫单链表，是线性表的链式存储结构。在该存储结构中，每个结点由数据域和指针域两部分组成。 19.栈和队列都可以采用链式存储结构。 20.顺序表与链表的区别 A.顺序表：线性表的顺序表表示，其特点是用物理存储位置上的邻接关系来表示结点间的逻辑关系。其优点：无须为表示结点间的逻辑关系额外增加存储空间；可以方便随机存取表中的任意结点。其缺点：插入和删除运算不方便。除队尾位置外，在表的其他位置上进行插入和删除操作都必须移动大量的结点，其效率较低。 B.链表：线性表的链式存储表示，其特点是用指针来表示结点间的逻辑关系。其优点：插入和删除运算方便；链表占用的存储空间可以随时改变，不会出现空间的闲置和溢出现象。其缺点：为表示结点间的逻辑关系，需要增加额外的存储空间（指针域），存储密度比顺序表低。 21.双向链表：在单链表中的结点中增加一个指针域指向它的直接前驱，这样的链表称为双向链表（即一个链表结点含有两个指针） 22.循环链表，把单链表最后一个结点的指针域的值由NULL该为指向链表的第一个元素的地址，则整个链表就构成一个闭合的环链，这样的链表叫循环链表。相应的也有双向循环链表。 23.树：是一种非线性结构，元素间具有明显的层次特征。树是由n个结点组成的有限集合，n=0称为空树；n0时有一个根结点 24.树的特点：A.每一个树只有一个根结点。每一个结点最多只有一个前驱，它称为该结点的父结点；B.每一个结点可以有多个后继，它们都称为该结点的子结点。没有后继的结点称为叶子结点；C.一个结点所拥有的后继个数称为树中该结点的度；D.树的最大层次叫树的深度。 25.二叉树由一个根结点和两棵互不相干的子树（左子树和右子树）构成，且左右子树都是二叉树。 26.特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，分别为左子树和右子树；每个结点最多有两个子结点，即所有结点的度小于等于2；二叉树是有序树，而树上无序的，且二叉树不能颠倒，因此二叉树只有5种基本形态（二叉树、右子树、左子树、根树、空树） 27.满二叉树：除了最后一层外，每一层上的所有结点都有两个子结点的二叉树。深度为k的满二叉树，第k层上有2k-1个结点，整棵二叉树共有2k -1个结点。 28.完全二叉树：除了最后一层外，每层的结点数都达到最大值的二叉树叫完全二叉树。即本层结点树达到最大值后，才能放入下一层；若左边有空时不能将结点放入右边；最后一层只缺少右边的若干结点。满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。 29.二叉树的性质 A.在二叉树的第k层最多有2k-1个结点； B.深度为m的二叉树 最多有2m -1个结点； C.对于任意二叉树，度为0的结点（即子结点）总比度为2的结点（叶子结点）多一个； D.二叉树都是按照从上到下，从左到右的顺序 30.二叉树通常采用链式结构。由于每一个元素可以有两个后继，所以用于存储二叉树的存储结点的指针域有两个。 31. 二叉树的三种遍历