第九章(数据结构与算法 面试真题)

一、数据结构真题

1. 数组和链表的区别？

参考答案：

2. 栈和队列的区别？

参考答案：

• 栈（Stack）：后进先出（LIFO）
• 队列（Queue）：先进先出（FIFO）

// 栈
classStack {
constructor() {
this.items = [];
    }
push(item) { this.items.push(item); }
pop() { returnthis.items.pop(); }
peek() { returnthis.items[this.items.length - 1]; }
}

// 队列
classQueue {
constructor() {
this.items = [];
    }
enqueue(item) { this.items.push(item); }
dequeue() { returnthis.items.shift(); }
front() { returnthis.items[0]; }
}

3. 什么是哈希表？

参考答案：

哈希表通过哈希函数将键映射到数组索引，实现 O(1) 平均时间复杂度的增删改查。

classHashTable {
constructor(size = 100) {
this.size = size;
this.table = newArray(size);
    }

hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i)) % this.size;
        }
return hash;
    }

set(key, value) {
const index = this.hash(key);
this.table[index] = value;
    }

get(key) {
const index = this.hash(key);
returnthis.table[index];
    }
}

冲突解决：

• 链地址法
• 开放地址法

4. 什么是二叉树？

参考答案：

每个节点最多有两个子节点的树结构。

classTreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
    }
}

// 二叉树遍历
functionpreOrder(node) { // 前序
if (!node) return;
console.log(node.val);
preOrder(node.left);
preOrder(node.right);
}

functioninOrder(node) { // 中序
if (!node) return;
inOrder(node.left);
console.log(node.val);
inOrder(node.right);
}

functionpostOrder(node) { // 后序
if (!node) return;
postOrder(node.left);
postOrder(node.right);
console.log(node.val);
}

5. 什么是堆？

参考答案：

堆是一种完全二叉树，分为最大堆和最小堆。

// 最小堆
classMinHeap {
constructor() {
this.heap = [];
    }

insert(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
    }

bubbleUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[parent] <= this.heap[index]) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }
}

二、算法真题

6. 排序算法有哪些？

参考答案：

// 快速排序
functionquickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}

// 归并排序
functionmergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
returnmerge(left, right);
}

functionmerge(left, right) {
const result = [];
while (left.length && right.length) {
        result.push(left[0] <= right[0] ? left.shift() : right.shift());
    }
return [...result, ...left, ...right];
}

7. 二分查找怎么实现？

参考答案：

functionbinarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;

while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
    }

return -1;
}

时间复杂度：O(log n)

8. 什么是动态规划？

参考答案：

动态规划将问题分解为子问题，保存子问题的解避免重复计算。

// 斐波那契数列
functionfib(n) {
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
return dp[n];
}

// 优化空间
functionfib(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
return curr;
}

9. 什么是贪心算法？

参考答案：

贪心算法每步选择局部最优，期望得到全局最优。

// 找零问题
functionfindChange(amount) {
const coins = [25, 10, 5, 1];
const result = [];
for (const coin of coins) {
while (amount >= coin) {
            result.push(coin);
            amount -= coin;
        }
    }
return result;
}

10. 什么是回溯算法？

参考答案：

回溯算法尝试所有可能，找到满足条件的解。

// 全排列
functionpermute(nums) {
const result = [];

functionbacktrack(path, used) {
if (path.length === nums.length) {
            result.push([...path]);
return;
        }

for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true;
backtrack(path, used);
            path.pop();
            used[i] = false;
        }
    }

backtrack([], []);
return result;
}

11. 什么是布隆过滤器？

参考答案：

布隆过滤器是一种空间效率高的概率数据结构。

classBloomFilter {
constructor(size = 100) {
this.size = size;
this.data = newArray(size).fill(0);
    }

hash(value, seed) {
let hash = 0;
for (let i = 0; i < value.length; i++) {
            hash = (hash * seed + value.charCodeAt(i)) % this.size;
        }
return hash;
    }

add(value) {
for (let i = 1; i <= 3; i++) {
const index = this.hash(value, i);
this.data[index] = 1;
        }
    }

contains(value) {
for (let i = 1; i <= 3; i++) {
const index = this.hash(value, i);
if (this.data[index] === 0) returnfalse;
        }
returntrue;
    }
}

12. 什么是 LRU 缓存？

