1、逻辑结构与物理结构（存储结构）的区别？

    答：逻辑结构是指 数据元素之间的逻辑关系 ，而物理结构则是 数据的逻辑结构在计算机中的存储形式 。
    逻辑结构分类：
      （1）集合：各个元素之间是 “平等” 的，类似于数学里面的集合
      （2）线性结构：数据结构中的 数据元素是一对一关系 的
      （3）树形结构：数据结构中的 数据元素之间存在一对多 的层次关系
      （4）图形结构：数据结构中的 数据元素之间存在多对多 的关系
    物理结构分类：
      （1）顺序存储结构：把 逻辑上相邻 的元素存储在 物理位置上也相邻 的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
          优点：可以实现随机存储，每个元素占用最少的存储空间。
          缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
      （2）链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
          优点：不会出现碎片的现象，能充方利用所有存储单元。
          缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。
      （3）索引存储结构：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
          优点：检索速度快。
          缺点：附加的索引表额外占用存储空间。另外，增加和删除数据也要修改修改索引表，因而会花费较多的时间。
      （4）散列存储结构： 根据元素的关键字 直接计算出该 元素的存储地址 ，又称为哈希（Hash）存储。
          优点：检索、增加和删除结点的操作都很快。
          缺点：若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

2、算法的特点？

    算法的五大特征：
      （1）有穷性：有限的步骤
      （2）确定性：不可二义性
      （3）可行性：每一步都是通过执行有限次数完成的
      （4）输入：零个或多个输入
      （5）输出：至少有一个或多个输出
    好的算法包括：正确性、可读性、健壮性（当输入数据不合法时，算法也能做出相应的反应）、效率与低存储需求
      时间复杂度：算法的执行时间与原操作的执行次数之和成正比
      空间复杂度：如果输入数据所占空间只取决于问题本身，而与算法无关，只需要分析除了输入和程序之外的辅助变量所占用的空间即可。

3、常见的数据结构？

    数据结构：指相互之间存在一种或者多种特定关系的数据元素的集合。
    常见的数据结构：
      （1）数组：一维数组、二维数组
      （2）链表：单链表、循环链表
      （3）栈：先进后出、递归、后缀表达式、函数调用
      （4）队列：先进先出、树的层次遍历、图的广度遍历
      （5）树：二叉树、森林、平衡二叉树、线索二叉树、遍历
      （6）图：有向图、无向图、遍历、最短路径

4、链表结构和顺序存储结构的区别？

    顺序存储结构：把 逻辑上相邻 的元素存储在 物理位置上也相邻 的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
    链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    顺序存储结构：
         读取方便O(1)
         插入删除需要移动大量元素（平均需要移动半个表长的元素）
         空间分配：一次性
         存储密度=1
    链式存储结构：
         读取不方便，需要遍历O(n)
         插入删除方便，只需要改变指针
         空间分配：在需要的时候分配
         存储密度<1
    存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）

5、线性链表？

    线性链表中一个节点代表一个存储空间，即节点。每一个节点包括两个部分，一个用来存储数据，一个存储下一个元素的地址。

6、数组和链表的区别？

    数组：
        事先定义长度，不能适应数据动态地递减
        从栈中分配空间
        快速访问数据元素，插入删除不方便
    链表：
        动态地进行存储分配，可以适应数据动态地递减
        从堆中分配空间
        查找访问数据不方便，插入删除数据方便

7、判断一个链表是否有环，如何找到这个环？

    题问：给定一个单链表，只给出头指针h：
        （1）如果判断是否存在环？
            对于判断一个单链表是否存在环，可以利用追赶的方式，设立两个指针slow、fast，从头指针开始，每次分别前进一步和两步，如果存在环，则两者相遇；如果没有环，fast遇到NULL退出。
        （2）如何知道环的长度？
            在slow和fast相遇的地方标记，再次相遇所走过的操作数就是环的长度。
        （3）如何找出环的连接点在哪里？
            分别从相遇点和头指针开始走，再次相遇的那个点就是连接点。
        （4）带环链表的长度是多少？
            连接点距离头指针的长度，加上环的长度，即为链表长度。

8、单链表和双链表的区别？

    单链表：只能向后访问，不能逆向访问
    双链表：在单链表的基础上添加一个指向前驱节点的指针域，实现双向遍历

