Appearance
算法与数据结构 共13题
题目清单
- M15：关于哈希表正确的有？
- M16：关于堆正确的有？
- M17：关于二分正确的有？
- M18：关于递归 DFS 正确的有？
- F01：补全 lower_bound。
- F02：补全链表反转。
- F03：补全快速幂。
- F06：补全 BFS 队列。
- F08：补全 KMP 失配跳转。
- F09：补全堆下沉孩子下标。
- F10：补全前缀和区间查询。
- F13：补全拓扑排序入度更新。
- F14：补全滑动窗口无重复。
不定项选择题
M15. 不定项选择题
关于哈希表正确的有？
A. 平均 O(1) 依赖分布和负载 B. 冲突可链地址解决 C. 最坏可能退化 D. 一定保持 key 有序
答案：A、B、C
解析：哈希表不保证顺序。
M16. 不定项选择题
关于堆正确的有？
A. priority_queue 默认大顶堆 B. 可用于 TopK C. 插入 O(log n) D. 查找任意元素 O(1)
答案：A、B、C
解析：堆只能快速访问堆顶，不能 O(1) 查任意元素。
M17. 不定项选择题
关于二分正确的有？
A. 要求答案或谓词有单调性 B. 可用于 sqrt C. 边界容易错 D. 不需要循环终止条件
答案：A、B、C
解析：二分核心是单调性和边界设计。
M18. 不定项选择题
关于递归 DFS 正确的有？
A. 可能栈溢出 B. 适合树/图遍历 C. 需要 visited 防重复 D. 永远比 BFS 快
答案：A、B、C
解析：DFS/BFS 取决于问题，没有永远更快。
代码填空
F01. 代码填空
补全 lower_bound。
cpp
int lowerBound(vector<int>& a, int x) {
int l=0, r=a.size();
while (l<r) {
int m=l+(r-l)/2;
if (/*1*/) {
l=/*2*/;
}
else {
r=/*3*/;
}
}
return l;
}答案：
cpp
a[m] < x
m + 1
m解析：第一个 >= x，mid 小于目标时丢弃左侧。
F02. 代码填空
补全链表反转。
cpp
ListNode* rev(ListNode* h) {
ListNode* pre=nullptr;
while (h) {
ListNode* nxt=/*1*/;
h->next=/*2*/;
pre=/*3*/;
h=nxt;
}
return pre;
}答案：
cpp
h->next
pre
h解析：先保存 next，再改指针，否则后续链表丢失。
F03. 代码填空
补全快速幂。
cpp
long long qpow(long long a, long long n, long long mod) {
long long ans=1%mod;
while (n) {
if (/*1*/) {
ans=/*2*/;
}
a=/*3*/;
n>>=1;
}
return ans;
}答案：
cpp
n & 1
ans * a % mod
a * a % mod解析：指数按二进制拆，低位为 1 就乘入答案。
F06. 代码填空
补全 BFS 队列。
cpp
int bfs(vector<vector<int>>& g, int s) {
queue<int> q;
vector<int> vis(g.size());
q.push(s);
vis[s]=1;
int cnt=0;
while (!q.empty()) {
int u=q.front();
/*1*/;
cnt++;
for (int v:g[u]) {
if (!vis[v]) {
/*2*/;
q.push(v);
}
}
}
return cnt;
}答案：
cpp
q.pop()
vis[v] = 1解析：BFS 出队后访问邻居，入队时立刻标记避免重复入队。
F08. 代码填空
补全 KMP 失配跳转。
cpp
while (j>0 && s[i]!=p[j])
j = /*1*/;答案：
cpp
nxt[j - 1]解析：KMP 失配后跳到上一个最长相等前后缀长度。
F09. 代码填空
补全堆下沉孩子下标。
cpp
int l = i * 2 + /*1*/;
int r = i * 2 + /*2*/;答案：
cpp
1
2解析：数组堆中下标 i 的左右孩子是 2i+1、2i+2。
F10. 代码填空
补全前缀和区间查询。
cpp
sum(l, r)= prefix[/*1*/] - prefix[/*2*/];
// prefix[0]=0, 区间闭区间 [l, r]答案：
cpp
r + 1
l解析：前缀和 prefix[i] 表示前 i 个元素之和。
F13. 代码填空
补全拓扑排序入度更新。
cpp
for (int v:g[u]) {
if (--indeg[v] == /*1*/) {
q.push(v);
}
}答案：
cpp
0解析：入度变为 0 表示所有前置已处理，可以入队。
F14. 代码填空
补全滑动窗口无重复。
cpp
if (last.count(c) {
) left=max(left, /*1*/);
}
last[c]=right;答案：
cpp
last[c] + 1解析：重复字符在窗口内时，左边界移动到上次位置后一格。
