Silencer76

06-18 15:05 已编辑牛客_牛客运营(实习员工)

发布于北京

关注

独家首发 | 2024京东秋招后端开发笔试真题深度解析！

秋招季战火重燃，各大厂的笔试题如约而至。京东作为电商巨头，其技术岗位的竞争向来激烈。今年的后端开发笔试题考察了哪些知识点？难度如何？

今天，我们就为大家独家带来新鲜出炉的2024京东秋招后端开发岗第1批笔试真题，并附上深度解析，希望能为正在求职路上的你提供一些参考和帮助！

想挑战一下原题？点击这里直达：2024京东秋招后端开发岗笔试真题(第一批)

一、精选选择题解析

选择题是考察候选人基础知识扎实程度的试金石。我们精选了三道覆盖不同领域的题目，来看看你是否能轻松应对。

1. (算法-时间复杂度) 以下函数的时间复杂度是多少？

void foo(int n, int x, int y) {
    int z = 0;
    if (n <= 0) {
        z = x + y;
    } else {
        foo(n - 1, x + 1, y);
        foo(n - 1, x, y + 1);
    }
}

A. O(2^n)

B. O(n)

C. O(logn)

D. O(n^2)

正确答案：A

考点解析： 这是一道典型的递归函数时间复杂度分析题。

递推关系：函数 foo(n) 会调用两次 foo(n-1)。因此，其执行次数的递推关系可以表示为 T(n) = 2T(n-1) + c (c为常数时间操作)。
递归树：我们可以将调用过程想象成一棵二叉树。根节点是 foo(n)，它有两个子节点 foo(n-1)，每个 foo(n-1) 又有两个子节点 foo(n-2)，以此类推，树的深度为 n。
复杂度计算：这棵近似完全二叉树的节点总数约为 2^n。因此，函数调用的总次数是指数级的。时间复杂度为 O(2^n)。

2. (数据库-SQL) 某网站的数据库有一个成绩表myscore，希望找出成绩表中平均分小于90的所有试卷。

A. select paper_id from myscore where sum(score) < 90 group by paper_id

B. select paper_id from myscore group by paper_id having avg(score) < 90

C. select paper_id from myscore where avg(score) < 90

D. select paper_id from myscore where avg(score) < 90 group by paper_id

正确答案：B

考点解析： 这道题考察SQL查询中 WHERE 和 HAVING 子句的关键区别。

GROUP BY：题目要求计算"平均分"，这是针对每个"试卷"的，所以必须先用 GROUP BY paper_id 对数据进行分组。
HAVING vs WHERE：WHERE 子句用于在分组前过滤原始的行数据，它不能作用于聚合函数（如 AVG(), SUM()）。HAVING 子句则用于在分组后过滤这些分组，它可以（也通常是）作用于聚合函数。
分析选项：
- A, C, D 选项都在 WHERE 子句中使用了聚合函数，这是错误的。
- B 选项正确地先进行 GROUP BY 分组，然后使用 HAVING 子句对分组后的结果（每个试卷的平均分）进行筛选。

3. (操作系统-Linux) 在 Linux 中，将文件 xyz 中的单词 "AAA" 全部替换为 "BBB"，正确的命令为？

A. sed 's/AAA/BBB' xyz > xyz

B. sed 's/AAA/BBB/g' xyz > xyz

C. replace 's/AAA/BBB/p' xyz > xyz

D. replace 's/AAA/BBB/d' xyz > xyz

正确答案：B (有陷阱)

考点解析： 本题考察 sed (Stream Editor) 命令，但包含一个非常常见的陷阱。

替换语法：sed 的替换语法是 s/旧内容/新内容/标志。要替换行内"全部"匹配项，需要使用 g (global) 标志。因此，从语法上看，s/AAA/BBB/g 是正确的意图。
重定向陷阱：所有选项都使用了 > xyz 的方式来尝试将输出写回原文件。这是一个严重错误！Shell在执行命令前会先处理I/O重定向，> xyz 会立刻将 xyz 文件清空。然后 sed 再尝试从这个已经被清空的文件中读取，结果自然是什么也读不到，最终 xyz 变成一个空文件。
正确做法：安全的、用于原地修改文件的 sed 命令是使用 -i 选项，例如：sed -i 's/AAA/BBB/g' xyz。
结论：虽然所有选项在实际操作中都是错误的，但本题很可能意在考察 sed 的 g 标志。在给出的选项中，B 是唯一一个表达了"全局替换"意图的。考生需要识别出重定向的陷阱，并理解 g 标志的作用。

二、压轴编程题详解

编程题是评估候选人代码能力和问题解决能力的核心环节。今年的三道题分别考察了前缀和、自定义排序和树的深度优先搜索，都是面试中的高频考点。

1. 牛牛与切割机

知识点：前缀和, 枚举

题目描述 有一个长度为 n 的序列 a，牛牛想对这个序列切割一刀，把它划分成两个非空序列。一个序列为 a[1...p]，另一个为 a[p+1...n]。切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。

题目分析 这是一个典型的最优化问题。我们需要遍历所有可能的切割点，计算出每个切割点对应的两个子数组的和，然后求出它们的乘积，最后在所有结果中找到最小值。为了避免在每次切割时都重复计算子数组的和（这样会导致O(n²)的复杂度，无法通过），我们可以采用前缀和的思想进行优化。

解题思路

计算总和：首先遍历一次数组，计算出整个序列的元素总和 sum。
遍历并计算：使用一个循环，遍历从 i = 0 到 n-2 的所有切割点。
维护左侧和：在循环中，用一个 long long 类型的变量 temp 累积左侧子序列的和。
计算乘积并更新：对于每个切割点 i，左侧和为 temp，右侧和即为 sum - temp。计算两者的乘积，并与全局最小值 mi（需要初始化为一个极大的数）比较，更新 mi。
循环结束后，mi 中存储的就是最小的切割代价。

