数据结构笔试面试总结

一、线性表：

线性表的定义和抽象数据类型：线性表可以是有序、无序表；抽象类型包括数据和操作两个部分，数据部分可以用顺序，链接，散列，索引任何一种方法存储到计算机中；线性表的顺序存储结构和链接存储结构（单链表，双向链表，带表头的附加结点的线性链表，循环链表）；操作：初始化单链表，删除单链表中的所有结点，使之成为一个空表，得到单链表的长度，检查单链表是否为空，得到单链表多种第及个结点中的元素，遍历一个单链表，从单链表中查找出等于给定值的第一个元素，更新单链表中等于给定值的第一个元素，向单链表中按照给定条件插入一个元素，从单链表中删除符合给定条件的第一个元素，对单链表进行数据排序.

二、稀疏矩阵、集合、广义表

稀疏矩阵：非零元素的个数远远小于零元素个数，对于每个非零元素的表示是通过三元组（主序：行号，辅序：列号，元素值），采用顺序或链式方式存储。

广义表：线性表的推广，表或表中表。采用动态链接结构。递归的数据结构。

三、栈和队列

栈：只允许在表的一端进行插入和删除运算，对栈进行运算的成为栈顶，另一端为栈底。向栈插入元素叫进栈，删除元素叫出栈。栈是先进后出。栈顶指示栈为空，进栈，栈顶指针+1，出栈，栈顶递归数据结构。

队列：在一端进行插入，在另一端进行删除，插入的一端叫做队尾（rear），进行删除的一端叫做队首（front），先进先出。

非线性数据结构。

结点的度和树的度；分支结点和叶子结点；孩子结点和双亲结点；结点的层数和树的深度；有序树和无序树；森林；

树的性质；

二叉树：度为2的有序树。存储结构：顺序存储，数组；链接存储结构：指针；

二叉树的遍历：前序遍历：DLR

中序遍历：LDR

后序遍历：LRD

树的遍历：先根遍历，后根遍历，按层遍历

顶点的度依附于顶点的边的数目记为td(v)；

顶点的出度od（v）；

顶点的入度id（v）；

td(v)＝od（v）＋id（v）；

1n个顶点的无向图最多有n/2条边；

2n个顶点的有向图最多有n条边；

六：查找:

1、顺序查找

2、二分查找

3、分块查找

4、数表的动态查找（二叉排序树查找、平衡二叉树AVL树、B树、B+树）

5、哈查找

查找有静态查找和动态查找两种，静态查找只在数据结构里查找是否存在某个记录而不改变数据结构。实现静态查找的数据结构称为静态查找表；动态查找要在查找过程中插入数据结构中不存在的记录，或者从数据结构中删除已存在的记录。实现动态查找的数据结构称为动态查找表。衡量查找算法的标准是平均查找长度，它是指在查找过程中进行的关键码比较次数的平均值。实现动态查找的数据结构称为动态查找表。

静态查找表的查找方法主要有顺序查找、折半查找和索引查找等。顺序查找不要求查找表中的记录有序，效率不是很高，适合于记录不是很多的情况。折半查找要求查找表中的记录有序，查找效率很高，适合于记录比较多的情况。索引查找要求查找表分段有序，适合于记录非常多的情况。动态查找表主要介绍了二叉排序树。二叉排序树是一棵二叉树，其左子树结点关键码的值小于根结点关键码的值，右子树结点关键码的值大于根结点关键码的值。二叉排序树上的操作主要有查找、插入和删除等操作。

在哈表中查找记录不需要进行关键码的比较，而是通过哈函数确定记录的存放位置。哈函数的构造方法很多，主要有直接定址法、除留余数法、数字分析法和平方取中法等。由于同义词会产生哈冲突，解决哈冲突的方法主要有开放地址法和链表法等，其中开放地址法主要有线性探测法和二次探测法等。查找又称检索，是在程序设计中对数据结构中的记录进行处理时经常采用的一种操作。同排序一样，查找是对关键码进行处理，关键码分为主关键码和次关键码，以主关键码进行的查找是最经常、也是最主要的查找。

1.顺序查找法

即从第一个元素顺序到最后一个元素依次与待查的值进行比较，如果相等，查找成功，否则继续比较，直到所有元素都比较过了，如果还没有匹配的值，查找失败。查找适用于数据量少、不要求已经排序的数据，它的时间复杂度为O(N)；

2.二分查找

又称折半查找，适用于数据量大、已经排序的数据，它的时间复杂度为O(Log2(N))。

二分查找的基本思想是(设R[XXX是当前的查找区间)：

首先需要一个递减的步长gap，最后的步长必须是1。工作原理是首先对相隔较远的元素

的所有内容排序，然后再使用同样的方法对相隔近些的元素的排序，以此类推。

（3）归并排序

把数据等分成两部分,各自用归并排序排好后再合并，它在归并时耗费O(n)的空间。

3、对排序算法的总结

(1)若n较小(如n≤40)，可采用插入排序或选择排序。当记录规模较小时，插入排序较好；反之，因为选择移动的记录数少于插人，应选选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(N猳g2(N))的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；快速排序不适合用于“几乎已排好序”或“几乎正好倒序”的数据。在此最坏情况下，时间复杂度为O(N2)。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。归并排序是稳定的,而且适用于数据量特别大以至于无法在内存中容纳,需要通过外存来进行的外部排序。

堆和栈有什么区别：

1、栈区（stack）—由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

2、堆区（heap）—一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表