华中科技大学研究生考试软件工程答案数据结构“名词解释”部分《数据结构与算法分析》

数据结构的关系和操作等的科学。数据(data)被计算机程序处理的符号的总称。数据元素(dataelement)行考虑和处理。数据对象(dataobject)是性质相同的数据元素的集合，是数据的一个子集。数据结构(datastructure)合。根据数据结构之间关系的不同特性，通常有下列4结构、图状结构或网状结构。抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作，有“数据抽象”和“数据封装”两个重要特性。算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每五个特性。算法设计的要求：正确性、可读性、健壮性、效率与低存储需求。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)T(n)=O(f(n))nf(n)渐近时间复杂度，简称时间复杂度。线性表：是n个数据元素的有限序列，有顺序存储和链式存储两种表示形式。线性表的链式存储结构针域。循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。双向链表是指有两个指针域，其一指向直接后继，另一指向直接前趋。栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义先出表。1. 队列在队列中，允许插入的一端称做队尾，允许删除的一端称做队头。串(string)中的位置。并且各个对应位置的字符都相等时才相等。树(tree)是指n(n>=0)有且仅有一个特定的称为根。2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树。度。度为0叶子或终端结点树的度孩子双亲称兄弟结点的祖先1子树中的任一结点都称为该结点的子孙。结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树在第l+1的深度或高度。无序树。森林(forest)m(m>0)棵互不相交的树的集合。二叉树Tree)并且二叉树的子树有左右之分，其次序不能任意颠倒。k2K-1个结点的二叉树称为满二叉树。深度为kn个结点的二k1n时，称之为完全二叉树。遍历二叉树：指按某条搜索路径巡访树上每个结点，使得每个结点均被访问一次，而且仅被访问一次。有先序遍历、中序遍历、后序遍历三种。若结点有左子树，则其(右)孩子，否则令（后继从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径目称做路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n{w,w,}，试构造一棵有n个叶子结点的二叉树，每个叶子结1 2 n点带树为w,则其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树。i顶点vwv弧尾，称w为弧头有向图vw边向图。有n*(n-1)/2完全图。具有n(n-1)有向完全图，稀疏图稠密图权网。v是和v相关联的边的数目，记为TD(V)。v路径的长度是路径上边回路或环。序列中不重复出简单路径简单回路或简单环。G中，如果从顶点v有路径，则称v是连通的。如果对于图中任意两个顶点v、v∈V,v和v都是连通的，则称G是连通图。所谓连通分量指的是i j i j无向图中的极大连通子图。G中，如果对于每一对v、v∈V,v≠vvvvv

都存在路径，i j i j i j j i则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。连通图的生成树棵树的n-1n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。如果一个有向图恰有一个顶点的入度为01有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。2图的存储结构有邻接矩阵、邻接表、逆邻接表以及十字链表等。图的遍历通常有两条遍历图的路径：深度优先搜索：类似于树的先序遍历，假设从图中某顶点v出发，在访问了v之后依次从vv有路径相的顶点做为起始点，重复上述过程，直至图中所有顶点都被访问到为止。广度优先搜索：类似于村的层序遍历，假设从图中某顶点v出发，在访问了v之有顶点都被访问到为止。假若在删去顶点v以及和v以上的边通分量，则称顶点v关节点连通图。若在连通图上至少删去k连通度。这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。拓扑排序(Topological序。AOV-网的网。AOE-网：指用边表示活动的网，是一个带权的有向无环图，其中，顶点表示事件弧表示活动，权表示活动持续的时间，通常一个AOE-网可用来估算工程的完成时间。在正常的情况（无环）下，网中只有一个入度为零的点，称做源点汇点。在AOE-关键路径活动。查找表（SearchTable：是由同一类型的数据元素构成的集合。若对查找表只作静态查找表(StaticSearch中同时插入查找表中不存在的数据元素，则称此类表为动态查找表(DynamicSearchTable)。关键字（Key主关键字(PrimaryKey)，次关键字(SecondaryKey)。查找成功，此时查找的结果可给出一个“空”记录或“空”指针。顺序查找(SequentialSearch)的查找过程为：从表中最后一个记录开始，逐个进行记录平均查找长度(AverageSearchLength)：为确定记录在查找表中的位置，需和3给定值进行比较的关键字的个数的期望值称为查找算法在查找成功时的平均查找长度。折半查找(BinarySearch)后逐步缩小范围直到找到或找不到该记录为止。判定树：树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个查找过程的二叉树称为判定树不超过树的深度。次优查找树(NearlyOptimalSearch带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小。二叉排序树(BinarySortTree)树:若它的左子树不空，则左子村上所有结点的值均小于它的根结点的值。若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。它的左、右子树也分别为二叉排序树。平衡二叉树(BalancedBinary。平衡因子BF(BalanceFactor)：为该结点的左子树深度减去它的右子树的深度，1，则该二叉树是不平衡的。哈希表(HashTable)：根据设定的哈希函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址集上，并以关键字在越来越集中的像作为记录在表中的存储位地址或散列地址。冲突(Collision)：对不同的关键字可能得到同一哈希地址，这种现象称为冲突，具有相同函数值的关键字对该哈希函数来说称做同义词。常用的构造哈希函数的方法有：直接定址法：取关键字或关键字的某个线性函数值为哈希地址。r先知道的，则可取关键字的若干位组成哈希地址。平方取中法：取关键字平方的后的中间几位做为哈希地址。m的数p除后的余数为哈希地址。随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址。常用的处理冲突的方法：生。链地址法：将所有关键字为同义词的记录存储在同一线性链表中。建立一个公共溢出区。二次聚集继哈希地址的现象。装填因子：是表中填入的记录数与哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模n的函数。排序(Sorting)：是指将一个数据元素的任意序列重新排列成一个按关键字有序的序4列。R=R,且在排序前的序列中RR，若在排序后的序列中R仍领先于R，则i j i j i j称所用的排序方法是稳定的，反之称所用的排序方法是不稳定的。两大类：内部排序：指的是待排序记录放在计算机随机存储器中进行的排序过程外部排序排序过程中尚需对外存进行访问的排序过程。直接插入排序(StraightInsertionSort)：它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。希尔排序(Shell’sSort)：又称缩小增量排序，基本思想是先将整个记录序列分进行一次直接插入排序。起泡排序(BubbleSort)：首先将第一个记录的关键字同第二个记录的关键字进行n-1个记录和第n个记录的关键字进行比较快速排序(QuickSort)：它的基本思想是，通过一趟排序将待排记录分割成独立的快