9、头指针和头结点的区别？

    头指针：
        是链表指向第一个结点的指针，若链表有头节点，则是指向头节点的指针
        是必需的
        具有标识作用
    头节点：
        头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前
        不是必需的，为了方便操作
        对于插入和删除第一个结点，和其他结点操作统一

10、简述KMP算法？

    KMP算法是在简单模式匹配的基础上对串的模式匹配进行优化。
    主要的思路是 每趟比较过程中让子串先滑动到一个合适的位置 。
    当发生不匹配时，不同于简单模式匹配的右移一位，而是 移动到合适的位置 。
    这里所移动的位置依靠与next数组，求next数组的方法是比较 前后缀相同元素 。

11、栈和队列的区别？

  栈：
    先进后出
    允许在表尾进行插入和删除
    插入和删除都在表尾进行
    top==-1为空
    top++进栈
    top–出栈
  队列：
    先进先出
    允许在一端进行插入一端进行删除
    在队尾插入在队头删除
    front==rear为空
    rear=(rear+1)%maxsize进队
    front=(front+1)%maxsize出队

12、栈和队列的相同之处和不同之处？

  相同点：
    （1）栈和队列都是线性结构
    （2）栈和队列在插入时都是在表尾进行
    （3）栈和队列都可以用顺序存储结构和链式存储结构
    （4）栈和队列插入和删除操作的时间复杂度和空间复杂度是一样的
  不同点：
    （1）删除元素位置不同，栈在表尾，队在表头
    （2）用链表存储时可以实现多栈空间共享，队列不行

13、两个栈实现队列，两个队列实现栈？

  两个栈实现一个队列：
    先将数据存在到第一个栈里，在将第一个栈里的元素全部出栈到第二个栈，第二个栈出栈，即可达到先进先出。

  两个队列实现一个栈：
    先将数据存到第一个队列里面，然后数据出队一直出队到第二个队列里面，直到第一个队列里面剩余一个数据，这个时候出队，即可达到先进后出的特性。

14、树和二叉树的相关概念？

  （1）二叉树和度为2的树的区别？
    二叉树的特点：
      <1>每个节点最多有两颗子树，节点的度最大为2
      <2>左子树和右子树是有顺序的，次序不能颠倒
      <3>即使某结点只有一个子树，也要区分左右子树
      <4>二叉树可以是空树、只有一个根节点、根节点只有左子树、根节点只有右子数、根节点左右子树都有
    度为2的树：树的结点的最大的度为2
  （2）二叉树的遍历：先序、中序、后序、层次遍历。
  （3）树的遍历：先根遍历（先访问根节点，从左到右先根遍历的每个子树）、后根遍历（先依次后根遍历每个根子树，然后再访问根节点）

15、二叉平衡树？

  在二叉排序树的基础上，只要保证每个节点左子树和右子数的高度差小于等于1就可以了。适合用于插入删除比较少，但是查找比较多的情况。

16、二叉搜索树？

  是比根节点大的放在右子数，比根节点小的放在左子树，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

17、红黑树？

  主要性质：
    （1）节点是红色或者黑色，没有其他的颜色
    （2）根节点是黑色，不能为红色
    （3）每个叶节点是黑色，这里的叶子节点，节点是指空的叶子节点
    （4）不存在两个连续的红色节点，即父节点和子节点不能是连续的红色
    （5）从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点
  优点：平均查找，添加输出效果都还不错
  红黑树的应用比较广泛，主要是用来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。例如Java集合中的TreeSet和TreeMap，C++ STL中set、map，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct（虚拟内存）时就是采用了红黑树来维护内存块的。

18、图的相关概念？

  图结构中节点之间的关系是任意的，图中的任意两个节点都可能有关系。
  图分为有向图和无向图
  有向图的基本算法：拓扑排序、最短路（Dijkstra算法和Floyd算法）
  无向图的基本算法：最小生成树（Prime算法，Kruska算法）、DFS、BFS

19、邻接矩阵与邻接表的区别？

  图的存储结构：
    邻接表：（链式存储结构）由单链表的表头形成的顶点表，和单链表其余节点形成的边表两部分组成；一般顶点表存放顶点信息和指向第一个边节点的指针。适合用于稀疏图。
    邻接矩阵：（顺序存储结构）用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。适合用于稠密图。
    有向图的十字链表法
    无向图的多重链表法

