《华中科技大学名词解释》由会员分享，可在线阅读，更多相关《华中科技大学名词解释（6页珍藏版）》请在金锄头文库上搜索。
1、图图:是一种数据结构 ,是顶点和边的集合 .G=(V,E). 顶点:图中的数据元素叫顶点 . 完全图 :有 n(n-1)/2 条边的无向图 ,称之为完全图 .即任意两个顶点之间 ,都有边 . 有向完全图 :有 n(n-1)条弧的有向图 ,称之为有向完全图 .即任意两个顶点间,都有弧. 稀疏图 :有很少条边或弧 (少于 nlogn)的图称为稀疏图 . 稠密图 :有很多条边或弧 (多于 nlogn)的图称为稠密图 . 子图:有两个图 G(V,E),G (V ,E),如果 V包含于 V,E包含于 E,则称G 是 G 的子图 .即边和顶点都是子集 . 路径:是一个顶点序列 . 回路或环 :第一个顶点或
2、最后一个顶点相同的路径. 简单路径 :顶点不重复出现的路径 . 连通图 :图中任意两个顶点都是连通(即有路径 )的. 连通分量 :无向图中的极大连通子图. 强连通图 :有向图中任意两个顶点都是连通的. 强连通分量 :有向图中的极大连通子图. 生成树 :是一个连通图的极小连通子图,它包含全部 n 个顶点,但只有足以构成一棵树的 n-1 条边. 无向图顶点 v 的度:和 v 相关联的边的数目 . 有向图顶点 v 的入度:以 v 为弧头的弧的数目 . 有向图顶点 v 的出度:以 v 为弧尾的弧的数目 . 邻接表 :是图的一种链式存储结构. 最小生成树 :是无向图的一颗生成树,且边权值之和最小 . 关
3、节点 :删除一个顶点v 及相关的边后 ,将图的一个连通分量分割成两个或以上的连通分量 ,则 v 是该图的一个关节点 . 重连通图 :一个没有关节点的图 . 拓扑排序 :由某个集合的上的一个偏序得到该集合上的一个全序. 关键路径 :路径长度最长的路径 . 源点:AOV 网中入度为 0 的点. 汇点: AOV 网中出度为 0 的点. 有向带权图源点 :路径上的第一个顶点 . 有向带权图终点 :路径上的最后一个顶点 . 树树:有 n 个结点的有限集 . 树结点的度 :结点拥有的子树的数目. 叶子/终端节点 :度为 0 的结点 . 非终端结点 /分支结点 :度不为 0 的结点. 树的度 :树内各结点度
4、的最大值. 树结点层次 :从跟开始定义 ,根为第一层 ,根的孩子为第二层 . 树的深度 /高度:树中结点的最大层次 . 有序树 :树中结点的各子树看成从左至右是有次序的,即不能交换 . 无序树 :树中结点的各子树看成从左至右是无次序的,即可以交换 . 森林:是 m 课互不相交的树的集合 . 二叉树 :一种树型结构 ,且每个结点至多只有两棵子树,二叉树的子树有左右之分 ,次序不能交换 . 满二叉树 :一颗深度为 k 且有 2k-1 个结点的二叉树 . 完全二叉树 : 对于深度为 K 的,有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1 至 n 的结点一一对应 . 有
5、向树 :是一个有向图 ,且满足 :有且仅有一个结点的入度为0;除根结点为所有结点入度为1;从根到任意结点有一条路劲. 有向完全树 :即是一颗有向树 ,又是一颗完全二叉树 . 先序遍历 :访问根节点 ,先序遍历左子树 ,先序遍历右子树 . 中序遍历 :中序遍历左子树 ,访问根节点 ,中序遍历右子树 . 后序遍历 :后续遍历左子树 ,后续遍历右子树 ,访问根节点 . 线索:指向结点前驱和后继指针. 线索二叉树 :加上线索的二叉树 . 线索化 :以某种次序遍历二叉树,使其变为线索二叉树的过程叫做线索化. 哈夫曼树 (最优二叉树 ):带权路径长度最小的二叉树. 前缀编码 :任意一个字符的编码都不是另一
6、个字符的编码的前缀. 查找查找表 :同一类型的数据元素构成的集合. 静态查找表 :只有如下两种操作的查找表:查询某个特定的数据元素是否在查找表中 ;检索某个特定数据元素的各种属性. 动态查找表 :有如下四种操作的查找表:查询某个特定的数据元素是否在查找表中 ;检索某个特定数据元素的各种属性;在查找表中插入一个数据元素 ;从查找表中删除一个数据元素. 关键字 :数据元素中某个数据项的值,用于唯一标识一个数据元素. 平均查找长度 :为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值 . 静态最优查找树 :带全内路径长度之和最小的二叉树.近似最小时为次优查找树 . 二叉排序树 :或者
7、是一棵空树 ,或者具有如下性质 :若左子树非空 ,则左子树上的所有结点值均小于它的根节点值.若右子树非空 ,则右子树上的所有结点值均大于它的根节点值.左右子树也是二叉排序树. 平衡二叉树 :或者是一棵空树 ,或者具有如下性质:左右子树深度差绝对值不大于 1.左右子树均是平衡二叉树. 平衡因子 :结点左子树深度减去右子树深度. 冲突:针对不通关键字得到同一哈希地址. 装填因子 :哈希表中填入的记录数 /哈希表长度排序排序:将一个记录的任意序列 ,重新排列成按一个关键字有序的序列. 堆:堆是一颗完全二叉树,根结点最大的堆叫最大堆,根结点最小的堆叫最小堆 .堆的左右子树也是堆 . 串串:由零个或多个
8、字符组成的有限序列. 子串:串中任意连续个字符组成的子序列. 存储密度 :串值所占的存储位 /实际分配的存储位模式匹配 :子串的定位操作 . 线性表线性表 :含有 n 个元素的有限序列 . 数据元素 :就是记录 . 数据项 :一个数据元素可以有若干数据项文件:含有大量记录的线性表称为文件. 线性链表 :用一组任意的存储单元存储线性表的数据元素. 静态链表 :用数组描述的链表 . 循环链表 :一种链式存储结构 ,表中最后一个结点的指针域指向头结点,整个链表形成一个环 . 双向链表 :结点有两个指针域 ,一个指向它的后继 ,一个指向它的前驱 . 栈和队列栈:限定插入和删除仅在表尾进行的线性表. 队
9、列:是一种先进先出的线性表. 递归函数 :一个直接调用自己或通过一系列语句间接调用自己的函数. 双端队列 :限定插入和删除仅在表的两端进行的线性表. 链队列 :用链表表示的队列 . 循环队列 :将存储空间想象为一个首尾相接的圆环,存储在其中的队列称之为循环队列 . 绪论数据元素 :数据的基本单位 . 数据对象 :性质相同的数据元素的集合. 数据结构 :相互之间存在一种或多种特定关系的数据元素的集合. 数据类型 :一个值的集合和定义在该集合上的一组操作. 结构类型 :一种数据结构和定义在该结构上的一组操作. 抽象数据类型 :一个数学模型以及定义在该模型上的一组操作. 算法: 特定问题的求解步骤 ,它是指令的有限序列 ,每个指令表示一个或多个操作 . 算法特性 :有穷性,确定性,可行性,输入,输出. 算法设计要求 :正确性 ,可读性,健壮性,效率与低存储需求 . 时间复杂度 :随问题规模的 n 的增大 ,算法执行时间的增长率 . 空间复杂度 :随问题规模的 n 的增大 ,算法所需存储空间的增长率.
