数据结构笔试面试总结_数据结构笔试总结

数据结构笔试面试总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构笔试总结”。

一、线性表：

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

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

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

三、栈和队列

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

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

四、树

非线性数据结构。

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

树的性质；

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

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

中序遍历：LDR

后序遍历：LRD

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

五：图

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

顶点的出度od（v）；

顶点的入度id（v）；

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

性质：n个顶点的无向图最多有n（n-1）/2 条边；n个顶点的有向图最多有n（n－1）条边；

六：查找:

查找：

1、顺序查找

2、二分查找

3、分块查找

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

5、哈希查找

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

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

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

1.顺序查找法

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

2.二分查找

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

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

(1)首先确定该区间的中点位置：mid=(low+high)/

2(2)然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：

①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。

②类似地，若R[mid].key

因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

3.分块查找

分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法

分块查找表的存储结构由“分块有序”的线性表和索引表组成。

(1)“分块有序”的线性表

表R[1..n]均分为b块，前b-1块中结点个数为s=n/b，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。

(2)索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

分块查找的基本思想是：

(1)首先查找索引表,索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

(2)然后在已确定的块中进行顺序查找,由于块内无序，只能用顺序查找。

4.对查找算法的总结

(1)若n较小(如n≤40)，可采用顺序查找。(2)若文件初始状态有序，且n较大，则应采用时间复杂度为O(Log2(N))的二分查找方法。(3)若文件初始状态分块有序，且n较大，则应采用分块查找。

七：排序

1、简单排序算法

（1）冒泡法

这是最原始，也是众所周知的最慢的算法。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

（2）选择法

这种方法提高了一点性能(某些情况下)，这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，再从剩下的部分中选择最小的与第二个交换，这样往复下去。

（3）插入法

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张。

2、高级排序算法

（1）快速排序

快速排序的基本思想是基于分治策略的。将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。首先我们选择一个中间值middle(程序中我们使用数组中间值)，然后把比它小的放在左边，大的放在右边(具体的实现是从两边找，找到一对后交换)。然后对两边分别使用这个过程。

（2）Shell排序(希尔排序)

首先需要一个递减的步长gap，最后的步长必须是1。工作原理是首先对相隔较远的元素的所有内容排序，然后再使用同样的方法对相隔近些的元素的排序，以此类推。

（3）归并排序

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

3、对排序算法的总结

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

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

堆和栈有什么区别：

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

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