后端开发刷题 | 笔试

Linux 中，下面哪个选项不是 inode 中记录的数据（）

A

最后一次读取时间

B

最近修改的时间

C

该文件的实际内容

D

该文件的容量

正确答案：C

解析：储存文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode，中文译名为"索引节点”。

Java 中，下面代码会出现编译错误的是（）

A

int[] arr = new int[]{1, 2, 3};

B

int[] arr = {1, 2, 3};

C

int arr[] = new int[3];

D

int arr[3] = {1, 2, 3};

正确答案：D

下面 Java 代码的运行结果为（）

1 2 3 4 5 6

public static void main(String[] args) {     List<Integer> list1 = Arrays.asList(1, 2, 3);     List<Integer> list2 = Arrays.asList(1, 2, 3);     System.out.println(list1 == list2);     System.out.println(list1.equals(list2)); }

A

false true

B

true false

C

true true

D

false false

正确答案：A

一个具有23个顶点的连通无向图，最少有（）条边。

A

0

B

1

C

22

D

23

正确答案：C

解析：

在一个无向图中，从每一个顶点到每一个其它顶点都存在一条路径，则此无向图是连通的。

有n个顶点的连通图最多有n（n-1）/2 条边，最少有n-1条边

考虑以下递归函数：

1 2 3 4 5

function calculateI(i):     if i <= 0:         return 0     else:         return 2 * calculateI(i - 1) + 1

对于给定的初始i值为4，计算最终的i值是多少？

A

14

B

15

C

16

D

17

正确答案：B

对数组a=[25, 10, 30, 15, 20, 5]采用快速排序的方法，以第一个元素为基准，从小到大排序，则第一次得到的划分结果是（ ）

A

[5, 10, 20, 15, 25, 30]

B

[25, 10, 30, 15, 20, 5]

C

[10, 5, 25, 30, 15, 20]

D

[15, 10, 20, 25, 30, 5]

正确答案：A

解析：快速排序的划分过程是通过选择一个基准元素，将数组分为两个部分，小于基准的放在左边，大于基准的放在右边。以第一个元素25为基准，第一次划分后，小于25的元素为[10, 15, 20, 5]，大于25的元素为[30]，所以划分结果为[5, 10, 20, 15, 25, 30]，对应选项A。

假设操作系统中有5个作业，它们的到达时刻分别是0,3,5,7,9，运行时间分别是4,2,3,1,5，系统在t=2时开始作业调度，如果采用时间片轮转调度算法，每个时间片为3个时间单位，那么在t=2时，选中的作业是（）。

A

J1

B

J2

C

J3

D

J4

E

J5

正确答案：A

解析：

1. 第一个作业在t=0时到达，因此在t=2时它已经在系统中等待调度。
2. 第二个作业在t=3时到达，所以在t=2时它还未到达系统，不能被调度。
3. 第三个、第四个和第五个作业分别在t=5, 7, 9时到达，因此在t=2时它们也都不能被调度。

由于只有第一个作业在t=2时已经在系统中，所以系统会选择这个作业进行调度。

接下来，我们应用时间片轮转调度算法。每个时间片是3个时间单位，而第一个作业的运行时间是4个时间单位。因此，在第一个时间片（t=2到t=5）内，这个作业会运行3个时间单位，然后在下一个时间片开始时（即t=5时），如果它还未完成，则根据轮转调度算法，它可能会被暂停，让其他已到达的作业（如果有的话）获得执行机会。但在这个特定情况下，直到t=5时，只有第一个作业是已到达并可调度的。

关于HTTP协议，以下描述错误的是（）。

A

HTTP协议是一种无状态的协议。

B

HTTP协议使用TCP作为传输协议。

C

HTTP协议的默认端口号是80。

D

HTTP协议可以加密传输数据，提高安全性。

正确答案：D

解析：HTTP协议是一种无状态的协议，因为每个请求都是独立的，服务器不会保存客户端的状态信息，因此选项A描述正确。HTTP协议使用TCP作为传输协议，因此选项B描述正确。HTTP协议的默认端口号是80，因此选项C描述正确。但是HTTP协议本身不提供数据加密功能，因此选项D描述错误。为了提高传输数据的安全性，可以使用HTTPS协议，它是HTTP协议的安全版本，使用SSL/TLS协议加密传输数据。因此，正确答案是D。

编程题：

小欧喝水

小欧拿了𝑛n个杯子排成了一排，其中有𝑘k个杯子装满了水，剩余的𝑛−𝑘n−k个杯子为空的。小欧每回合的操作如下：
1. 随机选择一个杯子。
2. 杯子是空的。回合直接结束。
3. 杯子是满的。如果小欧上一回合喝过了水，则回合结束；否则将喝完这杯水，回合结束。

小欧想知道，她喝完所有水的回合数期望是多少？

输入描述:

 

输出描述:

一个浮点数，代表期望的回合数。

示例1

输入

1 1

输出

1.000000000

说明

只有一杯水，第一回合就可以喝完。

示例2

输入

2 2

输出

4.000000000

说明

第一回合有100%的概率喝一杯水。第二回合无论是否选到有水的杯子都不会喝水。0.5*3+0.25*4+0.125*5+...=4

解题思路：

用动态规划（DP）来计算小欧喝完所有水的期望回合数

定义 dp[i] 为小欧还需要喝 i 杯水时，期望的回合数。

1. 如果 i = 0，即没有水需要喝了，那么期望的回合数是 0。
2. 如果 i > 0，我们考虑两种情况：
   • 选择一个空杯子的概率是 (n-k)/n，这会导致回合直接结束，不增加任何回合数（但这种情况在计算期望时，会贡献为 1 次尝试，因为选择了一个空杯子后，下一轮会继续）。
   • 选择一个满杯子的概率是 k/n，如果小欧上一回合没有喝水（即这是一个新的回合，或者上回合选择了空杯子），她需要再喝一次水，并且之后还需要喝 i-1 杯水。如果小欧上一回合已经喝过水（这在连续两次选择满杯子时出现），她只需继续计算 i-1 杯水的期望。

我们可以写出如下的状态转移方程：

这里，(1 + dp[i-1])/2 表示小欧上一回合喝过水的期望（即连续两次选到满杯子的概率，并喝掉第二杯），(1 + dp[i])/2 表示小欧上一回合没喝过水的期望（即当前回合选到满杯子并喝掉）。但由于两种情况在连续选到满杯子时是互斥的，并且它们的概率都是 k/n，所以我们将它们加在一起然后除以 2 来平均。

然而，上述方程可以简化为：

进一步整理得：

现在，我们可以从 dp[1] 开始递推到 dp[k]。

代码（使用C语言实现）：

#include <stdio.h>  double dp[100005]; // 假设 k 不会太大，可以调整数组大小  int main() {  int n, k;  scanf("%d %d", &n, &k);  dp[0] = 0; // 基准情况  for (int i = 1; i <= k; i++) {  dp[i] = (double)n / k + (double)k / n * dp[i - 1];  }  printf("%.6f\n", dp[k]); // 输出结果，保留6位小数  return 0;  
}