20、深度优先遍历与广度优先遍历？

  深度优先遍历 类似于 二叉树的先序遍历
    步骤：
      <1>访问起始点v
      <2>若v的第一个邻接点没有被访问过，则深度遍历该邻接点
      <3>若v的第一个邻接点已经被访问，则访问其第二个连接点，进行深度遍历；重复以上步骤，直到所有节点都被访问为止
  广度优先遍历 类似于 层次遍历
    步骤：
      <1>访问起始点v
      <2>依次遍历v 的所有未访问过得邻接点
      <3>再次访问下一层中未被访问过的邻接点；重复以上步骤，直到所有节点都被访问过为止

21、最小生成树的算法（普利姆算法，克鲁斯卡尔算法）？

  普利姆算法（Prime）
    算法执行过程：
      （1）将v0到其他顶点的所有边当作侯选边
      （2）重复以下过程，直到所有的顶点被并入树中：
        （2.1）从侯选边中挑选出最小的边输出，并将与该边的另一端顶点并入树中
        （2.2）考查所有剩余的顶点，选取与这棵树相邻的边的最短边
    时间复杂度为O(n^2)，适合用于稠密图

  克鲁斯卡尔算法（Kruska）
    思路：每次找出候选边中权值最小的边，并入生成树中
    算法执行过程：
      （1）将图中边按照权值从小到大排序
      （2）然后从最小边开始扫描
      （3）并检测当前边是否为候选边，即是否该边并入会构成回路
    适用于稀疏图

22、什么时候最小生成树唯一？

  所有权值都不相同，或者有相同的边，但是在构造最小生成树的过程中权值相等的边都被并入到最小生成树中的图，其最小生成树是唯一的。

23、Dijkstra算法与Floyd算法的区别？

  Dijkstra算法（迪杰斯特拉）
    用于计算图中某一结点到其余顶点的最短路径
    思路：
      （1）集合S存放图中一找到最短路径的顶点
      （2）集合U存放途中剩余顶点
    算法执行过程：
      （1）初始时，S只包含原点，即：S={v}，v的距离为0。U包含除v以外的其他顶点。即：U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
      （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v大k的最短路径长度）。
      （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
      （4）重复步骤（2）和（3）直到所有顶点都包含在S中。

  Floyd算法（弗洛伊德）
    解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
    时间复杂度O(n³)，空间复杂度O(n²)
    算法描述：
      （1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权值为无穷大。
      （2）对于每一对顶点u和v，看看是否存在一个顶点w，使得从u到w再到v比已知的路径更短。如果是更新它。

24、拓扑排序的概念以及实现？

  AOV网：一种以顶点表示活动，以边表示活动的先后次序且没有回路的有向图。反映出整个工程中各个活动之间的先后关系的有向图。
  拓扑算法的核心过程：
    （1）从有向图中选择一个没有前驱（入度为0）的顶点输出
    （2）删除1中的顶点，并且删除从该顶点发出的全部边
    （3）一直重复
  若图中没有环的时候，还可采用深度优先搜索遍历的方法进行拓扑排序。

25、关键路径的相关概念？

  AOE网：在带权有向图中，若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间
  AOV和AOE的区别：
    相同点：都是无环图
    不同点：
      AOV活动在顶点，边无权值，代表活动之前的先后关系
      AOE活动在边，边有权值，代表活动持续的时间
  关键路径的核心算法：
    最大路径长度的路径称为关键路径
    关键活动：关键路径上的活动为关键活动，关键活动的最早开始时间等于最晚开始时间。由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从起始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。

26、各种排序的概括与总结？

  （1）排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、基数排序、堆排序
  （2）稳定的排序：冒泡排序、插入排序、归并排序、基数排序
  （3）经过一趟排序，能够保证一个关键字到达最终位置：冒泡排序、快速排序、简单选择排序、堆排序
  （4）关键字比较次数和原始序列无关：简单选择排序、折半排序
  （5）排序趟数和原始序列无关：冒泡排序、快速排序
  （6）将顺序存储更换为链式存储，时间效率低：希尔排序、堆排序
  （7）排序最优和最差相同的排序算法：简单选择、归并排序、堆排序
  （8）排序算法中哪些最坏和平均的时间复杂度是一样的：直接插入、折半插入、冒泡排序、简单选择排序、堆排序、归并排序

