数据结构思维导图

1. 快速排序算法中，每次划分后：将对划分所得的两个字表长度不等的两个字表分别排序，为提高效率，应先对那个字表进行排序

先对表长较短的进行排序，可以减少空间复杂度，但是时间复杂度没有影响

2. 拓扑排序可以全部输出后结束说明：没有有向回路

3. m叉树的优缺点：1优点在：存储结构统一，方便处理。缺点：空链域造成存储效率低下

4. m阶B树最大高度h<=logm/2（n+1）/2 +1

5. m阶B树有p个非叶子结点，则最多分裂p-2次

6. 度为m的树，空指针域数目为mn-（n-1）

7. 什么是好的散列函数

8. 线性探测法的不足之处

9. 哈夫曼编码与ASCII码的区别

10. 哈夫曼编码的优点：对频率高的字符赋以短编码，而对频率较低的字符赋以长编码，从而使字符的平均编码长度减短，起到压缩数据的效果

11. 除拓扑排序，其他判断图中是否存在环的方法

12. （2014）逻辑结构，存储结构，运算之间的关系：数据的逻辑结构反映数据元素之间的逻辑关系，即数据元素之间的关联方式；数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示极其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的。和存储结构无关，而运算的实现则是依赖于存储结构的。

13. 为什么会出现“假溢出”，以及如何解决：

在顺序队中，通常让队尾rear指向刚进队的元素位置，让队首指针front指向刚刚出队的元素位置。因此，元素进队时，rear要后移；元素出队时，front也要后移。经过一系列的出队和进队操作后，两个指针最后会达数组末端maxsize-1处，虽然队中已经没有元素，但是人无法让元素进队，这就是所谓的“假溢出”

将存储队列头尾相连，形成循环队列，队头队尾指针加一时用取模运算

队尾指针进时rear+1%maxsize 队头进时：。。。

14. 什么是算法，算法的主要特征：

算法是为解决一个特定问题而采取的特定有限步骤

有穷行，确定性，可行性，输入（零或多个输入），输出（一或多个输出）

15. 归纳法证明E是扩充二叉树的外路径，I是内路径长度，n是内结点数，证明E=I+2n

​ 当N=1时成立

​ 设n=k时成立

​ 则n=k+1时，增加一个内部结点时，In=in+1，其实该节点是从外部节点变来的，此时也相当于增加了一个外部结点（原外部结点变成内部节点，而增加了两个外部结点）则En+1=En+1+2

16. 程序步：是在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征值无关，（就是计算执行一个程序段共须得走多少行代码），不是程序步越小越好

17. 什么是数据结构，一个算法的好坏从哪方面衡量

正确性，可读性，健壮性，高效率与低存储量

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构，数据的运算

18. 度量程序方法有两种：事前分析和事后计算

19. 好的散列函数：支持快速计算，散列地址均匀，散列函数值尽可能覆盖到整个散列表的存储地址

20. 均匀的散列函数：对于关键字集合中的任意一个关键字，散列地址以相等的概率取0～m-1中的每一个只，即每一个关健字的同义词数量相同

简述下列术语的含义：数据、数据元素、逻辑结构、存储结构、线性数据结构和非线性数据结构。

数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号总称、数据元素：是数据的基本单位，在计算机中通常作为一个整体考虑和处理

数据项：组成数据元素的最小单元

数据对象：性质相同的数据元素的集合，是数据的一个子集

逻辑结构：从逻辑上描述数据，与数据的存储无关，独立于计算机的

存储结构：数据对象在计算机中的存储表示称为数据的存储结构，即存储了数据元素的数据又存储了数据元素之间的逻辑关系

线性数据结构：数据元素的有序序列，第一个元素无前驱只有后继，最后一个元素只有前驱无后继，其余结点都只有唯一的前驱和唯一的后继结点；数据元素之间一对一包括：线性表，栈、队列、串、数组

非线性数据结构：数据元素之间的关系不是一对一，有一对多的树形结构，多对多的图型结构，以及无对应关系的集合

什么是数据结构？有关数据结构的讨论应包括哪些方面？

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包括：逻辑结构，存储结构，数据的运算

从概念上讲，有哪些基本的逻辑结构关系？

按元素间的关系可分为线性结构和非线性结构，其中线性结构又分为：一般的线性表，栈、队列、串和数据；非线性结构分为：树、图和集合