参考答案：

Least Recently Used 最近最少使用缓存。

classLRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = newMap();
    }

get(key) {
if (!this.cache.has(key)) return -1;

const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
    }

put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
        } elseif (this.cache.size >= this.capacity) {
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
        }
this.cache.set(key, value);
    }
}

13. 什么是 Trie 树？

参考答案：

前缀树，用于字符串搜索。

classTrieNode {
constructor() {
this.children = {};
this.isEnd = false;
    }
}

classTrie {
constructor() {
this.root = newTrieNode();
    }

insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
                node.children[char] = newTrieNode();
            }
            node = node.children[char];
        }
        node.isEnd = true;
    }

search(word) {
const node = this.searchPrefix(word);
return node && node.isEnd;
    }

searchPrefix(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) returnnull;
            node = node.children[char];
        }
return node;
    }
}

14. 什么是图的遍历？

参考答案：

// BFS - 广度优先
functionbfs(graph, start) {
const visited = newSet();
const queue = [start];
    visited.add(start);

while (queue.length) {
const node = queue.shift();
console.log(node);

for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// DFS - 深度优先
functiondfs(graph, start, visited = newSet()) {
if (visited.has(start)) return;

console.log(start);
    visited.add(start);

for (const neighbor of graph[start]) {
dfs(graph, neighbor, visited);
    }
}

15. 什么是拓扑排序？

参考答案：

functiontopologicalSort(n, edges) {
const graph = Array.from({ length: n }, () => []);
const inDegree = newArray(n).fill(0);

for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }

const queue = [];
for (let i = 0; i < n; i++) {
if (inDegree[i] === 0) queue.push(i);
    }

const result = [];
while (queue.length) {
const node = queue.shift();
        result.push(node);

for (const neighbor of graph[node]) {
            inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

return result.length === n ? result : [];
}

16. 什么是并查集？

参考答案：

classUnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = newArray(n).fill(0);
    }

find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
        }
returnthis.parent[x];
    }

union(x, y) {
const px = this.find(x);
const py = this.find(y);

if (px === py) return;

if (this.rank[px] < this.rank[py]) {
this.parent[px] = py;
        } elseif (this.rank[px] > this.rank[py]) {
this.parent[py] = px;
        } else {
this.parent[py] = px;
this.rank[px]++;
        }
    }
}

17. 什么是跳表？

参考答案：

classSkipListNode {
constructor(val, maxLevel) {
this.val = val;
this.forward = newArray(maxLevel).fill(null);
    }
}

classSkipList {
constructor() {
this.header = newSkipListNode(-1, 16);
this.level = 0;
    }

randomLevel() {
let level = 0;
while (Math.random() < 0.5 && level < 16) {
            level++;
        }
return level;
    }

search(target) {
let current = this.header;
for (let i = this.level; i >= 0; i--) {
while (current.forward[i] && current.forward[i].val < target) {
                current = current.forward[i];
            }
        }
return current.forward[0] && current.forward[0].val === target;
    }
}

18. 什么是位运算？

参考答案：

// 判断奇偶
n & 1

// 交换a和b
a ^= b;
b ^= a;
a ^= b;

// 取绝对值
Math.abs(n) === (n ^ (n >> 31)) - (n >> 31)

// 判断2的幂次
(n & (n - 1)) === 0

// 统计1的个数
functioncountBits(n) {
let count = 0;
while (n) {
        n &= (n - 1);
        count++;
    }
return count;
}

19. 什么是递归和迭代？

参考答案：

// 递归 - 阶乘
functionfactorial(n) {
if (n <= 1) return1;
return n * factorial(n - 1);
}

// 迭代 - 阶乘
functionfactorialIter(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
        result *= i;
    }
return result;
}

// 尾递归优化
functionfactorialTail(n, acc = 1) {
if (n <= 1) return acc;
returnfactorialTail(n - 1, n * acc);
}

20. 什么是分治算法？

参考答案：

// 分治 - 归并排序
functionmergeSort(arr) {
if (arr.length <= 1) return arr;

const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));

returnmerge(left, right);
}

functionmerge(left, right) {
const result = [];
let i = 0, j = 0;

while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

return result.concat(left.slice(i)).concat(right.slice(j));
}

📌 面试重点：数组链表、排序算法、二分查找、动态规划是高频考点。