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*