北京大学数院-856大数据-2025年-解析

北京大学数院-856大数据-2025年

1. $n$ 个人随机选三门课，求至少有一门课没人选的概率。（15分）

Solution:

设$A_i = \{第i门课没有人选择\}$,则我们有：

$$\begin{aligned} P(至少有一门课没人选择) &= P(A_1\cup A_2 \cup A_3) \\ & = P(A_1) + P(A_2) + P(A_3) - P(A_1A_2) -P(A_1A_3)-P(A_2A_2) + P(A_1A_2A_3) \\ & =3\frac{2^n}{3^n} - 3\frac{1}{3^n} \end{aligned}$$

2. 随机变量$(X,Y)\sim N(u_1,u_2,\sigma_1^2,\sigma_2^2,\rho)$, $U=X+CY$,$V=Y-CY$,求$(U,V)$的分布，并求$U,V$独立时，$C$的值。（15分）

Solution:

我们可以看到$U,V$是正态的线性组合，由正态分布的性质，我们有

$$\begin{aligned} \begin{bmatrix} U\\ V \end{bmatrix} = \begin{bmatrix} 1&C \\ 0&1-C \end{bmatrix} \begin{bmatrix} X\\ Y \end{bmatrix}\sim N( \begin{bmatrix} u_1+Cu_2 \\ (1-C)u_2 \end{bmatrix}, \begin{bmatrix} \sigma_1^2+C^2\sigma_2^2 + 2\rho C\sigma_1 \sigma_2 & (1-C)(\rho\sigma_1\sigma_2+C\sigma _2^2)\\ (1-C)(\rho\sigma_1\sigma_2+C\sigma _2^2) &(1-C)^2\sigma^2_2 \end{bmatrix}) \end{aligned}$$

由正态分布的性质我们知道，当$C=1$时$U,V$是相互独立。

3. $X_1, X_2, \ldots, X_n \overset{\text{iid}}{\sim} N(u,\frac{1}{\lambda})$,u已知，且有$\lambda \sim Gamma(\alpha,\beta)$，其中$f(\lambda|\alpha,\beta) =\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}\lambda^{\alpha-1}exp(-\beta\lambda)$ ,求$\lambda |\vec{X}$和$E(\lambda| \vec{X})$。（20分）

Solution:

这题的Gamma分布其实是给错了，所以说哪怕是考研真题也会有错误，我们要大胆质疑！

$$\begin{aligned} \pi(\lambda) &\propto \lambda^{\alpha-1}exp(-\beta\lambda) \\ f(\lambda|\vec{X}) &\propto f(\vec{X} | \lambda)\pi(\lambda) \\ &\propto \lambda^{\frac{n}{2}}exp(-\frac{\lambda\sum(x_i-u)^2}{2})\lambda^{\alpha-1}exp(-\beta\lambda) \\ &\propto \lambda^{(\frac{n}{2}+\alpha)-1}exp(-(\beta+\frac{\sum(x_i-u)^2}{2})\lambda) \end{aligned}$$

所以由核函数我们可以看出来$\lambda |\vec{X} \sim Gamma(\alpha+\frac{n}{2}, \beta+\frac{\sum(x_i-u)^2}{2})$,所以$E(\lambda| \vec{X}) = \frac{\alpha+\frac{n}{2}}{\beta+\frac{\sum(x_i-u)^2}{2}}$

4. $X_1, X_2, \ldots, X_m \overset{\text{iid}}{\sim} N(u_1, \sigma^2)$,$Y_1, Y_2, \ldots, Y_n \overset{\text{iid}}{\sim} N(u_2, \sigma^2)$,其中$\sigma^2$未知，求$u_1-Cu_2$的$1-\alpha$的置信区间,$C$为常数。（20分）

Solution:

其实有多种方式构造这个枢轴量，我们在这采取类似于课本的构造方式。

$$\begin{aligned} &\bar{x} - C\bar{y} \sim N(u_1- Cu_2, (\frac{1}{m}+C^{2} \frac{1}{n})\sigma^2) \\ (m-1)&S_x^2 + (n-1)S_y^2 \sim \sigma^2\chi^2_{m+n-2} \end{aligned}$$

所以我们可以构造如下枢轴量:

$$t = \sqrt{\frac{mn(m+n-2)}{mC^2+n}}\frac{\bar{x}-C\bar{y}- (u_1-Cu_2)}{\sqrt{(m-1)S_x^2 + (n-1)S_y^2}} \sim t(m+n-2)$$

