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

11.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间物的符号表示，在计算机科学中是指所有以输入到计算机中并被计算机程序处理的符号的总称。3.数据元素是数据的基本单位，在计算机程序中通常作为一个整体进4.数据对象是性质相同的数据元素的集合，是数据的一个子集。5.数据结构是相互之间存在一种或多种特定关系的数据元素的集6.根据数据结构之间关系的不同特性，通常有下列4类基本结构:集合、线性结构、树形结构、图状结构或网状结构。7.抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作，有“数据抽象”与“数据封装”两个重要特性。8.算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每TnOfnn率与f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。n表示形式。括两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指域。3.循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。4.双向链表是指有两个指针域，其一指向直接后继，另一指向直接前趋。栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义尾，允许删除的一端称做队头。列称该串的子串，通常称字符在序列中的序号为该字符在序列中的序号为该字符的在串中的位置。并且各个对应位置的字符都相等时才相等。的称为根。2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树。2.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲。同一个双亲的孩子之间互2子树中的任一结点都称为该结点的子孙。3.结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，m6.二叉树(是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。称之为完全二叉树。8.遍历二叉树：指按某条搜索路径巡访树上每个结点，使得每个结点均被访问一次，而且仅被访问一次。有先序遍历、中序遍历、后序遍历三种。9.若结点有左子树，则其lchild(rchild)域指向指示其左(右)孩子，否则令lchild(rchild)其前驱(后继)，这种结点构成的二叉链表做为二叉树的存储结构称为线索链表。10.从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一个结点的路径长度之与。树的带权路径长度为树中所有叶子结点的带权路径长度之与。点带树为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树。w为弧头,此时称图为有向图，若<v,w>表示v与w之间的一条边，此时的图称为无2.有n*(n-1)/2条边的无向图称为完全图。具有n(n-1)条弧的有向图称为有向完全图，有很少条边或弧的图称为稀疏图，反之称为稠密图。有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权，这种带权的图称为网。4.无向图G=(V,{E})中从点v到顶点v’的路径是一个顶点序列，路径的长度是路径上边或弧的数目。第一个顶点与最后一个顶点相同的路径称为回路或环。序列中不重复出现的路径称为简单路径。除了第一个顶点与最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。5.在无向图G中，如果从顶点v到顶点v’有路径，则称v与v’是连通的。如果对于图中任意两个顶点vi、vj∈与都是连通的，则称是连通图。所谓连通分量指的是无向图中的极大连通子图。G图。有向图中的极大强连通子图称做有向图的强连通分量。7.一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一的生成树有且仅有n-1条边。如果一个图有n个顶点与小于n-1条边，则是非连通图，如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。向树。若干棵不相交的有向树的弧。39.图的存储结构有邻接矩阵、邻接表、逆邻接表以及十字链表等。索：类似于树的先序遍历，假设从图中某顶点v出发，在访问了v之通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做为起始点，重复上述过程，直至图中所有顶点都被访问到为止。2)广度优先搜索：类似于村的层序遍历，假设从图中某顶点v出发，在访问了v之于后访问的顶点的邻接点，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。vv个关节点。一个没有关节点的图称为重连通图。若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。14.拓扑排序：指由某个集合上的一个偏序得到该集合上的一个全15.网：指用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动16.网：指用边表示活动的网，是一个带权的有向无环图，其中，顶点表示事件弧表示活动，权表示活动持续的时间，通常一个AOE-网可用来估算工程的完成时间。17.在正常的情况(无环)下，网中只有一个入度为零的点，称做源点与一个出度为零的点，称为汇点。18.在AOE-网点，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是关键1.查找表()：是由同一类型的数据元素构成的集合。若对查找表只作查找操作，则称此类查找表为静态查找表，若在查找过程中同时插入查找表中不存在的数据元素，则称此类表为动态查找表2.关键字()：是数据元素或记录中某个数据项的值，用它可能标识一个数据元素，若此关键字可以惟一地标识一个记录，则称此关键字为主关键字，反之，称用以识别若干记录的关键为次关键字。3.查找：根据给定的某个值，在查找表中确定一个其关键字等给定值的记录或数据元素，或指示该记录在查找表中的位置，若表中不存在关键字等于给定值的记录，则称查找不查找不成功。5.平均查找长度：为确定记录在查找表中的位置，需与4给定值进行比较的关键字的个数的期望值称为查找算法在查找成功时的平均查找长度。6.折半查找的查找过程：先确定待查记录在有序表中所在范围，然后逐步缩小范围直到找到或找不到该记录为止。7.判定树：树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个查找过程的二叉树称为判定树。折半查找法在成功时进行比较的关键字个数最多8.次优查找树：构造一棵二叉树，使这棵二叉树的PH9.二叉排序树：或者是一棵空树，或者是具有下列性质的二叉a)若它的左子树不空，则左子村上所有结点的值均小于它的根结点的值。b)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。c)它的左、右子树也分别为二叉排序树。10.平衡二叉树：又称AVL树，它或者是一棵空树，或者是11.平衡因子：为该结点的左子树深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只能是-1，0，1，只要二叉树上一个结点的平衡因12.哈希表：根据设定的哈希函数与处理冲突的方法将一组关键字映射到一个有限的连续的地址集上，并以关键字在越来越集中的像作为记录在表中的存储位地址或散列地址。13.冲突：对不同的关键字可能得到同一哈希地址，这种现象称为冲突，具有相同函数值的关键字对该哈希函数来说称做同义词。14.常用的构造哈希函数的方法有：a键字或关键字的某个线性函数值为哈希地址。先知道的，则可取关键字的若干位组成哈希地址。c平方取中法：取关键字平方的后的中间几位做为哈希地址。15.常用的处理冲突的方法：a。c同义词的记录存储在同一线性链表中。d)建立一个公共溢出区。16.二次聚集：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。17.装填因子：是表中填入的记录数与哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模n的函数。1.排序：是指将一个数据元素的任意序列重新排列成一个按关键字有序的序5j称所用的排序方法是稳定的，反之称所用的排序方法是不稳定的。a)内部排序：指的是待排序记录放在计算机随机存储器中进行的排序过程b)外部排序：指的是待排序记录的数量很大，以致内在一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。4.直接插入排序：它的基本操作是将一个记录插入到5.希尔排序’：又称缩小增量排序，基本思想是先将整个记录序列分进行一次直接插入排序。6.起泡排序：首先将第一个记录的关键字同第二个记录的关键字进行较为止。判别起泡排序结束的条件应该是在一趟排序