一、单项选择题

1. 有5个红色球和5个蓝色球，它们除了颜色之外完全相同。将这10个球拍成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法? {{ select(1) }}

• 25
• 30
• 6
• 120

2. 在KMP算法中,对于模式串P="abacaba",其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度，且数组下标从0开始)的值是什么? {{ select(2) }}

• {0,0,1,0,1,2,3}
• {0,1,2,3,4,5,6}
• {0,0,1,1,2,2,3}
• {0,0,0,0,1,2,3}

3. 对一个大小为16(下标0-15)的数组上构建满线段树。查询区间[3,11]时最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)? {{ select(3) }}

• 7
• 8
• 9
• 10

4. 将字符串"cat","car","cart","case","dog",插入空的Trie树(前缀树)中。构建完成Trie树(包括根节点)共有多少个结点? {{ select(4) }}

• 8
• 9
• 10
• 11

5. 对于一个包含n个结点和m条边的有向无环图(DAG)，其拓扑排序的结果有多少种可能? {{ select(5) }}

• 只有1种
• 最多n种
• 等于n-m种
• 以上都不对

6. 在一个大小为13的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为H(key)=key mod 13。依次插入关键字18，26，35，9，68，74。插入74后，它最终被放置在哪个索引位置? {{ select(6) }}

• 5
• 7
• 9
• 11

7. 一个包含8个顶点的完全图(顶点的编号为1到8)，任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点3和7之间的边权重为|7-3|=4。该图的最小生成树总权重是多少? {{ select(7) }}

• 7
• 8
• 9
• 10

8. 如果一棵二叉搜索树的后序遍历序列是5,4,8,12,10,6，那么该树的前序遍历是什么? {{ select(8) }}

• 6,4,2,5,10,8,12
• 6,4,5,2,10,12,8
• 2,4,5,6,8,10,12
• 12,8,10,5,2,4,6

9. 一个0-1背包问题,背包容量为20。现有5个物品,其重量和价值分别为7,5,4,3,6和15,12,9,7,13。装入背包的物品能获得的最大总价值是多少? {{ select(9) }}

• 43
• 41
• 45
• 44

10. 在一棵以结点1为根的树中,结点12和结点18的最近公共祖先(LCA)是结点4。那么下列哪个结点的 LCA组合是不可能出现的? {{ select(10) }}

• LCA(12,4)=4
• LCA(18,4)=4
• LCA(12,18,4)=4
• LCA(12,1)=4

11. 递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少? {{ select(11) }}

• O(n)
• O(n log n)
• O(n²)
• O(n² log n)

12. 在一个初始为空的最小堆(min-heap)中,依次插入元素20,12,15,10,5,然后连续执行两次"删除最小值"(delete-min)操作。请问此时堆顶元素是什么? {{ select(12) }}

• 10
• 12
• 15
• 20

13. 1到1000之间，不能被2、3、5中任意一个数整除的整数有多少个? {{ select(13) }}

• 266
• 267
• 333
• 734

14. 斐波那契数列的定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算F(n)的时间复杂度是指数级的。而使用动态规划(或迭代)方法的时间复杂度是线性的。造成这种巨大差异的根本原因是? {{ select(14) }}

• 递归函数调用栈开销过大
• 操作系统对递归深度有限制
• 朴素递归中存在大量的重叠子问题未被重复利用
• 动态规划使用了更少的数据存储空间

15. 有5个独立的、不可抢占的任务A1,A2,A3,A4,A5需要在一台机器上执行(从时间0开始执行),每个任务都有对应的处理时长和截止时刻，按顺序分别为3,4,2,5,1和5,10,3,15,11。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务? {{ select(15) }}

• 处理时间最短的任务A5
• 截止时间最早的任务A3
• 处理时间最长的任务A4
• 任意一个任务都可以

二、程序阅读题

第一题

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

1. 当输入的n=3的时候，程序输出的答案为3。 {{ select(16) }}

• 正确
• 错误

2. 在dfs函数运行过程中k的取值会满足1≤k≤n+1。 {{ select(17) }}

• 正确
• 错误

3. 删除第19行的"flag[i]=false;"，对答案不会产生影响。 {{ select(18) }}

• 正确
• 错误

4. 当输入的n=4的时候,程序输出的答案为() {{ select(19) }}

• 11
• 12
• 24
• 9

5. 如果因为某些问题，导致程序运行第25行的dfs函数之前，数组p的初值并不全为0，则对程序的影响是() {{ select(20) }}

• 输出的答案比原答案要小
• 无法确定输出的答案
• 程序可能陷入死循环
• 没有影响

6. 假如删去第14行的"if(flag[i])continue;"，输入3，得到的输出答案是() {{ select(21) }}

• 27
• 3
• 16
• 12