所以置信区间如下：

$$[\bar{x}-C\bar{y} \pm t_{1-\alpha/2}\sqrt{\frac{mC^2+n)}{mn(m+n-2)}}\sqrt{(m-1)S_x^2 + (n-1)S_y^2}]$$

5. $Y_i = \beta x_i + \epsilon_i$,$i =1,...,n$,其中$\epsilon_i \overset{\text{iid}}{\sim} N(0,\sigma^2)$
   (1)求$\hat{\beta}_{MSE}$，给出$\sigma^2$的一个无偏估计。（5分）
   (2)求$\beta$的$1-\alpha$的置信区间。（5分）
   (3)设$y_0 = \hat{\beta}X_0 + \epsilon_0$，$\epsilon_0 \text{与} \epsilon_i$独立，给出$y_0$的$1-\alpha$的预测区间。（10分）

Solution:

(1).

$$\begin{aligned} \hat{\beta} &= argmin\sum(Y_i - \beta x_i)^2 \\ &= \frac{\sum x_i Y_i}{\sum x_i^2} \end{aligned}$$

由Cochran定理，我们知道：

$$\sum(Y_i - \hat{\beta}x_i)^2 \sim \sigma^2\chi^2_{n-1}\\$$

所以$\hat{\sigma^2} = \frac{\sum(Y_i - \hat{\beta}x_i)^2}{n-1}$是$\sigma^2$的一个无偏估计
(2)

$$\hat{\beta} \sim N(\beta, \frac{\sigma^2}{\sum x_i^2})$$

所以我们有

$$\frac{\hat{\beta}-\beta }{\sqrt{\frac{\hat{\sigma}^2}{(n-1)\sum x_i^2}}} \sim t(n-1)$$

所以$\beta$的$1-\alpha$的置信区间是：

$$[-t_{1-\alpha/2} \sqrt{\frac{\hat{\sigma}^2}{(n-1)\sum x_i^2}} +\hat{\beta}, t_{1-\alpha/2} \sqrt{\frac{\hat{\sigma}^2}{(n-1)\sum x_i^2}} +\hat{\beta} ]$$

(3)
因为是预测区间,我们有:

$$y_0 = \hat{\beta}x_0 + \epsilon_0 \sim N(y_0, \sigma^2(\frac{x_0^2}{\sum{x_i^2}} + 1))$$

所以$y_0$的$1-\alpha$的预测区间是：

$$[\hat{\beta}X_0 - t'_{1-\alpha/2}\sqrt{\frac{\hat{\sigma}^2}{(n-1)}(\frac{x_0^2}{\sum x_i^2}+1)},\hat{\beta}X_0 + t'_{1-\alpha/2}\sqrt{\frac{\hat{\sigma}^2}{(n-1)}(\frac{x_0^2}{\sum x_i^2}+1)}]$$

6. (1) 比较顺序查找、折半查找和散列查找，并说明为什么有散列和二分这种快速查找还需要顺序。（5分）
   (2) 比较栈和队列。（5分）
   (3) 说说$B_{+}$树与$B$树相比的优点。（5分）

Solution:

(1) 顺序查找：
适用范围：无序数组或链表。
时间复杂度：O(n)。
优点：简单易实现，不需要数据排序；适合频繁更新的数据集。
缺点：大规模数据时效率低。
折半查找（二分查找）：
适用范围：已排序的数组或列表。
时间复杂度：O(log n)。
优点：查找速度快，适合静态或少变动的数据集。
缺点：需要预排序，不适合链表结构。
散列查找：
适用范围：通过哈希函数映射键值到特定位置，适用于哈希表。
时间复杂度：理想情况下接近O(1)，冲突严重时可能退化为O(n)。
优点：平均查找速度极快，插入和删除操作也快。
缺点：需要额外空间，哈希函数设计不当会导致性能下降。

即使有了散列查找和二分查找，顺序查找依然重要：

1. 灵活性：不要求数据有序，适用于任何线性数据结构。
2. 简单性：实现简单，在小型数据集上表现良好。
3. 适应性：适合频繁更新的数据集，维持有序列表成本高。
4. 通用性：广泛适用，只要能逐个访问元素即可。

(2)
栈 (Stack) vs 队列 (Queue)

栈 (Stack)

• 操作方式：后进先出（LIFO）
  • 入栈（Push）：向栈顶添加元素。
  • 出栈（Pop）：移除并返回栈顶元素。
  • 查看栈顶（Peek/Top）：获取栈顶元素但不移除。
