数据结构作为计算机的一门基础学科，它在面试中占有很大的比重，本科阶段，我们也学过数据结构与算法，内容比较多，也比较难，尤其是图的应用以及各类查找和排序算法，这些也都是核心内容。数据结构在实际的应用中也比较多，因此，整理一些常见的笔试、面试的数据结构常考点非常有必要，本文将对数据结构常见面试问题进行整理，以便大家查阅。

第一章 绪论

1.数据结构的逻辑结构有哪些？物理结构有哪些？

​ 数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。数据的逻辑结构分为线性结构和非线性结构，线性结构包括一般的线性表、栈、队列、串、数组，非线性结构包括集合、树、图。

​ 数据的物理结构是指数据结构在计算机中的表示（又称映像），也称存储结构。数据的物理结构主要有顺序存储、链式存储、索引存储和散列存储。

2.什么是算法?算法的五大特性是什么？一个好的算法应该具备什么样的条件？

​ 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作。算法的五个特征分别是有穷性、确定性、可行性、输入、输出。一个好的算法应该达到的目标是正确性、可读性、健壮性、效率与低存储量需求。

3.什么是数据结构？数据结构在学什么？

​ 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的是计算机操作对象的逻辑结构、物理结构以及数据的运算。

4.数据结构的复杂度是什么意思？

时间复杂度：算法中所有语句的频次。

空间复杂度：指算法运行过程中所使用的的辅助空间的大小。

5.常见的数据结构有哪些，说说他们之间的逻辑关系。

数据结构四种常见的逻辑结构：

1）集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

2）线性结构：数据结构中的元素存在一对一的相互关系；

3）树形结构：数据结构中的元素存在一对多的相互关系；

4）图形结构：数据结构中的元素存在多对多的相互关系。

第二章 线性表

1.顺序表和链表的比较

①存取（读取）方式

​ 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

②逻辑结构与物理结构

​ 采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来实现的。

③查找、插入和删除操作

查找：对于按值查找，顺序表无序时，两者的时间复杂度均为O（n）；顺序表有序时，可采用折半查找，此时的时间复杂度为O (log2n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O（1），而链表的平均时间复杂度为O（n）。

插入、删除：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相应的结点指针域即 可。由于链表的每个结点都带有指针域，故而存储密度不够大。

④空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新的元素，则会出现内存溢出，因此需要预先分配足够大 的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态分配存储虽然存储空间可以扩 充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链式存储的结点空间只在需要时申请分配，只要内存有空间就可以连续分配，操作灵活、高效。

2.解释下头指针和头结点的区别？单链表增加头结点的目的是什么？

头指针：是指向第一个结点存储位置的指针，具有标识作用，无论链表是否为空，头指针都存在。

头结点：是为了操作统一和方便设立的，放在第一个元素结点之前，头结点的数据域可以不存储任何信息，因此头结点可有可无。

单链表增加头结点可以方便运算。

3.循环链表的优点是什么？

可以从任意一个结点访问整个链表。

4.数组和链表的区别是什么？（比较经典的问题）

​ 从逻辑结构来看：数组的存储长度是固定的，即数组大小定义之后不能改变，而且在插入和删除操作需要移动大量元素，相反对于 链表，它能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

​ 从访问方式来看：数组中的元素在内存中连续存放，可以通过数组下标进行随机访问，访问效率比较高。链表是链式存储结构，它 的存储空间不是必须连续，可以是任意的，因此访问链表必须从前往后依次进行，访问效率比较低。

5.解释一下顺序存储和链式存储

​ 顺序存储是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。

​ 链式存储是用任意的存储空间来存储数据元素，不能进行随机访问，访问效率较低。

第三章 栈和队列

1.请说明栈与队列的区别

​

查看更多