搜索
..数据：是对客观事物的符号表示。数据元素：是数据的基本单位，也称节点（node）或记录（record）。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据项：有独立含义的数据最小单位，也称域(field)。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计）物理结构（存储结构）：数据结构在计算机中的表示。（算法实现）存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。算法：对特定问题求解步骤的一种描述。算法的五个重要特性：有穷性，确定性，可行性，输入和输出。算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。衡量算法效率的方法：事后统计法和事前分析估算法。算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))，称T(n)为算法的(渐近)时间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。..栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目；空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。存储位置：LOC(i,j)=LOC(0,0)+(b2*i+j)L结点:包含一个数据元素及若干指向其子树的分支；结点的度:结点拥有的子树；树的度:树中所有结点的度的最大值；叶子结点:度为零的结点；分支结点:度大于零的结点树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的树的集合。二叉树的性质：性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)性质2：深度为k的二叉树上至多含2k-1个结点。（k≥1）性质3:对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。性质4:具有n个结点的完全二叉树的深度为log2n+1。满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。路径长度：路径上分支的数目。树的路径长度：树根到每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL(T)=wklk带权路径长度最小的二叉树，称为最优树二叉树或赫夫曼树。关键路径：路径长度最长的路径。..顶点：数据元素vi称为顶点边、弧：P(vi,vj)表示顶点vi和顶点vj之间的直接连线，在无向图中称为边，在有向图中称为弧。任意两个顶点构成的偶对(vi,vj)∈E是无序的，该连线称为边。是有序的，该连线称为弧。弧头、弧尾：带箭头的一端称为弧头，不带箭头的一端称为弧尾。顶点的度(TD)=出度(OD)+入度(ID)图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历图的路径：深度优先搜索和广度优先搜索。排序的分类：按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序一、名词总结：..ADT：抽象数据型是一个数学模型和在该模型上定义的操作的集合线性表：线性表是由n(n≥0)个相同类型的元素组成的有序集合。栈：线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。队列：将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是一种先进先出的线性表。串：线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。广义表：由零个原子，或若干个原子或若干个广义表组成的有穷序列。树：1、一个结点x组成的集{x}是一株树(Tree)，这个结点x也是这株树的根。2、假设x是一个结点，T1，T2，…，Tk是k株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，…，Tk。这些边也叫做分支，T1，T2，…，Tk称作根x的树之子树。二叉树：有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。满二叉树：深度为k且有2k－1个结点的二叉树称为满二叉树。..完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，称之为完全二叉树。线索二叉树：若结点p有左孩子，则p-lchild指向其左孩子结点，否则令其指向其（中序）前驱。若结点p有右孩子，则p-rchild指向其右孩子结点，否则令其指向其（中序）后继。堆：如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最大堆。同样，如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最小堆。选择树：一棵选择树是一棵二叉树，其中每一个结点都代表该结点两个儿子中的较小者。这样，树的根结点就表示树中最小元素的结点。二叉排序树：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1、若它的左子树非空，则左子树上的所有结点的值均小于它的根结点的值。2、若它的右子树非空，则右子树上的所有结点的值均大于或等于它的根结点的值。3、它的左右子树分别为二叉排序树。..图：一个图G=（V，E）是一个由非空的有限集V和一个边集E所组成的。若E中的每条边都是顶点的有序对（v,w），就说该图是有向图（directedgraph，digraph）。若E中的每条边是两个不同顶点无序对，就说该图是无向图，其边仍表示成（v,w）。开放树：连通而无环路的无向图称作开放树。最小生成树：设G=(V,E)是一个连通图，E中每一条边(u,v)的权为C(u,v)，也叫做边长。图G的一株生成树(spanningtree)是连接V中所有结点的一株开放树。将生成树中所有边长之总和称为生成树的价(cost)。使这个价最小的生成树称为图G的最小生成树。无向图双连通分量：设Vi是Ei中各边所连接的点集（1≤i≤k）,每个图Gi=(Vi,Ei)叫做G的一个双连通分量。双连通图：若对V中每个不同的三元组v,w,a；在v和w之间都存在一条不包含a的路，就说G是双连通的强连通性：设G=（V,E）是一个有向图，称顶点v,w∈V是等价的，要么v=w；要么从顶点v到w有一条有向路，并且从顶点w到v也有一条有向路。拓扑排序：给定一个无环路有向图G=(V,E),各结点的编号为v=(1,2,…,n)。要求对每一个结点i重新进行编号，使得若i是j的前导，则有Label[i]label[j]。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点i到结点j存在一条边，则在线性序列中，将i排在j的前面。..AOE网：在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络,简称AOE网。关键路径：在AOE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。查找表：由同一类型的数据元素（或纪录）构成的集合。关键字：数据元素中某一数据项的值，用以表示一个数据元素。AVL树：AVL树或者是一颗空二叉树，或者具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过1。B-树：B-树是一种非二叉的查找树除了要满足查找树的特性，还要满足以下结构特性：一棵m阶的B-树：（1）树的根或者是一片叶子(一个节点的树),或者其儿子数在2和m之间。（2）除根外，所有的非叶子结点的孩子数在m/2和m之间。（3）所有的叶子结点都在相同的深度。B+树：B-树的一种变形，二者区别在于：1、有k个子结点的结点必然有k个关键码；..2、非叶子结点仅具有索引作用，与记录有关的信息均放在叶结点中。地址散列法：被查找元素的存储地址=Hash(Key)。堆分类：把具有如下性质的数组A表示的二元树称为堆（Heap）:(1)若2*i≤n，则A[i].key≤A[2*i].key;(2)若2*i+1≤n，则A[i].key≤A[2*i+1].key;小顶堆把具有如下性质的数组A表示的二元树称为堆（Heap）:(1)若2*i≤n，则A[i].key≥A[2*i].key;(2)若2*i+1≤n，则A[i].key≥A[2*i+1].key;大顶堆词典排序：设集合S中的元素为整数元组，关系≤为S的线性序，对两个元素(s1,s2,…,sp)和(t1,t2,…,tq)存在(s1,s2,…,sp)≤(t1,t2,…,tq)，当存在一个整数j，1≤j≤max[p,q]，使得sj≤tj，且所有1≤i＜j，si＝ti；或者p≤q，并且si＝ti，1≤i≤p，则关系≤称为词典序。归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序序列。..索引：指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。二、重要算法总结第二章：1、模式匹配法（KMP算法）2、串的Substr算法第三章：1、二叉树的先、中、后序遍历（递归算法）2、二叉树的中序非递归遍历（辅助栈、非辅助栈）3、二叉树交换左右子树；4、二叉树求深度、结点赋层号5、哈夫曼树的构造第四章：1、DFS、BFS2、最小生成树3、强连通性4、拓扑排序5、Dijkstra算法单源最短路径..第五章：1、二叉排序树2、AVL树3、地址散列法第六章：简单排序算法及快排1．数据结构是一门研究什么内容的学科？数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，..抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整