滴滴研发岗模拟卷（二）
模仿 2024 秋招研发岗笔试：19 道单选 + 1 道多选 + 2 道编程，限时 100 分钟。单选/多选来自专项练习题库，编程题为原创。（单选/多选答案取自专项题库（参考）；编程题为原创，提供思路与参考代码。）
一、单选题（第 1–19 题，每题 5 分）
线性表(a_1,a_2,a_3,...,a_n)以链表方式存储时,访问第i位置元素的时间复杂性为（）？
给定一个m行n列的整数矩阵（如图），每行从左到右和每列从上到下都是有序的。判断一个整数k是否在矩阵中出现的最优算法，在最坏情况下的时间复杂度是________。
给定下列程序，那么执行printf("%d\n", foo(20, 13));的输出结果是（）
int foo(int x, int y){
if (x <= 0 || y <= 0)
return 1;
return 3 * foo( x-6, y/2 );
}
Given the following class:
public class Cat
{
long length;
public Cat(long l)
{
length = 1;
}
public static void main(String arg[])
{
Cat c1, c2, c3;
c1 = new Cat(10L);
c2 = new Cat(10L);
c3 = c2;
long m = 21L;
}
}
Which expression returns true?
下列数据结构具有记忆功能的是？
在支持多线程的系统中，进程P创建的若干线程不能共享的是？
对任何数据结构链式存储结构一定优于顺序存储结构()
Linux中包括两种链接：硬链接（Hard Link）和软连接（Soft Link），下列说法正确的是（）
以下哪个数据结构不是多型数据类型()
关于回滚段的使用，下列哪种分配方法比较合适?
如入栈序列为1,2,3,4,5,则可能得到的出栈序列为()
牛客网的数据库有一个paper表，现在要查询试卷名字包含"人人网"的所有数据，则sql语句应该为？
下列的进程状态变化中，哪些是不可能发生的？
内排序要求数据一定要以顺序方式存储()
下面有关虚函数的描述，说法错误的是？
一个递归算法必须包括()
若有以下定义和语句：
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, *p = a;
则不能表示a数组元素的表达式是
以下程序的输出结果是
#include <stdio.h>
int a, b;
void fun() {
a = 100;
b = 200;
}
int main() {
int a = 5, b = 7;
fun();
printf("%d %d\n", a, b);
return 0;
}
下面名词解释错误的是：
二、多选题（第 20 题，5 分）
请描述http请求get和post的区别，下面描述正确的有：
三、编程题（第 21–22 题，自测后对照参考解法）
给定 n 个会议，每个会议有开始时间 start 和结束时间 end。同一时间只能参加一个会议，求最多能参加多少个会议（区间调度问题）。
输入：第一行 n，接下来 n 行每行两个整数 start end。
输出：最多能参加的会议数。
示例：
输入：
4
1 3
2 4
3 5
4 6
输出：
2
查看参考解法
贪心：按结束时间升序排序，依次选择「开始时间不早于上一个所选会议结束时间」的会议，数量最多。
def max_meetings(meetings):
meetings.sort(key=lambda x: x[1])
cnt = 0
end = -1
for s, e in meetings:
if s >= end:
cnt += 1
end = e
return cnt
有 n 件物品和一个容量为 W 的背包。每件物品有重量 weight[i] 和价值 value[i]，每件物品只能取一次（0-1 背包）。求背包能装下的最大总价值。
输入：第一行 n W，第二行 n 个重量，第三行 n 个价值。
输出：最大总价值。
示例：
输入：
3 5
2 3 4
3 4 5
输出：
7
查看参考解法
0-1 背包动态规划：dp[j] 表示容量 j 时的最大价值，逆序枚举容量避免重复取。
def knapsack(W, weights, values, n):
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]