《数据结构与算法》——名词解释总结
考研题型⾥有⼀个题型叫做名词解释，这道题或多或少的咋试卷中占着⼀定的分量，但是分数⼜不是太多，⽤⼤量的⼤块时间来搞这个有点不太值当，所以抽些时间做个总结⽂档，⽤于空闲时间查看。
本⽂中概念不全，仅总结了个⼈易混淆及常考的概念。
名词解释
数据：是对客观事物的符号表⽰。
数据元素：是数据的基本单位，也称节点（node）或记录（record）。
数据对象：是性质相同的数据元素的集合，是数据的⼀个⼦集。
数据项：有独⽴含义的数据最⼩单位，也称域(field)。
数据结构：是相互之间存在⼀种或多种特定关系的数据元素的集合。
逻辑结构：抽象反映数据元素之间的逻辑关系。
物理结构：数据结构在计算机中的表⽰。（存储结构）
算法：对特定问题求解步骤的⼀种描述。
算法设计原则：正确性，可读性，健壮性，效率与低存储量需求。
空串：零个字符的串；
树的度：树中所有结点的度的最⼤值；
分⽀结点: 度⼤于零的结点
树的深度：树中叶⼦结点所在的最⼤层次
森林：m棵互不相交的树的集合。
满⼆叉树：指的是深度为k且含有2k-1个结点的⼆叉树。
完全⼆叉树：树中所含的 n 个结点和满⼆叉树中编号为 1 ⾄ n 的结点⼀⼀对应。
路径长度：路径上分⽀的数⽬。树的路径长度：树根到每个结点的路径长度之和。
树的带权路径长度：树中所有叶⼦结点的带权路径长度之和，记作：WPL(T) = Swklk
带权路径长度最⼩的⼆叉树，称为最优树⼆叉树或赫夫曼树。
关键路径：路径长度最长的路径。
顶点：数据元素vi称为顶点
边、弧：P (vi,vj)表⽰顶点vi和顶点vj之间的直接连线，在⽆向图中称为边，在有向图中称为弧。任意两个顶点构成的偶对(vi,vj)∈E是⽆序的，该连线称为边。是有序的，该连线称为弧。
弧头、弧尾：带箭头的⼀端称为弧头，不带箭头的⼀端称为弧尾。
顶点的度(TD)=出度(OD)+⼊度(ID)
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
通常有两条遍历图的路径：深度优先搜索和⼴度优先搜索。
排序的分类：
按待排序记录所在位置
内部排序：待排序记录存放在内存
外部排序：排序过程中需对外存进⾏访问的排序
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），就说该图是有向图（directed graph，digraph）。若E中的每条边是两个不同顶点⽆序对，就说该图是⽆向图，其边仍表⽰成（v, w）。
开放树：连通⽽⽆环路的⽆向图称作开放树。
最⼩⽣成树：设G=( V, E )是⼀个连通图，E中每⼀条边(u, v)的权为C(u, v)，也叫做边长。图G的⼀株⽣成树(spanning  tree)是连接V中所有结点的⼀株开放树。将⽣成树中所有边长之总和称为⽣成树的价(cost)。使这个价最⼩的⽣成树称为图G的最⼩⽣成树。
⽆向图双连通分量：设Vi 是 Ei 中各边所连接的点集（1≤i≤k）,  每个图Gi = ( Vi  ,  E i)叫做 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的树，以及⼴义表中的元素都是原⼦时。
内部排序  若整个排序过程都在内存中完成，则称此类排序问题为内部排序。
⽂件 ⽂件是由⼤量性质相同的记录组成的集合，按记录类型不同可分为操作系统⽂件和数据库⽂件。
⽂件存储结构的基本形式有哪些？⼀个⽂件采⽤何种存储结构应考虑哪些因素？ ⽂件的基本组织⽅式有顺序组织、索引组织、散列组织和链组织。⽂件的存储结构可以采⽤将基本组织结合的⽅法，常⽤的结构有顺序结构、索引结构、散列结构。
索引⽂件 在主⽂件外，再建⽴索引表指⽰关键字及其物理记录的地址间⼀⼀对应关系。这种由索引表和主⽂件⼀起构成的⽂件称为索引⽂件。索引表依关键字有序。
参考书籍及⽹址
1. 严蔚敏，吴伟民. 数据结构（C语⾔版）[M]. 北京： 清华⼤学出版社，2013.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。