• 特点：元素按照最后加入的最先被移除的原则处理；所有操作在一端（栈顶）进行。
• 应用场景：
  • 函数调用栈
  • 撤销操作（如文本编辑器中的撤销功能）
  • 表达式求值与转换

队列 (Queue)

• 操作方式：先进先出（FIFO）
  • 入队（Enqueue）：向队尾添加元素。
  • 出队（Dequeue）：移除并返回队头元素。
  • 查看队头（Front）：获取队头元素但不移除。
• 特点：元素按照最先加入的最先被移除的原则处理；插入在队尾，删除在队头。
• 应用场景：
  • 任务调度（如操作系统中的进程调度）
  • 缓冲区（如网络通信中的数据包传输）
  • 广度优先搜索（BFS）算法

主要区别

特性	栈 (Stack)	队列 (Queue)
存取顺序	后进先出（LIFO）	先进先出（FIFO）
操作位置	所有操作在栈顶	插入在队尾，删除在队头
应用场景	追踪最近添加项或回溯	按顺序处理任务或事件
实现复杂度	相对简单	稍微复杂一些
内存管理	只需跟踪一个指针（栈顶）	需要管理前后两个指针（队头和队尾）

通过上述对比可以看出，选择使用栈还是队列取决于具体的应用需求和你希望如何管理和访问数据。每种结构都有其独特的优点和适用场景。

(3)
B+ 树与B 树相比的优点

1. 更高效的范围查询

• B+树：所有关键字都存储在叶子节点中，并且叶子节点之间有链表相连。这使得范围查询非常高效，因为可以顺序扫描相连的叶子节点。
• B树：关键字分布在所有层级的节点中，进行范围查询时需要在树的不同层级间跳跃，效率较低。

2. 更高的扇出（Fan-out）

• B+树：每个内部节点只存储关键字而不存储数据记录指针，因此可以容纳更多的关键字，提高了每个节点的利用率，减少了树的高度。
• B树：每个节点不仅存储关键字还存储数据记录指针，导致每个节点能容纳的关键字数量较少，树的高度相对较高。

3. 更好的磁盘访问性能

• B+树：由于所有数据都在叶子节点中，一次范围查询只需访问一层叶子节点，减少了磁盘I/O次数。
• B树：可能需要访问多层节点来完成同样的查询，增加了磁盘I/O开销。

4. 简化的插入和删除操作

• B+树：插入和删除操作仅影响叶子节点及其直接父节点，简化了维护平衡的操作。
• B树：插入和删除可能导致非叶子节点的变化，增加了维护树结构复杂度。

5. 支持并行处理

• B+树：叶子节点之间的链表结构使得多个查询可以在不同的叶子节点上并行执行，提高了并发性。
• B树：缺乏这种直接的链表连接，难以实现高效的并行查询。

通过上述对比可以看出，$B_+$树在许多方面提供了比$B$树更优的性能和特性，特别是在支持大规模数据库系统的高效查询、插入和删除操作方面表现出色。

7. 开放地址法建立散列表。（15分）

Solution:

开放地址法（Open Addressing）是一种解决散列表中哈希冲突的方法。它规定所有元素都存储在散列表的数组本身中，而不是像链地址法那样将溢出元素链接到外部链表。当发生冲突时，通过特定的探测序列来寻找下一个可用的位置。

基本步骤

1. 初始化：

   • 创建一个大小为$m$的数组$T[0..m-1]$，并将所有位置初始化为空（或使用特殊值表示空位）。

2. 插入操作：

   • 对于要插入的键$k$，计算其哈希值$h(k)$。
   • 如果$T[h(k)]$为空，则直接插入该位置。
   • 如果$T[h(k)]$已被占用，则根据某种探测策略找到下一个可用位置，并继续尝试插入，直到找到空位为止。

3. 查找操作：

   • 对于要查找的键$k$，从$h(k)$开始按照相同的探测策略依次检查，直到找到键$k$或遇到空位（表示该键不在表中）。

4. 删除操作：

   • 删除操作较为复杂，因为直接删除可能会导致后续插入或查找失败。通常采用标记删除的方式，即用特殊标记代替实际删除，以保持探测序列的完整性。

探测策略

常见的探测策略包括以下几种：

1. 线性探测（Linear Probing）

线性探测是最简单的探测方法之一。它在发生冲突时，顺序地检查下一个位置，直到找到空位或遍历完整个数组。

