当前位置：首页 > article >正文

DeepSeek模拟阿里面试——数据结构

article 2025/2/12 14:02:55

哈希表
基本原理
哈希表通过哈希函数将键映射到数组中的一个索引位置，允许在O(1)的平均时间复杂度内进行查找、插入和删除操作。

冲突处理
开放地址法：包括线性探测、二次探测和双重哈希。
拉链法：每个哈希值对应一个链表，存储冲突的键。

性能
哈希函数质量：影响键值分布，减少冲突。
负载因子：控制在0.7到0.8之间，平衡时间和空间效率。

应用场景
缓存系统：快速查找。
数据库索引：提高查询速度。
集合操作：判断元素存在性。

二叉树
常见类型
二叉搜索树（BST）：查找、插入和删除的平均时间复杂度为O(log n)，但不平衡时可能退化为O(n)。
平衡二叉树（如AVL树）：通过旋转保持平衡，保证O(log n)操作时间。
B树和B+树：适用于数据库和文件系统，减少磁盘I/O。
红黑树：自平衡，适合高效插入、删除和查找。

应用场景
BST：动态集合和有序列表。
平衡二叉树：数据库索引。
B树和B+树：数据库和文件系统索引。
红黑树：高效集合和字典实现。

常见算法题
平衡二叉树判断：递归检查左右子树高度差。
层次遍历：队列实现逐层访问。

挑战与考虑
哈希表：选择好的哈希函数，处理大规模数据时的内存使用。
二叉树：保持平衡的旋转和颜色调整复杂性。
高效实现：哈希表的负载因子调整和扩容。

总结
选择哈希表或二叉树取决于需求：快速查找选哈希表，有序数据或高效动态操作选二叉树。

数组和链表的主要区别
存储结构：
数组：数据元素存储在连续的内存空间中，支持随机访问。
链表：由节点组成，每个节点包含数据和指针，存储在动态分配的内存中。
访问方式：
数组：可以通过索引直接访问，时间复杂度为O(1)。
链表：只能通过头节点逐个遍历访问，时间复杂度为O(n)。
插入和删除：
数组：插入和删除需要移动大量元素，时间复杂度为O(n)。
链表：插入和删除只需修改指针，时间复杂度为O(1)（假设已找到位置）。
内存使用：
数组：预分配内存，可能有空间浪费。
链表：动态分配内存，额外空间用于存储指针，可能导致内存碎片。
动态数组的实现原理
动态数组（如Java的ArrayList）使用倍增策略来实现高效扩容。当数组满时，创建一个新数组（通常是原大小的两倍），并将旧数组的数据复制到新数组中。这种方法摊还分析下，每次插入平均时间为O(1)，但扩容时可能有较高的时间复杂度。
链表的优缺点
优点：
动态大小，无需预分配内存。
插入和删除操作高效（O(1)时间，假设已找到位置）。
缺点：
内存消耗较大，每个节点需要存储指针。
随机访问慢，只能顺序遍历。
数组实现栈和队列
栈：
数组实现：使用指针记录栈顶，入栈和出栈为O(1)，但栈满时需要扩容。
链表实现：无需预分配内存，但指针操作可能带来额外开销。
队列：
数组实现：使用环形数组，高效处理入队和出队，但需要处理扩容。
链表实现：更灵活，但指针操作可能导致效率稍低。
数组转链表的实现
实现步骤：
创建链表头节点。
遍历数组，依次创建节点并连接到链表中。
链表逆序的算法
迭代法：使用三个指针（前驱、当前、后继）逐步反转链表。
递归法：将链表拆分为头节点和剩余部分，递归反转并连接。
环形链表的检测
使用Floyd判圈算法（快慢指针）：
快指针一次走两步，慢指针一次走一步。
如果快指针追上慢指针，则存在环。
数组和链表的内存分配
数组：连续内存分配，适合随机访问，但插入删除效率低。
链表：动态内存分配，适合动态大小和频繁插入删除，但随机访问效率低。
双链表和单链表的区别
双链表：每个节点有两个指针，支持双向遍历，插入删除更高效。
单链表：每个节点一个指针，只能单向遍历，但内存消耗较少。
数组越界问题
问题：可能导致程序崩溃或未定义行为。
预防：访问前检查索引范围，使用支持边界检查的数据结构。