第二题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using%d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 0;
    for (w = 1; w * (w + 1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
        if (check(nh)) {
            for (int j = nh - ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}

1. 当输入为"6 5 1"时,猜测次数为5;当输入"6 5 2"时,猜测次数为3。 {{ select(22) }}

• 正确
• 错误

2. 不管输入的n和k具体为多少，t=2时的猜测数总是小于等于t=1时的猜测数。 {{ select(23) }}

• 正确
• 错误

3. 不管t=1或t=2，程序都一定会猜到正确结果。 {{ select(24) }}

• 正确
• 错误

4. 函数guess1在运行过程中,cnt_broken的值最多为() {{ select(25) }}

• 0
• 1
• 2
• n

5. 函数guess2在运行过程中，最多使用的猜测次数的量级为() {{ select(26) }}

• O(n)
• O(n²)
• O(√n)
• O(log n)

6. 当输入的n=100的时候,代码中t=1和t=2分别需要的猜测次数最多分别为() {{ select(27) }}

• 100, 14
• 100, 13
• 99, 14
• 99, 13

第三题

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k = k >> 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 - 1]) {
            ++cntans1[newcnt1 - 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
            ;
        if (las < cnt1 && ans1[las] + ans2[i] == 0)
            ans += cntans1[las];
    }
    printf("%lld\n", ans);
    return 0;
}

1. 删除第51行的"std::sort(ans2.begin(),ans2.end());"后,代码输出的结果不会受到影响。 {{ select(28) }}

• 正确
• 错误

2. 假设计算过程中不发生溢出,函数mpow(x,k)的功能是求出xᵏ的取值。 {{ select(29) }}

• 正确
• 错误

3. 代码中第39行到第50行的目的是为了将ans1数组进行"去重"操作。 {{ select(30) }}

• 正确
• 错误

4. 当输入为"3 1 5 1 2 -1 2 1 2"时,输出结果为() {{ select(31) }}

• 4
• 8
• 0
• 10

5. 记程序结束前p数组元素的最大值为P,则该代码的时间复杂度是() {{ select(32) }}

• O(n)
• O(mⁿ log mⁿ)
• O(mⁿ/² log mⁿ/²)
• O(mⁿ/² (log mⁿ/² + log P))

6. 本题所求出的是() {{ select(33) }}

• 满足a,b,c∈[1,m]的整数方程a³+b³=c³的解的数量
• 满足a,b,c∈[1,m]的整数方程a²+b²=c²的解的数量
• 满足xᵢ∈[0,m]的整数方程∑ᵢ₌₁ⁿ kᵢ·xᵢᵖⁱ=0的解的数量
• 满足xᵢ∈[1,m]的整数方程∑ᵢ₌₁ⁿ kᵢ·xᵢᵖⁱ=0的解的数量

三、程序填空题

第一题

(特殊最短路)给定一个含N个点、M条边的带权无向图,边权非负。起点为S,终点为T。对于一条S到T的路径，可以在整条路径中，至多选择一条边作为"免费边":当第一次经过这条被选中的边时，费用视为0;如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从S到T的最小总费用。

以下代码求解了上述问题。试补全程序。

1. ①处应填() {{ select(34) }}

• 0
• 1
• -1
• false

2. ②处应填() {{ select(35) }}

• d[u][used]
• d[u][0]
• d[t][used]
• INF

3. ③处应填() {{ select(36) }}

• d[v][1]
• d[v][used]
• d[u][used]
• d[v][0]

4. ④处应填() {{ select(37) }}

• d[v][0]
• d[v][1]
• d[u][0]
• d[u][1]

5. ⑤处应填() {{ select(38) }}

• d[t][1]
• d[t][0]
• min(d[t][0], d[t][1])
• d[t][0] + d[t][1]

第二题

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线(编号0∼n-1)，已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货(结果记为1)，否则正常收货(记为0)。受售后压力限制，在所有发货批次中，最多只能有k次退货(即结果为1的次数≤k)。工厂的目标是，设计最少的间接测试轮数w(发货总批次)，保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标,包含两部分:i)确定w的最小值,并设计最优测试方案;ii)根据测试结果推断存在缺陷的生产线。该程序确定w最小值的方法为:由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。

test_subset()函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。

试补全程序。

1. ①处应填() {{ select(39) }}

• (1<<w)<n
• count_patterns(w,k)<n
• count_patterns(k,w)<n
• comb(w,k)<n

2. ②处应填() {{ select(40) }}

• next_permutation(bits.begin(), bits.end())
• prev_permutation(bits.begin(), bits.end())
• next_permutation(bits.begin(), bits.begin()+ones)
• prev_permutation(bits.begin(), bits.begin()+ones)

3. ③处应填() {{ select(41) }}

• (j>>i)&1
• (i>>j)&1
• code[i][j]==1
• code[j][i]==1

4. ④处应填() {{ select(42) }}

• (signature>>i)&1
• (signature>>i)^1
• signature|(1<<i)
• (signature>>i)|1

5. ⑤处应填() {{ select(43) }}

• is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
• code[j]==sig_bits
• plan[j]==sig_bits
• code[j][i]==sig_bits[i]