数据结构基础知识整理

《数据结构基础知识整理》由会员分享，可在线阅读，更多相关《数据结构基础知识整理（12页珍藏版）》请在金锄头文库上搜索。

1、 数据结构基础知识整理* 名词 解释 1、数据：是信息的 载体，能够被计算机识别、存储和加工处理。* 2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。* 3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。* 4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。* 5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言

2、的。* 6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。* 7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。* 8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。* 9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n) 的数量 级（阶）称 为算法的渐近时间复杂度。* 10、最坏和平均 时间复 杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入

3、实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。* 11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。* 12、线性表：由n(n0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外） ，这是一种线性结构。* 13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。* 14、单链表：每个结点有两个域：一个值

4、域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。* 15、双 链表：每个 结点中增加了一个 prior，用来指向 该点的直接前趋结点。它是一种双向、对称的结构。* 16、循环链表：是一种首尾相接的链表。单循环链表形成一个next 链环，而双循环链表形成next链环和priorJ链环。* 17、存储 密度：是指结 点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1 ，而链表的存储密度小于1。* 18、 栈：只允 许在一端进 行插入、删除运算的线性表，称 为“栈” （stack） 。* 19、 LIFO表：

5、即后进先出表，修改操作按后 进先出的原 则进行。譬如栈就是一种LIFO表。 * 20、 顺序栈 ：采用顺序存 储结构的栈，称为顺序栈。* 21、 链栈：采用 链式存储结 构的栈，称为链栈。 * 22、 队列：只允 许在一端 进行插入、另一端进行删除运算的 线性表，称为“队列” （queue） 。* 23、 FIFO表：即先进先出表。譬如 队列就是一种FIFO表。 * 24、 顺序队 列：采用顺序存 储结构的队列，称为顺序 队列。* 25、循 环队 列：为克服顺 序队列中假上溢现象，将向量空 间想象为一个首尾相接的圆环，这种向量称为循环向量，存储在其中的队列称为循环队列。* 26、 链队列：采用

6、 链式存 储结构的队列，称为链队列。 * 27、字符串：由零个或多个字符组成的有限序列，一般高 为S=“a1，a2， an”。* 28、空白串：由一个或多个空格组成的串称为空白串。 * 29、空串：长度为零的串称 为空串，它不包括任何字符。 * 30、 顺序串：串的 顺序存 储结构简称的为顺序串。* 31、 链式串：串的 链式存 储结构简称为链式串。 * 32、模式匹配：子串的定位运算又称为串的模式匹配。* 33、 对称矩 阵：元素满足 aij=aji（0i,jn）的矩阵。 * 34、三角矩阵：主对角线 以上或以下的元素（不包括 对角线）均为常数的矩阵。* 35、 带状矩 阵：所有非零元素均集

7、中在以主 对角线为 中心的带状区域的矩阵。 * 36、稀疏矩阵：非零元素 远远少于矩阵元素的矩阵。* 37、广 义表：有 n个元素a1,a2an 组成的有限序列，其中n可以是原子或一个广义表。* 38、三元 组 表：若线性表 顺序存储的每一个结点均是三元 组，那么该线性表的存储结构称为三元组表。J * 39、行表：记录稀疏矩阵 中每行非零元素在三元组表中的起始位置的表称 为行表。* 40、内部排序：假设给 定含有n个记录（R1,R2,Rn）的文件，其相应的关键字为（K1，K2 ，,Kn）, 则排序是确定一个排列（P(1),P(2),P(n) ） ，使得（Kp(1)Kp(2)Kp(n)） ，从而

8、得到有序文件（R* p(1), R p(2),R p(n)） 。整个排序过程都在内存中进行的排序即为内部排序。* 41、稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然保持不变，则这处排序方法是稳定的。* 42、就地排序：若排序算法所需的辅助空间并不依赖 于问题的规模n，即辅助空间为O(1),则称为就地排序。* 43、堆：n 个关键字序列K1，K2，,Kn ，称为堆，当且仅当序列满足如下性质：KiK2i，且KiK2i1 或KiK2i，且KiK2i1。* 44、 查找：即 给定一个值 K，在含有n个结点的表中找出关

9、键字等于给定值K的结点。* 45、 动态查 找表：若在查 找的同时对表做修改操作（如插入和 删除） ，则相应的表称之为动态查找表。* 46、静 态查 找表：若在查 找的同时不对表做修改操作（如插入和 删除） ，则相应的表称之为静态查找表。* 47、内 查找：若整个 查找 过程都在内存中进行，则称之 为内查找。 * 48、外 查找：若 查找过程中需要 访问外存，则称之为 内查找。* 49、平均查找长度：ASLpici ，其中n 是结点的个数；pi是查找第i个结点的概率；ci 是找到第i个结点所需要进行的比较次数。* 50、散列函数：在关键字和表地址之 间建立的对应关系 h称为散列函数。* 51、

10、冲突：两个不同的关键字，其散列函数值相同，因而被映射到同一个表位置上的 现象称为冲突。 * 52、同 义词 ：发生冲突的两个关 键字称为该散列函数的同 义词。* 53、装填因子：设m 和n分别表示表长和表中填入的结点数，则将=n/m定义为散列表的装填因子。 * 二、填空* 1、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序存储方法、链接、索引、散列。 2、数据的运算最常用的有五种，检索、插入、删除、更新、排序。* 3、一个算法的效率可分为时间和空间效率。 4、数据结构按逻辑结构可分为线性结构和非线性结构。线性结构反映结点间的逻辑关系是一对一的，非线性是多对多的。* 5、顺序表相对于链

11、表的优点有节省存储和随机存储。 6、链表相对于顺序表的优点有插入和删除操作方便。* 7、按 顺序存储方法存储的线性表称为顺序表，按链式存储方法存储的线性表称为链表。 8、线性表中结点的集合是有限的，结点间的关系是一对一的。J * 9、在n个结点的顺序表中插入(删除)一个结点需平均移动n/2 （(n-1)/2）个结点，具体的移动次数取决于表长n和插入（删除）位置 i。* 10、在 顺序表中 访问任意一 结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。* 11、在民个结点的单链表中要 删除已知结点*p，需找到它的直接前趋结点的地址，其时间复杂度为O(n)。* 12、在双 链 有

12、中要删除已知 结点*p，其时间复杂度为O(1)。* 13、在 单链 表中要在已知 结点*p之前插入一新结点，仍需找到*p的直接前趋结点的地址，其时间复杂度为O(n)；而在双链表中，完成同样操作其时间复杂庶O(1)。* 14、在循环链表中，可根据在一结点的地址遍历整个链表，而单链表中需知道头指针才能遍历链表。 15、在栈中存取数据遵从后进先出的原则，队列中则是先进先出。* 16、栈结构中，允许插入、删除的一端称为栈顶，另一瑞称为栈底；在队列中，允许插入的称为队尾，允许删除的一端称为队首。* 17、在有 n个元素的栈中，进栈和退栈操作的复杂度为O(1) 和O(1) 。* 18、 设长度 为n 的链

13、队列用单循环链表示，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和 O(1)；若只设尾指针，则O(1) 和O(1)。* 19、通常在程序中使用串可分为串变量和串常量；而串按存储方式又可分为顺序串和链式串。 20、链式存储与顺序存储的相互串匹配算法的效率相同。* 21、成功匹配的起始位置称为有效位移，所有匹配不成功称为无效位移；NaivestrMatch 返回的是第1个有效位移。* 22、串的朴素匹配算法最坏的情况下需要比较字符的 总次数为(n-m+1)m,n为主串长，m 为子串长。* 23、对于数组Anm，其元素aij按行优先与列优先存储的地址之差为(i-1)(n-1) -(j-1

14、)(m-1).(两次存储的LOC(a11)相同 .)* 24、特殊矩阵是指非零或零元素分布有一定 规律的矩 阵。 25、多维数组的存储方式有顺序和链式。 26、递归表是指允许递归的广义表，纯表是指与树对应的广义表。* 27、任何一个非空广义表的表 头是表中第一个元素，它可以是原子，也可是广 义表而表尾必定是广义表。* 28、表的长度是指广义表元素的个数，表的深度是指广义表展开后扩号的层数。 29、树中结点的最大层次称为树的深度（高度） 。* 30、若有一棵二叉排序树，则按照中序遍历顺序将产生一个有序序列。 31、由一棵二叉树的前序序列和中序可惟一确定这棵二叉树。* 32、将一棵树转换成一棵二叉

15、树后，二叉树的根结点没有右子树。 33、图有邻接矩阵、邻接表等存储结构，遍历图有深度优先（DFT）和广度优先（BFT）等方法。J * 34、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。 35、如果n个顶点的图是一个环，则它有n个生成 树。* 36、n个顶点e条边的图用邻接矩阵（邻接表）存储，则空间复杂度为O(n2)（O(n+e)） 。 37、稀疏（稠密）图G，采用邻接表（ 邻接矩阵）存储较省空间。* 38、图的逆邻接表存储结构只适用于有向图。 39、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是将邻接矩阵的第i行全置0 、* 40、n个顶点e条边的图用邻接

16、矩阵（邻接表）存储，深度优先遍历的时间复杂度为O(n2)（O(n+e)） 。 （广度优先时间复杂度同上。 ）* 41、 图的BFS 生成树的树高比DFS生成树的树高小或相等。* 42、用 Prim（Kruskal）算法求具有n个顶点e 条边的图的最小生成树的时间复杂度为O(n2)（O(elog2e)） 。* 43、稀疏（稠密）图G 的最小生成树，最好用Kruskal（Prim）算法求解。* 44、用迪杰斯特拉（Dijkstra）算法求n个顶点e 条边的图中的某一顶点到其余各顶点间最短路径的时间复杂度为O(n2) 。* 45、用 Dijkstra算法求某一顶点到其余各顶点间最短路径是按路径长度递增的次序来得到最短路径的。* 46、拓扑排序算法是通过重复选择具有0 个前趋顶点的过程来完成的。 47、拓扑排序输出的顶点数小于有向的顶点数，刚该图一定存在环。* 48、 对n 个 顶点e条边