C++ 数据结构基础面试题

1. 数组和链表的区别是什么？

答案：

• 存储方式数组：连续内存空间链表：非连续内存，通过指针连接
• 访问方式数组：随机访问O(1)链表：顺序访问O(n)
• 插入删除数组：O(n)，需要移动元素链表：O(1)，只需修改指针
• 内存占用数组：固定大小，可能浪费链表：动态分配，额外存储指针
• 缓存友好性数组：连续内存，缓存友好链表：分散内存，缓存不友好

2. 栈和队列的区别？如何实现？

答案：

• 特点栈：后进先出（LIFO）队列：先进先出（FIFO）
• 操作栈：push（入栈）、pop（出栈）、top（查看栈顶）队列：push（入队）、pop（出队）、front（查看队首）
• 数组实现栈维护一个top指针push：top++，存入元素pop：返回元素，top--
• 数组实现队列维护front和rear指针循环队列避免空间浪费push：rear++pop：front++
• 链表实现栈：头插法队列：头删尾插

3. 什么是哈希表？如何解决冲突？

答案：

• 哈希表定义通过哈希函数将键映射到数组索引平均O(1)的查找、插入、删除空间换时间
• 哈希函数将键转换为数组索引要求：均匀分布、计算快速、确定性
• 冲突解决链地址法（Chaining）每个位置存储链表冲突元素加入链表STL的unordered_map使用此方法开放地址法（Open Addressing）线性探测：顺序查找下一个空位二次探测：按平方数探测双重哈希：使用第二个哈希函数
• 负载因子元素数量/桶数量过高时需要rehash扩容

4. 二叉树的遍历方式有哪些？

答案：

• 前序遍历（Pre-order）根 → 左 → 右递归或栈实现
• 中序遍历（In-order）左 → 根 → 右二叉搜索树中序遍历是有序的
• 后序遍历（Post-order）左 → 右 → 根适合释放节点
• 层序遍历（Level-order）逐层遍历使用队列实现
• 递归实现

void inorder(TreeNode* root) {    if (!root) return;    inorder(root->left);    cout << root->val;    inorder(root->right);}

• 迭代实现

void inorder(TreeNode* root) {    stack<TreeNode*> s;    TreeNode* curr = root;    while (curr || !s.empty()) {        while (curr) {            s.push(curr);            curr = curr->left;        }        curr = s.top(); s.pop();        cout << curr->val;        curr = curr->right;    }}

5. 什么是二叉搜索树（BST）？

答案：

• 定义左子树所有节点 < 根节点右子树所有节点 > 根节点左右子树也是BST
• 操作复杂度查找：平均O(log n)，最坏O(n)插入：平均O(log n)，最坏O(n)删除：平均O(log n)，最坏O(n)
• 删除节点叶子节点：直接删除一个子节点：用子节点替换两个子节点：用后继或前驱替换
• 退化问题插入有序数据会退化成链表需要平衡树（AVL、红黑树）

6. 什么是平衡二叉树（AVL树）？

答案：

• 定义任意节点的左右子树高度差不超过1自平衡的二叉搜索树
• 平衡因子左子树高度 - 右子树高度取值：-1、0、1
• 旋转操作LL型：右旋RR型：左旋LR型：先左旋后右旋RL型：先右旋后左旋
• 性能查找：O(log n)插入：O(log n)删除：O(log n)严格平衡，查找效率高插入删除需要频繁旋转

7. 什么是红黑树？

答案：

• 性质节点是红色或黑色根节点是黑色叶子节点（NIL）是黑色红色节点的子节点必须是黑色从根到叶子的所有路径包含相同数量的黑色节点
• 与AVL树对比红黑树：近似平衡，插入删除快AVL树：严格平衡，查找快
• 应用STL的map、setLinux内核的进程调度Java的TreeMap
• 时间复杂度查找、插入、删除：O(log n)

8. 什么是堆？如何实现？

答案：

• 定义完全二叉树大顶堆：父节点 ≥ 子节点小顶堆：父节点 ≤ 子节点
• 数组实现节点i的左子节点：2i+1节点i的右子节点：2i+2节点i的父节点：(i-1)/2
• 操作插入：添加到末尾，上浮调整删除堆顶：用末尾元素替换，下沉调整建堆：从最后一个非叶子节点开始下沉
• 应用优先队列堆排序Top K问题

9. 图的存储方式有哪些？

答案：

• 邻接矩阵二维数组存储matrixi表示i到j的边空间：O(V²)适合稠密图
• 邻接表数组+链表每个顶点存储其邻接顶点空间：O(V+E)适合稀疏图
• 边集数组存储所有边的信息适合边操作多的场景
• 对比邻接矩阵：判断边存在O(1)，遍历邻接点O(V)邻接表：判断边存在O(degree)，遍历邻接点O(degree)

10. 常见的图遍历算法有哪些？

答案：

• 深度优先搜索（DFS）递归或栈实现尽可能深地搜索应用：拓扑排序、连通性检测
• 广度优先搜索（BFS）队列实现逐层搜索应用：最短路径、层序遍历
• DFS实现

void dfs(int v, vector<bool>& visited, vector<vector<int>>& graph) {    visited[v] = true;    for (int u : graph[v]) {        if (!visited[u]) {            dfs(u, visited, graph);        }    }}

• BFS实现