1.队列和栈的区别

答：一、规则不同

（1）队列：先进先出

（2）栈：先进后出

二、对插入和删除操作的限定不同

（1）队列：只能在表的一端进行插入，并在表的另一端进行删除；

（2）栈：只能在表的一端插入和删除。

三、遍历数据速度不同

（1）队列：基于地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快；

（2）栈：只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性。

2.折半查找和顺序查找的优缺点

答：顺序查找：从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

优点：算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。

缺点：与其他查找方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。

折半查找：又称为二分查找法，查找过程令处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时为止。

优点：比较次数少，查找速度快，平均性能好；

缺点：要求待查表为有序表，且插入删除困难。

3.二叉树的顺序存储和链式存储

答：顺序存储：是指用一组地址连续的存储单元依次从上而下、从左到右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i 的结点元素存储在某个数组下标为 i-1 的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系。

链式存储：是指用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个链结点来存储。

4.哈夫曼树的原理

答：又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,…,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,…,wn}，则所构造出的带权路径长度最小的二叉树就被称为哈夫曼树。

5.链表的头指针、头节点和首元素的概念

答：头节点：在链表的第一个节点之前会额外增设一个节点，该节点的数据域一般不存放数据。

首元素：链表中第一个元素所在的节点，它是头节点后边的第一个节点。

头指针：链表的头指针永远指向链表中第一个节点的位置，换句话说，如果链表有头节点，头指针指向头节点；否则，头指针指向首元节点。

头节点和头指针的区别是：

（1）头指针是一个指针，头指针指向链表的头节点或者首元节点；

（2）头节点是一个实际存在的节点，它包含有数据域和指针域。

头节点和头指针的区别在程序中的直接体现是：头指针只声明而没有分配存储空间，头节点需要声明并分配一个节点的实际物理内存。

6.树和图的概念

答：树是一种递归数据结构，包含一个或多个数据节点的集合，其中一个节点被指定为树的根节点，而其余节点被称为根的子节点。

图是由一个非空的顶点集合和一个描述顶点之间多对多关系的集合组成的一种数据结构。

7.链表的概念

答：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成。

8.数据存储结构有哪几种

答：链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

顺序存储：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素。

索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址，索引表由若干索引项组成。

散列存储：是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

9.树与二叉树之间的相互转换

答：树转换成二叉树：（1）加线：在兄弟之间加一连线。（2）抹线：对每个结点，除了其左孩子外，抹掉其与其余孩子之间的连线。（3）旋转：将树作适当的旋转即可。

二叉树转成树：（1）逆旋转：把二叉树从左上到右下分为若干层。（2）加线：找到每一层结点在其上一层的父结点。（3）抹线：删除每一层结点之间的连接。

10.什么是共享栈

答：利用栈底位置不变的特性，让两个顺序栈共享同一个一维数组空间，将两个栈的栈底分别设在共享空间的两端，两个栈顶向共享空间延伸。

11.解释下平衡二叉树

答：平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点的时候，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡树。在保持二叉排序树特性的前提下，调整最小不平衡树中各结点之间的连接关系，进行相应的旋转，使之称为新的平衡子树。

12.栈的进出次序

答：先进后出；栈是一种数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。

13.算法的时间复杂度

答：在程序中反复执行的语句的执行次数被称为语句的频度，就是所有语句频度之和的数量级，而所有语句的频度之和与程序最内层循环的频度是同一数量级，所以算法的时间复杂度是最内层循环的频度的数量级。

14.贪心算法、动态规划和分治算法

答：贪心算法：指从上到下，每次都求解局部最优解的算法，特点是每次求解最优解，但是最终的结果不一定是最优。

动态规划：是将一个大问题划分成若干个子问题，问题之间存在重叠，从上到下，求解整体最优解，每一次的求解会对下一次的问题造成影响，最终的最优解不一定包含每次的最优解，但是一定有部分最优解。

分治算法是将一个大问题划分成若干个和大问题相似的子问题，再对子问题进行递归求解，最终合并得到最后的结果。

15.顺序表和链表的比较

答：（1）存取（读取）⽅式：顺序表能够随机读取和顺序读取，⽽链表只能按顺序读取。

（2）插⼊和删除：顺序表插⼊和删除需要移动⼤量的元素，链表的插⼊和删除只需要修改指针的位置。

（3）空间分配：顺序表的空间分配分为静态分配和动态分配，静态内存分配时，很容易导致内存溢出或者是浪费，⽽动态内存分配时，有时候不存在⼀⼤块连续的存储空间，导致分配失败，并且需要移动⼤量的元素，效率低。⽽链表是直接在需要的时候申请内存，只要有内存就能够分配，操作灵活、⾼效。

