首页 > 【回馈牛客】测开学习路线——2_数据结构和数据库
头像
初闻不知卷中意
编辑于 2021-02-18 12:27
+ 关注

【回馈牛客】测开学习路线——2_数据结构和数据库

序言

这次更数据结构和数据库。
数据结构可能对于非科班来说不算友好,我会多介绍点学习方法;科班的同学只需要复习一遍知识,然后多刷题就行了。
对于测开,数据库的掌握主要是会写sql语句,其次需要掌握《数据库系统原理》(科班必修课)里前几章内容,InnoDB底层,redis底层,具体知识点如下

数据结构

  • 范围
    一般来说,面试官喜欢问
    十大排序里的快速排序,堆排序,冒泡排序的源码,算***涉及到
    数组,
    链表(判断是否有环、环入口、合并链表、复制复杂链表),栈(括号匹配,逆波兰式计算,实现队列),
    队列(实现栈),
    二叉树(前、中、后序遍历 递归/非递归代码;平衡二叉树,二叉排序树;B/B+树),
    图(问的比较少,知道深度遍历和广度遍历思想)等

  • 学习方法(个人学习方法分享)
    1.科班:复习《数据结构》严蔚敏版,可以配合王道408的数据结构视频和书食用
    2.非科班:如果感觉上面两本书比较枯燥,可以看《大话数据结构》(听说比较有趣),配合王道视频

    复习完基础知识,就需要刷《剑指offer》、Leadcode前100,边刷边总结方法。刷多了你会发现一些规律,有的题可以用刷过的方法解。
    刷的时候如果一开始感觉自己写比较困难,可以先参照书上的源码敲一遍,理解思路,然后逐步脱离答案,自己想解法。最后多总结,同时也要锻炼自己的调bug水平,以及工具的使用(c++ STL了解底层的话用起来很方便)


  • 十大排序
    1.冒泡排序 O(n^2) * 稳定
    适用于基本有序、数据量小序列
    2.选择排序 O(n^2)
    3.插入排序 O(n^2)(直接插入,折半插入)
    4.希尔排序 O(nlogn)
    5.归并排序 O(nlogn)
    6.快速排序 O(nlogn) * 不稳定(枢轴改进方法)
    7.堆排序 O(nlogn) * 不稳定
    8.计数排序 O(n+k)
    9.桶排序 O(n+k)
    10.基数排序 O(nk)
    重点是上面带
    的排序算法源码,以及稳定性。其余算法了解即可,会源码更佳。

  • 二叉树
    1.遍历
    前序,中序,后序遍历
    递归,非递归
    2.平衡二叉树
    插入自调整
    LL,RR,LR,RL
    3.红黑树 *
    应用:c++ set/map java HashMap(数组+链表+红黑树)
    当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

    五大性质:
    性质1. 节点是红色或黑色。
    性质2. 根节点是黑色。
    性质3.所有叶子结点都是黑色。(叶子是NIL(值为空且黑色)节点,虚拟出来的)
    性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5.. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。黑色完美平衡

与平衡为二叉树对比(或问,为什么c++和java底层不用平衡二叉树)

图片说明

4.B、B+树
应用:操作系统的文件索引和数据库索引
性质与区别:请自己查阅

为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引?
图片说明


  • BFS、DFS
    找对应题刷就行了

数据库

  • 事务
    1)ACID
    原子性、一致性、隔离性、持久性 定义
    2)隔离等级
    可串行化
    可重复读(mysql默认)
    读提交(其他大多数数据库默认)
    读未提交
    定义
    3)并发事务下的问题
    脏读
    不可重复读
    幻读
    定义

  • 索引
    1.分类
    聚簇索引
    非聚簇索引
    联合索引
    图片说明
    2.InnoDB与MyISAM的区别
    索引方案、索引查询方式、数据存储格式、是否支持事务

    • 范式
      图片说明

    • InnoDB技术点
      内存缓冲池 Buffer Pool
      检查点 CheckPoint
      redo/undo页
      查阅资料自己理解

    • redis

    1.持久化方法
    RDB/AOF
    2.字段基本类型
    图片说明

    • MongoDB

    1.优势
    面向文档存储、自动分片、高度可扩展性
    2.存储方式
    虚拟内存(操作系统知识点)+持久化
    3.适用场景
    大数据

  • 如何选择数据库
    图片说明

  • 写一个sql语句
    推荐大家先复习完语法后刷牛客/LeadCode上的sql题,中等练完就行,要求不太高

    重点
    增删改查
    多表查询


等下更,别急

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