参考代码 (C++)

#include <iostream>
using namespace std;
int a[1010100];
int main() {
    int n,i;
    cin>>n;
    int sum=0;
    for(i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    long long temp=0;
    long long mi=1e18;
    for(i=0;i<n-1;i++){
        temp+=a[i];
        mi=min(mi,temp*(sum-temp));
    }
    cout<<mi<<'\n';
}

2. 字符串排序

知识点：排序, 字符串

题目描述 给定一个包含26个不同小写字母的字符串 abc，它定义了一种新的字母表排序规则。例如，abc 为 "bac..." 时，代表 b 的优先级高于 a，a 高于 c。现在给定 n 个字符串，请将这 n 个字符串按照新的字母表规则排序。

题目分析 这道题的本质是实现一个自定义排序。标准的排序算法（如 std::sort）是基于默认的字典序进行比较的，我们需要提供一个自定义的比较函数，让排序算法根据我们指定的规则来判断两个字符串的先后顺序。

解题思路

建立位次映射：为了能快速查询到每个字符在新规则下的优先级，我们使用一个 map<char, int> 类型的全局变量 mp。遍历读入的规则字符串 str，将每个字符及其索引（即优先级）存入 mp 中。
编写自定义比较函数：实现一个 bool cmp(string s, string t) 函数。
- 函数内，逐位比较两个字符串 s 和 t 的字符，直到达到其中较短字符串的长度。
- 在第 i 位，如果 s[i] 和 t[i] 不同，就通过查询 mp 来比较它们的优先级，并返回 mp[s[i]] < mp[t[i]] 的结果。
- 如果遍历完共同长度后所有字符都相同，那么就根据字符串的总长度来判断，短的排在前面，返回 s.size() < t.size()。
排序与输出：在 main 函数中，读入数据后，调用 sort(s, s+n, cmp)，其中 s 是存储所有字符串的数组，n 是字符串数量。最后，遍历并输出排好序的字符串数组。

参考代码 (C++)

#include<bits/stdc++.h>
using namespace std;
string s[1010];
map<char,int>mp;
bool cmp(string s,string t){
    int i;
    for(i=0;i<min(s.size(),t.size());i++){
        if(s[i]!=t[i])return mp[s[i]]<mp[t[i]];
    }
    return s.size()<t.size();
}

int main(){
    string str;
    cin>>str;
    for(int i=0;i<26;i++){
        mp[str[i]]=i;
    }
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++)cout<<s[i]<<'\n';

}

3. 牛牛的糖果树

知识点：树, 深度优先搜索(DFS)

题目描述 牛牛有一棵 n 个节点的树，每个节点上都有一种颜色的糖果。对于树中的任意一个节点，牛牛可以获取它子树中的所有糖果。她会先找出出现次数最多的糖果颜色（如有多种，都算最多），然后把这些颜色的糖果全部丢掉。在剩下的糖果中，她会统计出现次数为奇数的糖果颜色，并计算这些颜色的异或和。牛牛想知道，对于所有节点作为子树根节点的情况，这个异或和的最大值是多少。

题目分析 这是一个树形问题，需要对每个节点，计算其子树内符合特定条件的颜色的异或和，并最终求出所有结果中的最大值。核心是统计每个节点子树中各种颜色的出现次数，这可以通过深度优先搜索（DFS）后的"树上动态规划"思想实现。

解题思路

数据结构：使用邻接表 g 存树，a 数组存每个节点的颜色。关键是定义一个二维数组 tong[x][j]，用于记录在以 x 为根的子树中，颜色 j 出现的次数。
深度优先搜索 (DFS)：设计 dfs(int x, int pr) 函数，x是当前节点，pr是其父节点。
- 后序遍历：函数首先递归调用 dfs(i, x) 处理 x 的所有子节点 i。
- 统计自身：在递归前或后，将当前节点 x 的颜色计入统计数组，即 tong[x][a[x]]++。
- 合并子树信息：当对子节点 i 的 dfs 调用返回后，意味着 tong[i] 数组已计算完毕。此时，将子树 i 的颜色统计信息合并到父节点 x 上：tong[x][j] += tong[i][j]。
计算与更新：在 dfs 函数处理完一个节点 x 的所有子树并合并信息后：
- 计算出 x 子树中出现次数最多的颜色频率 ma。
- 计算结果 res：遍历所有颜色 j，如果 tong[x][j] 不等于 ma 且为奇数，就进行异或操作 res ^= j。
- 用 res 更新全局最大值 ans。
从根节点1开始执行 dfs(1, 0)，结束后 ans 即为最终答案。

参考代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int a[1010];
vector<int>g[1010];
int tong[1010][1010];       //tong[i][j] 代表i号节点的子树中，颜色j的出现次数。
int ans;
void dfs(int x,int pr){
    tong[x][a[x]]++;
    for(auto i:g[x]){
        if(i==pr)continue;
        dfs(i,x);
        for(int j=1;j<=1000;j++){
            tong[x][j]+=tong[i][j];
        }
    }
    int ma=0;
    for(int j=1;j<=1000;j++)ma=max(ma,tong[x][j]);
    int res=0;
    for(int j=1;j<=1000;j++){
        if(tong[x][j]!=ma){
            if(tong[x][j]&1){
                res^=j;
            }
        }
    }
    ans=max(ans,res);
}
int main(){
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans<<'\n';
}