备战秋招冲击大厂 Java 面试题库—数据结构与算法专项练习

1. 数据结构定义

数据结构作为计算机系统中用于存储与组织数据的一种方式，本质上是具备一种或多种特定关联性的数据元素集合。在多数情况下，合理选择的数据结构能够有效提升程序的运行效率或存储性能。同时，数据结构往往与高效的检索算法和索引技术密切相关。

• 数组：其物理存储单元具有连续且顺序排列的特性
• 链表：链表属于物理存储单元非连续、非顺序排列的存储形式，其数据元素之间的逻辑顺序依赖于链表内部指针链接所形成的次序
• 队列：队列（queue）是一种线性表结构，仅允许在某一端执行插入操作，而在另一端实施删除操作
• 栈：栈（stack）亦称堆栈，是一种运算受到限制的线性表结构。其插入和删除操作仅限于线性表的一端，该端被定义为栈顶，而相对应的另一端则称为栈底
• 堆：堆可被视作一种以完全二叉树形式呈现的数组对象。其中根节点值最大的堆被称为最大堆或大根堆；而根节点值最小的堆则被称为最小堆或小根堆。构建堆的时间复杂度为O(n)，并且堆始终满足以下条件：其总是一个完全二叉树；任一节点的值不会超过或低于其父节点的值；
• 散列表：（Hash table，也叫哈希表），是一种基于关键码值（Key value）直接访问的数据结构

2. 堆的创建、插入、删除、堆排序

• 堆的插入：在最小堆构建完成后，于其末尾位置添加新元素，此操作可能导致堆的结