数据结构面试题

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

数据结构

  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) 恢复状态,回来
    经典例题:全排列、八皇后