数据结构面试经典问题摘要参考资源基础深度补充
借鉴资源基础数据结构常见面试问题深入挖掘数据结构面试问题(三)在数据结构面试中，一定要听数据结构算法常见面试问题的补充
1 .请详细说明数组和链表的区别。
从逻辑结构看：
a )数组必须定义预先决定的长度(要素的个数)，不能应对数据动态增减的情况。 数据增加可能会超过定义的元素数量。数据减少会浪费内存。数组可以根据下标直接访问。
B )链表动态进行存储分配，能够适应数据动态增减的情况，便于数据项的插入、删除。 (在数组中插入和删除数据项时，必须移动其他数据项，这非常复杂。)链表必须基于next指针找到以下元素
从内存存储器的角度来看：
a ) ) )静态)数组从堆栈中分配区域，因此对程序员来说方便且高速，但自由度小
b )链表从堆中分配空间，自由度大，但申请管理麻烦
通过上述比较可以看出，如果需要快速访问数据，而且很少插入或删除元素，则需要使用数组。相反，如果需要频繁插入或删除元素，则需要使用链表的数据结构。
2 .排序算法是什么？ C语言共有多少种排序方法
排序算法有很多，每个算法的时间和空间复杂度不同，效率也有差异，使用上也可能不同。 原则上，数据结构是一个领域，与语言没有绝对的联系，往往同一算法可以用多种语言实现。 插入排序、气泡排序、选择排序、快速排序、堆栈排序、合并排序、基数排序、希尔排序等常用算法如下所示。
3 .如何理解开心服装表，开心服装表是什么
摘自百度：散列表(Hash table，也称为开心服饰表) )是基于键码值(Key value )直接访问的数据结构。 这意味着通过将键码值映射到表中的某个位置来访问记录，从而缩短搜索时间。 该映射函数称为哈希函数，存储记录的数组称为哈希表。 在规定表m中存在函数f[key]，如果对任意的规定的关键词值key代入函数而得到记录在包含该关键词的表中的地址，则将表m称为高兴的服饰[hash]表，将函数f[key]
4 .请写下以下算法的时间复杂度
气泡排序法插入排序法堆积排序法二叉树排序法
o(n )2) o )2) o ) O(O(nlog2n )最坏o ) N2 )平均o ) nlog2n )
快速排序法希尔排序法
最坏o(n2 )平均o ) O(nlog2n ) o ) nlogn )不稳定
5 .数据结构、二叉树相关知识、销量、为什么要使用二叉树等。
在计算机科学中，二叉树是每个节点最多有两个子树的有序树。 通常，树根子树被称为“左子树”(left subtree )和“右子树”(right subtree )。 二叉树常用作二叉树的搜索树和二叉树的山或二叉树的排序树。 二叉树的每个节点最多只有两个部分树，二叉树的部分树有左右之分，顺序不能颠倒。
文件系统和数据库系统一般采用树，特别是b树的数据结构数据，主要是排序和检索效率。 二叉树是最基本、最典型的顺序树，用于教授和研究树的特性，本身实际上很少应用。 因为缺点很明显。 像泡沫分类一样，在效率问题上不实用，但不会失去一个教育例子的好手段。
6 .如何判断链表上是否有环？
两个针分别按一定的步骤走，P1走一布，P2走两布。 如果链表中有圈，P1和P2有时会相遇。 (追击问题的解法)
7、简述快速排序流程
1 )选择基本元素。 通常选择第一个元素或最后一个元素。
2 )将待排序的记录按一次排序分为独立的两部分，其中部分记录的要素值小于基准要素值。 其他部分记录的要素值大于基准值。
3 )此时，基准元素位于确定顺序后的正确位置
4 )然后，将这两部分的记录分别用同一方法继续排序，直到整个序列有序为止。
8、各种排序算法比较
在时间的复杂性上：
(1)平方阶数(o ) N2 ) )排序
各种简单排序：直接插入、直接选择、冒泡排序；
)2)线性对数阶(o ) O(nlog2n ) )排序
快速排序、堆栈排序、合并排序
说明：
当原表规则或基本规则时，直接插入排序和冒泡排序可以大大减少比较次数和移动记录次数，降低时间复杂度到o(n )；
快速排序相反，原表基本有序时为脱泡排序，时间复杂度为o(n2 )；
原表是否有序对简单选择排序、堆积排序、合并排序、基数排序的时间复杂度影响不大。
稳定性：
排序算法的稳定性：如果要排序的序列中存在多个具有相同关键字的记录并进行排序，且这些记录的相对顺序不变，则称算法为稳定。 如果排序后记录的相对顺序发生了变化，则会说算法不稳定。
稳定排序算法：气泡排序、插入排序、合并排序、基数排序
不是稳定的排序算法。 选择排序、快速排序、希尔排序和堆栈排序
9、排序算法选择标准：
将要排序的元素的数量设为n。
1 )当n较大时，应该采用时间复杂度为o(nlog2n )的排序方法。 快速排序、堆栈排序、合并排序顺序。
2 ) n较大时，允许内存空间，要求稳定性)合并排序
3 )当n较小时，可以采用直接插入或直接选择排序。
直接插入排序：如果元素有规律分布，则直接
插入排序将大大减少比较次数和移动记录的次数。直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
10、用循环比递归效率高吗？
递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。
递归算法：
优点：代码简洁、清晰，并且容易验证正确性。
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
循环算法：
优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
解决高兴的服饰冲突的方法
高兴的服饰表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。
1） 线性探测法
2） 平方探测法
3） 伪随机序列法
4） 拉链法
11、KMP算法：
在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。