• 公式：$h_i(k) = (h(k) + i) \mod m$，其中$i = 0, 1, 2, ..., m-1$

2. 二次探测（Quadratic Probing）

二次探测通过增加步长的平方来减少聚集现象。这种方法可以有效避免“初级聚集”，但仍然可能存在“次级聚集”。

• 公式：$h_i(k) = (h(k) + c_1 \cdot i + c_2 \cdot i^2) \mod m$，其中$c_1$和$c_2$是常数，$i = 0, 1, 2, ..., m-1$

3. 双重散列（Double Hashing）

双重散列使用第二个哈希函数来计算探测的步长，这减少了哈希冲突的聚集效应。

• 公式：$h_i(k) = (h_1(k) + i \cdot h_2(k)) \mod m$，其中$h_1(k)$是初始哈希函数，$h_2(k)$是第二个哈希函数，$i = 0, 1, 2, ..., m-1$

优缺点

• 优点：

  • 存储紧凑：所有元素都在数组内，不需要额外的链表空间。
  • 查找速度快：可以直接定位到数据的位置。

• 缺点：

  • 当负载因子较高时，探测效率较低，可能导致大量的碰撞和性能下降。
  • 删除操作复杂，需要额外的维护。
  • 对探测策略的选择有较高要求，不同策略的性能差异可能较大。

---

8. 给出Kruskal建边的顺序。（15分）

Solution:

直接给图推流程是相对简单的，在这里我们给出用并查集实现Kruskal的算法。

class UnionFind:
def init(self, n):
self.parent = list(range(n))
self.rank = [1] * n

def find(self, p):
    if self.parent[p] != p:
        self.parent[p] = self.find(self.parent[p])  
    return self.parent[p]

def union(self, p, q):
    rootP = self.find(p)
    rootQ = self.find(q)
    if rootP != rootQ:
        if self.rank[rootP] > self.rank[rootQ]:
            self.parent[rootQ] = rootP
        elif self.rank[rootP] < self.rank[rootQ]:
            self.parent[rootP] = rootQ
        else:
            self.parent[rootQ] = rootP
            self.rank[rootP] += 1

def connected(self, p, q):
    return self.find(p) == self.find(q)

def kruskal(edges, V):
edges.sort(key=lambda edge: edge[2])

uf = UnionFind(V)
mst = []
mst_weight = 0

for edge in edges:
    u, v, weight = edge
 
    if not uf.connected(u, v):
        uf.union(u, v)
        mst.append(edge)
        mst_weight += weight

return mst, mst_weight

9.写出堆排序的代码，并说明堆排序是否稳定。（15分）

Solution:

堆排序并不是一个稳定的排序算法，就比如初始数组为1,2,2，在删除1后下个数是第三个2，而不是第二个2。

class Min_heap(object):
def init(self,
data):
self.data = data
self.l = len(data)
self.build_Min_heap()

def build_Min_heap(self):
    start = int((self.l-2) / 2) 
    for i in range(start,-1,-1):
        l_c = i * 2 + 1
        r_c = i * 2 + 2
        m = l_c
        if r_c < self.l and self.data[r_c] < self.data[l_c]:
            m = r_c
        if self.data[m] < self.data[i]:
            self.data[m], self.data[i] = self.data[i], self.data[m]

def is_min_heap(self, node):
    l_c = node * 2 + 1
    r_c = node * 2 + 2
    if r_c < self.l:
        if self.data[r_c] < self.data[node] or not self.is_min_heap(r_c):
            return False
        
    if l_c < self.l:
        if self.data[l_c] < self.data[node] or not self.is_min_heap(l_c):
            return False
    return True

def add_element(self, element):
    self.l += 1 
    self.data.append(element)
    t = self.l-1
    i = int((self.l -2) / 2)
    while(i >=0 and self.data[i] > element):
         self.data[t] = self.data[i]
         t = i
         i = int((i-1) / 2)
    self.data[t] = element

def del_element(self):
    last = self.l-1
    self.l -= 1
    self.data[0], self.data[last] = self.data[last], self.data[0]
    i = 0
    d = self.data[0]
    while(i * 2 + 1 <self.l):
        l_c = i * 2 + 1
        r_c = i * 2 + 2 
        t = l_c
        if r_c <self.l and self.data[r_c] < self.data[t]:
            t = r_c

        if self.data[t] < d:
            self.data[i] = self.data[t]
        else:
            break
        i = t
    self.data[i] = d 

def sort_heap(self):
    while(self.l!=1):
        self.del_element()