数据结构面试题

数据结构23道面试题目
 面试题  1917  4 分钟  

呜呜呜，又是看八股文的一天。

数据结构

  1. O(n)的大O是什么意思？什么是时间复杂度?
    答：大O是最坏情况下的时间复杂度。时间复杂度是评价算法运行速度的快慢，是最基本语句的执行次数。

  2. 线性存储结构和链式存储结构的优点?
    线性存储支持随机存取数据，速度快。
    链式存储插入和删除数据不需要移动大量元素，底层存储时可以不连续。

  3. 解释一下顺序存储与链式存储
    顺序存储：所有元素存放在一块连续的存储区域中，这块区域通常可以用一个数组来表示。
    链式存储：链式存储不要求相邻元素的实际物理位置相邻，只需要存储相邻元素的位置即可。

  4. 头结点和头指针的区别？
    头结点：链表中的第一个结点
    头指针：头节点的地址

  5. 栈和队列的区别
    区别：栈是一个后进先出的结构，队列是一个先进先出的结构。

  6. 有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？
    (F的位置-P的位置+n)%n. （PS:P的位置可能大于F的位置，所以需要加N）

  7. 如何区分循环队列是队空还是队满？
    最简单的方法就是在循环队列中加入一个元素个数的标记方法。
    也可以牺牲一个位置，不用来存储，这样头指针+1==尾指针，队列满；头指针==尾指针，为队列空。

  8. 大顶堆实现及应用
    大顶堆实际上是一棵完全二叉树，任何节点都比其左右孩子大。堆的应用有堆排序，解决TopK的问题。

  9. 哈希表的概念？哈希冲突的解决办法？ 哈系表，又称为散列表。是一个根据键来找到对应值的数据结构。通过哈希函数将键映射到内存位置。
    冲突通常有两种解决办法：
    (1) 拉链法，在映射到的位置来一个链表来进行存储
    (2) 开放地址法，从映射位置往后找一个空位置来进行存储

  10. 判断链表是否有环（非常重要！）
    标记法、快慢双指针法。
    对于快慢双指针法找到入环点可以，一个指针指向起点，一个指针指向重合点，相遇点就是入环点。

  11. 平衡二叉树、二叉排序树、完全二叉树的定义
    平衡二叉树(AVL)：它的左右两个子树高度差的绝对值不超过1，并且左右两个子树都是二叉平衡树。
    二叉排序树(BST)：又称二叉查找树，根结点的值大于全部左子树的值，根结点的值小于全部右子树的值。左右子树仍是二叉查找树。
    完全二叉树：叶结点只在最后一层或者次后层，最后一层的叶结点只能在最左边。

  12. 如何由遍历序列构造一颗二叉树？已知先序序列和后序序列能否重现二叉树？ 先序(根)遍历：遍历顺序，根-左-右.
    中序(根)遍历：遍历顺序，左-根-右.
    后序(根)遍历：遍历顺序，左-右-根.
    不能，无法确定根结点了

  13. B树是什么?在数据库中有什么应用？
    B树是一个优化的二叉搜索树，一个结点可以有多个值，减小了树的高度。数据库通常使用B树进行索引。

  14. 红黑树是什么？
    由于平衡二叉树每次插入和删除都需要作出复杂的操作，所以红黑树的特点在查找效率和插入删除数据花费时间作出了权衡。

  15. 二分搜索和单纯的线性搜索的区别?
    二分查找时间复杂度是O(logN)，线性搜索时间复杂度是O(N)。
    二分查找要求数据是有序的，线性搜索对数据没有要求。

  16. 各种排序的思路
    冒泡排序：两两比较每次把最值元素拿出来。
    插入排序：每次将一个待排序的数，插入到排好序的数组中去。
    选择排序：跟冒泡排序差不多，遍历未排序部分，然后拿出来。
    快速排序：将数组分为两部分，一部分比基数大，一部分比基数小，然后在递归。O(Nlog(N))
    堆排序：构建一个堆每次取堆顶元素。O(Nlog(N))
    归并排序：分成子问题，合并两个有序数组。O(Nlog(N))

  17. 最短路算法思路
    迪杰斯特拉算法（单源最短路径）：每次选择最近的一个点，然后使用这个点优化距离表。

  18. 最小生成树算法思路
    (1) Kruska算法，时间复杂度(ElogE,E边数)
    1.1 对所有边进行排序
    1.2 挑一个权重最小的边
    1.3.1 如果不联通，加入这条边。如果联通，不加入这条边。

(2) Prim算法，时间复杂度(NN,N顶点数)
2.1 随机选取一个点
2.2 选择离他最近的点，然后加上边
2.3 重复步骤1-2

  1. 邻接表和邻接矩阵
    邻接表，存储的是该点的所有邻居结点.
    邻接矩阵，如果相邻是1,不相邻是0.

  2. 介绍一下深度优先搜索和广度优先搜索是如何实现的？
    DFS： 递归实现
    BFS： 使用队列存储待遍历结点

  3. 介绍一下字符串匹配算法：朴素的匹配算法和KMP算法。 朴素的匹配算法： 一个一个匹配，暴力法。
    KMP算法：在匹配失败的情况下，利用之前比较的情况，来使主串的起始点更靠后。(我是半瓶水)

  4. 什么是动态规划？
    动态规划：利用历史记录来避免重复计算而已。
    动态规划通常有三步：(1) 定义dp数组含义 (2) 初始化dp数组 (3) 找出数组之间的关系，进行计算
    经典例题：爬楼梯、小偷入室

  5. 什么是回溯算法？ 什么是回溯算法：进行下一步选择之后，然后重新回到当前状态
    回溯算法通常有三步：(1) for所有选择 (2) 进入某一选择 (3) 恢复状态，回来
    经典例题：全排列、八皇后

updatedupdated2021-09-212021-09-21

相关文章：