27、各种查找方法？

  查找方法分为静态查找表和动态查找表
    静态查找表：顺序查找、折半查找、分块查找
      顺序查找：结构简单，顺序结构和链式结构都可以，查找效率低
      折半查找：要求查找表为顺序存储结构，并且有序
      分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，从而保存块间是有序的，把各子表中最大关键词构成一张索引表，表中还包含各子表的起始地址。
        特点：块间有序，块内无序，查找时，块间索引查找，块内进行顺序查找。
    动态查找表：二叉排序树、平衡二叉树
      二叉排序树：是比根节点大的放在右子数，比根节点小的放在左子树，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。
      平衡二叉树：他的左右子树高度差不能大于1，且左右子树也都是平衡二叉树

28、快速排序的优化？

  优化：
    （1）当整个序列有序时退出算法
    （2）当序列长度很小时（根据经验是大概小于8），应该使用常数更小的算法，比如插入排序等。
    （3）随机选取分割位置
    （4）当分割位置不理想时，考虑是否重新选取分割位置
    （5）分割成两个序列时，只对其中一个递归进去，另一个序列仍可以在这一函数内继续划分，可以显著减小栈的大小（尾递归）
    （6）将单向扫描改成双向扫描，可以减少划分过程中的交换次数
  优化1：当待排序序列的长度分割到一定大小后，使用插入排序
    原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。
  优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与Key相等元素分割。
  优化3：优化递归操作（快排函数再函数尾部有两次递归操作，我们可以对其使用递归优化）
    优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

29、B树和B+树的区别，以一个m阶数为例？

  关键词的数量不同：
    B+树中具有n个关键字的结点只包含有n棵子树。每个结点关键字个数的范围是⌈m/2⌉<=n<=m
    B树中具有n个关键字的结点含有n+1棵子树。每个结点关键字个数的范围是⌈m/2⌉-1<=n<=m-1
  存储的位置不同：
    B+树中数据都存储再叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储再每一个结点中。
  分支结点的结构不同：
    B+树的分支结点仅仅存储着关键字信息和儿子的指针，也就是说内部结点仅仅包含着索引信息。
  查询不同：
    B树再找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束
  B树：

  B+树：

30、哈希表（概念、构造方法、冲突解决）？

  概念：根据给定的关键字来计算出关键字的表内地址
  构造方法：
    直接定址法：
      H(Key)=a*Key+b
      特点：计算简单，且不会产生冲突，若关键字发布不连续，空位较多，则会造成存储空间的浪费。
    数字分析法：
      当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出发布均匀的任意几位作为散列的地址，适用于所有关键字都已知的情况。
    平方取中法：取关键字平方后的中间几位作为Hash地址（适用于关键字的每位取值都不够均匀或小于散列地址所需的位数）
    除留余数法：取关键字对p取余的值作为散列地址，其中p<m，即H(Key)=Key%p(p<m)。
  冲突解决方法：
    开放定址法：
      （1）线性探查法：依次探查下一个地址，直到有空位置出现为止（任意产生堆积）
      （2）平方探查法：可以减少堆积问题，但是不能探查到hash上的所有单元，可探查到一半单元。
    链地址法：把所有的同义词用单链表连接起来
    公共溢出区法：
      为所有冲突的关键字记录一个公共溢出区来存放。再查找时，堆给定关键字通过散列函数计算出散列地址后，先于基本表的相应位置进行对比，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。如果相对于基本表而言，再有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

31、用循环比递归的效率高吗？

  递归和循环两者完全可以互换。不能完全决定性地说循环的效率比递归的效率高
  递归算法：
    优点：代码简洁、清晰，并且容易验证正确性。
    缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。
  但是，对于某些问题，如果不使用递归，将是极端难看的代码。再编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
  循环算法：
    优点：速度快，结构简单。
    缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

32、贪心算法和动态规划以及分治法的区别？

  贪心算法：顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。
  动态规划：把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划从下到上，一步一步找到全局最优解。
  分治法：将原问题划分成n个规模较小而结构与原问题相似的子问题。递归地解决这些子问题，然后再合并其结果，就得到原问题的解。（各子问题独立）

33、算法与数据结构中的大O是什么意思？

  答：大O表示的是最坏的情况下的时间复杂度。