16.简述逻辑结构与存储结构的联系和区别。

答：联系：数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

区别：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。

17.简述顺序表和链表存储方式的特点。

答：顺序表的优点是可以随机存取元素，存储密度高；缺点是不便于插入和删除元素。

链表的优点是便于节点的插入和删除；缺点是不能进行随机访问，只能顺序访问，存储密度较低。

18. 解释带头结点的单链表和不带头结点的单链表的区别。

答：区别主要体现在其结构上和算法操作上。

在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点；不带头结点的单链表不含头结点。

在操作上，带头结点的单链表的初始化为申请一个头结点，无论插入或删除的位置是第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。

19.数据逻辑结构包括哪⼏种类型？

答：逻辑结构包括线性结构和⾮线性结构。更细分的话可以说，逻辑结构包括集合、线性结构、树形结构和网状结构。

20.数据结构与数据类型有什么区别？

答：数据结构包括三个方面，分别是数据的逻辑结构、数据的存储结构和数据的运算；而数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构，后者是前者的一种简化情况。

21.简述顺序存储队列假溢出的避免⽅法及队满和空的条件。

答：避免⽅法：⼀是将队列元素向前“平移”;⼆是将队列看成⾸尾相连，即看成为循环队列。

在循环队列下，定义front＝rear时为队空，⽽判断队满则常⽤两种⽅法:⼀种是⽤“牺牲⼀个单元”，即rear+1=front时为队满:另⼀种⽅法是“设标记”，如设标记tag,tag=0时为队空:tag=1时，若因插⼈导致front=rear则为队满。

22.什么是递归程序？

答：⼀个函数在结束本函数前，直接或间接调⽤函数⾃⾝，称为递归。

递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执⾏中占内存空间较多，运⾏效率低。

递归程序执⾏中需要借助栈这种数据结构来实现。

递归程序的⼊⼝语句和出⼝语句⼀般⽤条件判断语句来实现。递归程序有基本项和归纳项组成。

23.什么是⼴义表？⼴义表与线性表的区别

答：⼴义表中的元素可以是元素也可以是⼦表。线性表中的元素可以是各种各样的，但必须具有相同的性质，属于同⼀数据对象。

24.树二叉树的区别和联系

答：树与⼆叉树是两种不同的数据结构，在逻辑上都是树形结构，区别主要有：

（1）⼆叉树的度⾄多为2，树⽆此限制；

（2）⼆叉树有左右⼦树之分，即使在只有⼀个分枝的情况下，也必须指出是左⼦树还有右⼦树，树⽆此限制；

（3）⼆叉树允许为空，树⼀般不允许为空。

25.连通、连通分量、强连通分量的概念，极⼤连通⼦图？极⼩连通⼦图？

答：在⽆向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。图中任意两点是连通的，则称图G为连通图。⽆向图中的极⼤连通⼦图称为连通分量。

有向图中，若v到w和w到v都有路径存在，则称这两个点是强连通的。任⼀对顶点都是强连通的，则此图为强连通图。有向图中的极⼤强连通⼦图称为有向图的强连通分量。

极⼤是要求该连通⼦图包含其所有的边；极⼩是在保持连通的情况下使边数最少的⼦图。

26.散列表存储的基本思想是什么？

答：散列表的基本思想是⽤关键字的值决定数据元素的存储地址。

27．散列表存储中解决碰撞的基本⽅法有哪些？

答：开放定址法、再散列法、链地址法和建⽴公共溢出区。

28.如何衡量hash函数的优劣？

答：能否将关键字均匀映射到哈希空间上，有⽆好的解决冲突的⽅法，计算哈希函数是否简单⾼效。由于哈希函数是压缩映像，冲突难以避免。

29.在查找算法中，设置监视哨的作⽤是什么？

答：监视哨的作⽤是免去查找过程中每次都要检测整个表是否查找完毕，提⾼了查找效率。

30.排序稳定性的概念

答：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。

31.稳定排序有哪些?不稳定排序有哪些？

答：稳定排序：直接插⼊排序、折半插入排序、冒泡排序、简单选择排序、归并排序、基数排序

不稳定排序：希尔排序、快速排序、堆排序

32.简述堆的结构

答：堆是⼀种特殊的完全⼆叉树，所有⽗结点都⽐⼦结点要⼩的完全⼆叉树我们称为最⼩堆。反之，如果所有⽗结点都⽐⼦结点要⼤，这样的完全⼆叉树称为最⼤堆。