有哪两种常见的存储表示方式？

存储结构分为：顺序存储、链式存储、索引存储、散列存储；

性能存储方式	顺序存储	链式存储
访问方式	随机/顺序	顺序
空间	静态分配	动态分配
存储地址	连续	可以不连续
存储密度	1	<1
适用操作	访问元素多的操作	插入/删除多的操作
表长限制	要先知表长	表长未知也可创建
插入删除操作	不利	有利

什么是抽象、数据抽象和过程抽象？

抽象：抽取共同的和本质的内容，忽略非本质的细节

数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分开考虑

过程抽象：程序设计者将一个运算的定义与实现运算的具体方法分开考虑

什么是封装和信息隐蔽？

封装：是指把数据和操纵数据的运算组合在一起的机制

信息隐蔽：封装对使用者隐藏了数据结构以及程序的实现细节，这种设计数据结构或程序称为信息隐蔽

什么是抽象数据类型和类属抽象数据类型？

数据类型分为：原子类型，结构类型，抽象数据类型

抽象数据类型：指用户定义的、表示应用问题的数学规模，以及定义在这个规模上的一组操作的总称；

包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作集合

为什么说C语言的类型int是抽象数据类型？

我们只能用过类型int所规定的运算操纵整形变量或常量，不需要关注int底层如何实现

一个数据结构的ADT描述是ADT的接口，它包括哪几部分？

数据对象、数据对象上关系的集合、数据对象的基本操作的集合

什么是算法？说明算法和程序的区别。

算法:是对特定问题求解步骤的一种描述，是指令的有限序列

程序：是算法的代码实现

算法必须可终止和程序没有这一限制

简述衡量一个算法的主要性能标准。

算法的五大基本特征：又穷性，确定性，可行性，输入（0或多个），输出（1或多个）

“好”算法：正确性、可读性，健壮性，低存储高效率需求

什么是算法的时间复杂度和空间复杂度？

（事前分析）

时间复杂度：一个语句在算法中被重复执行的次数最高的频度

空间复杂度：该算法所耗费的存储空间

什么是程序步？引入程序步概念对算法的时间分析有何意义？

程序步：在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关

通过对算法程序步执行的次数来确定算法的问题规模来求出渐进时间复杂度

什么是算法的事前分析和事后测试？

事前分析：在算法还没开始执行，排除程序运行环境的因素后再来讨论算法的时间效率

事后测试：测试一个程序在所选择的输入数据下运行时实际需要的时间

什么是渐近时间复杂度？

算法时间增长率和某个函数增长率相同，使用大O表示的算法的时间复杂度称为算法的渐进时间复杂度

什么样的图其最小生成树是唯一的

在构造最小生成树的过程中，要从剩余边中选择权值最小的并入当前生成树中，如果有多条边权值相同且都为最小值时，则可以选择其中任意一条边并入，这样就会产生多种最小生成树，要使最小生成树唯一，则所有边的权值都不相同时才能满足

为什么关键路径既是最长又是最短

关键路径是完成整个项目所需要的时间最长的活动时间的排序，而最短是指完成整个最短需要这么长时间

除拓扑排序，其他判断图中是否存在环的方法：

采用深度优先遍历有向图思想，在一个顶点v的所有边都被检查过后，要返回顶点v，进而退回上一个顶点，重新开始检查上一个顶点的其他边。如果图中不存在回路，则在v处遍历v的其他领接顶点的过程结束前，不会出现一条指向v的边，通过检查是否有这样一条边来判断

哈夫曼编码的优缺点

不等长编码，能产生较短的码文，平均码长最短，不具有二义性；缺点：在译码时由于是不等长，译码效率较低

什么是递归，递归算法，比较递归与非递归之间的关系：

所谓递归是指，若一个函数、过程或者数据结构定义的内部又直接或间接的出现定义本身的应用，则称他们是递归的，或者递归定义的。递归是一个数学概念，也是一种有用的程序设计方法；常见有三种情况：定义是递归的，数据结构是递归的，问题的解法是递归的

递归的优缺点：程序简洁而清晰，且易于分析，缺点是浪费时间和空间

1、数据结构的基本概念

2、线性表

3、栈和队列

4、串

5、树与二叉树

6、图

7、查找

8、排序