数据结构名词解释.doc

数据结构名词解释
树的度是树中所有结点的最大度数。

结点的左子树深度与右子树深度之差。

一个连通图的生成树是指一个极小连通子图,它含有图中的全部顶点,N-1条边。
3深度优先搜索。直到与V0所连通的所有顶点均被访问。如果,此时图中还有顶点尚未访问,则从剩余的顶点中再任选一个顶点作为出发顶点V0,重复上述过程,直到图中全部顶点均被访问为止。

除了第一个顶点和最后一个顶点之外,其余顶点均不相同的回路称为简单回路。

在用一个顶点序列表示一条路径时,若序列中没有相同的顶点重复出现,则称其为简单路径。

根据给定的关键字值,在特定的表中,确定一个其关键字与给定值相同的数据元素,并返回该数据元素在列表中的位置。这个过程叫查找。
(ASL)
为确定数据元素在表中的位置,需和给定值进行比较的关键字个数的数学期望值,成为查找算法在查找成功的平均查找长度。

它或是一棵空树,或是有下面性质的树：若左或右子树不空,左子树所有结点值小于根结点,而右子树所有结点值大于根结点的值,其左右子树也是二叉排序树。

对于给定的关键字K,从线性表的第一个(或最后一个)元素开始,依次向后(或前)与元素的关键字比较,若某个记录的关键字与K 相等,查找成功,否则失败。

或是一棵空树,或左右子树高度差的绝对值小于等于1而且,左右子树也是平衡二叉树。

在一个已排好序的基础上,每一步将下一个待排序记录插到已排好记录的子集上,使之重新有序,直到所有待排记录插完为止。
(索引查找)
分块查找以前两个为基础,将待查记录分成若干块,每块的关键字无序,但每块的关键字的最大值有序,查找时,先查找到待查记录所在的块,再在块内进行顺序查找。找块时,即可以用折半查找,也可用顺序查找。

由某个集合上的偏序集得到该集合上的一个全序,这个操作叫做拓扑排序。

将两个或两个以上的有序表合并成一个新的有序表,开始将每个元素当成是一个个单独的有序表,逐渐表个数以原来一半的速度递减,每个表的长度却是原来长度的2倍增加,不断重复,直到最后是一个表,而表的长度是元素个数为止。

根据关键字的递减或递增的次序,把文件中的各个记录依次排列起来,可使一个无序的数据元素序列变成一个有序的序列的操作。

它是插入排序的一种,又叫缩小增量排序,先按增量进行分组,组内插入排序,然后每次缩短增量,再进行分组和组内插入排序, 直到增量为1时,进行最后一次排序止。

指的是待排序记录存放在计算机存储器中进行的排序过程；

指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中对外存进行访问的排序过程。

假设Ki=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri领先于Rj(即i＜j)。若在排序后的序列中Rj 领先于Ri ,则称所用的排序方法是不稳定的。

假设Ki=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri领