常见数据结构及面试常见代码题(1)

数组

基本操作： 插入、删除、返回指定位置的元素、得到数组所有元素的数量。

面试常见问题： 1 寻找数组第k大的数字 2 找到数组中第一个不重复的整数 3 合并两个有序数组 4 重新排列数组中的正值和负值

栈

应用： 撤销操作

基本操作：

Push 顶部插入
Pop  移除栈顶元素
isEmpty 栈为空则返回true
Top 返回顶部元素，但不移除

面试常见问题：

5 用栈计算后缀表达式 6 对栈的元素进行排序 7 判断表达式是否括号平衡

队列

应用： 银行排队

基本操作：

Enqueue(): 在队列尾部插入
Dequeue(): 移除队列头部
isEmpty(): 队列空则返回true
Top: 返回队列第一个元素

面试常见问题：

8 用队列表示栈 9 对队列前k个元素倒序 10 使用队列生成1-n的二进制数

链表

是一种重要的线性数据结构，链表就像一个节点链，每个节点包含着自己的数据和指向后续节点的指针。链表包含一个头指针，指向链表的第一个元素。当链表为空时，他指向null或者无具体内容。 应用：实现文件系统，散列表或者邻接表 基本操作：

InsertAtEnd: 在链表末尾插上元素 InsertAtHead:在链表开始插入指定元素 Delete:在链表中删除指定元素 DeleteAtHead:删除链接链表的第一个元素 Search:从链表中返回第一个元素 isEmpty: 如果链表为空，则返回true

面试常见问题：

11 翻转链表 12 检测链表中的环 13 返回链表倒数第N个节点 14 删除链表中的重复项

树

树形结构是一种层级式的数据结构，由顶点和连接他们的边形成。树中不存在环路

应用： 人工智能和一些复杂算法

树形结构基本术语：

Root: 根节点 Parent:父节点 Child: 子节点 Leaf:叶子结点 Sibling:兄弟节点

树的主要类型： 平衡树 二叉树 二叉搜索树 AVL树 红黑树 B树和B+树

常见面试题型：

15 二叉树的高度 16 二叉搜索树中第k个最大值 17 查找与根节点距离为k的节点 18 二叉树中查找给定节点的祖先节点 19 腾讯笔试（二叉树中给定节点的第层的祖先节点）

图

图示一组以网络形式相互连接的节点 图可以用邻接矩阵或者邻接表表示 常见图遍历算法：DFS 和 BFS

常见面试问题：

20 检查图是否为树 21 计算图的边数 22 找到两个顶点之间的最短路径 23 实现 DFS 和 BFS

字典树

用于快速检索，可以解决一些字符串问题。主要用于搜索字典中的单词。在搜索引擎中自动提供建议，也可用于IP的路由。

常见面试问题：

24 字典树中的总单词数 25 打印字典树中的所有单词 26 用字典树对数组元素进行排序 27 使用字典树从字典中形成单词 28 构建T9字典（字典树+DFS）

哈希表

用于唯一标识对象并将对象存储在提前计算好的唯一索引中的过程。对象以键值对的形式存储。 哈希表通常以数组的形式实现

散列数据结构的性能：

哈希函数 哈希表的大小 碰撞处理的方式

面试常见问题：

29 在数组中查找对称键值对 30 追踪遍历的完整路径 31 查找数组是否是另一数组的子集 32 检查给定的数组是否不相交

本菜鸟会陆续更新每道题的每种解法。。。。。