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

一、(15分) 甲、乙两人进行象棋比赛，每局甲胜的概率为 pp，乙胜的概率为 q=1−pq=1-p. 若某一方获胜的局数比另一方多三局，我们则认为他获得了胜利. 求甲获胜的概率.

Solution: 何书元1.19, 考虑吸收壁问题.
设 AA 表示第一局甲获胜，BiB_i 表示甲比乙多胜 ii 场下的最后获胜(i<0i<0 表示为少胜), ai(i≥0)a_{i}(i\geq 0) 表示甲比乙多胜 ii 场下的获胜概率, ai(i<0)a_{i}(i<0) 表示甲比乙少胜(乙比甲多胜) ii 场下的获胜概.由全概率公式有

P(Bi)=P(Bi∣A)P(A)P(Bi∣Aˉ)P(Aˉ)⇒ai=pai+1+(1−p)ai−1,a3=1,a−3=0.\begin{aligned} P\left( B_i\right)&=P(B_i|A)P(A)P(B_i|\bar{A})P(\bar{A})\\ \Rightarrow a_i &= pa_{i+1}+(1-p)a_{i-1}, \quad a_3=1, a_{-3} = 0. \end{aligned}

从而可以求得甲获胜的概率

a0=p31−3p+3p2.a_0 = \frac{p^3}{1-3p+3p^2}.

Remark: 同样的, 如果是多胜 kk 场，所求概率为

pk1−kp(1−p).\frac{p^k}{1-kp(1-p)}.

二、(15分)设 XX 与 YY 独立，都服从标准正态分布. 令 U=X+Y2,V=(X−Y)24U=\frac{X+Y}{2},V=\frac{(X-Y)^2}{4}, 求出 (U,V)(U,V) 的联合分布.

Solution: (X,Y)(X,Y) 的联合分布为

fX,Y(x,y)=12πe−x2+y22I(−∞<x,y<+∞).f_{X,Y}(x,y)=\frac{1}{2\pi}e^{-\frac{x^2+y^2}{2}}I(-\infty<x,y<+\infty).

而

{U=X+Y2V=(X−Y)24⇒{X=U+VY=U−Vor{X=U−VY=U+V\begin{cases} U=\frac{X+Y}{2}\\ V=\frac{(X-Y)^2}{4} \end{cases} \Rightarrow \begin{cases} X = U+\sqrt{V} \\ Y = U-\sqrt{V} \end{cases} \text{or} \begin{cases} X = U-\sqrt{V} \\ Y = U+\sqrt{V} \end{cases}

进而有 ∣J∣=1v|J|=\frac{1}{\sqrt{v}}, 且可以发现 X2+Y2=2(U2+V)X^2+Y^2 =2(U^2+V). 从而有

fU,V(u,v)=fX,Y(x,y)∣J∣=1π1ve−(u2+v)I(−∞<u<+∞,v>0).\begin{aligned} f_{U,V}(u,v)=f_{X,Y}(x,y)|J|=\frac{1}{\pi}\frac{1}{\sqrt{v}}e^{-(u^2+v)}I(-\infty<u<+\infty, v >0). \end{aligned}

三、(15分) 设 X1,⋯ ,XNX_1,\cdots, X_N 独立同分布于 U(0,1)U(0,1), X(r)X_{(r)} 是对应的次序统计量 (1≤r≤N)(1\leq r\leq N). 若 kk 为已知常数, 且 1≤r1<r2<⋯<rn≤N1\leq r_1< r_2< \cdots < r_n\leq N, 这 nn 个下标也已知. 求 E(∏i=1nX(ri)k)E\left(\prod_{i=1}^nX_{(r_i)}^k \right).

Solution: 令 Yi=X(ri)/X(ri+1),i=1,2,…,n−1Y_i =X_{(r_i)}/X_{(r_{i+1})}, i=1,2,\ldots, n-1, 以及 Yn=X(rn)Y_n = X_{(r_n)}, 可以发现 YiY_i 之间相互独立.
利用次序统计量的经典结论，我们有 Yi∼Be(ri,ri+1−ri),i=1,2,…,n−1Y_i\sim Be(r_i,r_{i+1}-r_i), i=1,2,\ldots, n-1, 以及 Yn∼Be(rn,N−rn+1)Y_n\sim Be(r_n, N-r_n+1).
故有

E(∏i=1nX(ri)k)=E(Y1kY22k⋯Ynnk)=∏i=1nE(Yiik)E\left(\prod_{i=1}^nX_{(r_i)}^k \right) =E\left( Y_1^kY_2^{2k}\cdots Y_{n}^{nk}\right)=\prod_{i=1}^n E\left( Y_i^{ik}\right)

进一步, 由Beta分布的性质有

E(∏i=1nX(ri)k)=∏i=1nE(Yiik)=∏i=1n−1(B(ri+ik,ri+1−ri)B(ri,ri+1−ri))⋅B(rn+nk,N−rn+1)B(rn,N−rn+1)=N!(N+nk)!∏i=1n(ri−1+ik)!(ri−1+(i−1)k)!\begin{aligned} E\left(\prod_{i=1}^nX_{(r_i)}^k \right) &= \prod_{i=1}^n E\left( Y_i^{ik}\right)\\ & = \prod_{i=1}^{n-1} \left( \frac{B(r_i+ik,r_{i+1}-r_i)}{B(r_i,r_{i+1}-r_i)}\right) \cdot \frac{B(r_n+nk,N-r_n+1)}{B(r_n, N-r_n+1)}\\ & = \frac{N!}{(N+nk)!}\prod_{i=1}^n\frac{(r_i-1+ik)!}{(r_i-1+(i-1)k)!} \end{aligned}

Remark: 其实本质为 X(i)/X(j)X_{(i)}/X_{(j)} 与 X(j)X_{(j)} 的独立性, 因此对于乘积形式的次序统计量我们会如下计算,

E(X(i)X(j))=E(X(i)X(j)X(j)2)=E(X(i)X(j))E(X(j)2).E\left( X_{(i)}X_{(j)}\right) = E\left( \frac{X_{(i)}}{X_{(j)}} X^2_{(j)}\right) = E\left( \frac{X_{(i)}}{X_{(j)}}\right) E\left(X^2_{(j)}\right).

请好好体会这个式子的思想对于本题解题思路的启发和体现.

四、(15分) 若 X1,X2,…,XnX_{1},X_{2},\dots,X_{n} 取自总体 N(θ,σ12)N(\theta,\sigma_1^2), Y1,Y2,…,YmY_{1},Y_{2},\dots,Y_{m} 取自总体 N(θ,σ22)N(\theta,\sigma_2^2), 其中 σ1,σ2\sigma_1,\sigma_2 已知.
(1)(7分) 设 T=cXˉ+dYˉT=c \bar{X}+d \bar{Y} 是 θ\theta 的无偏估计，求 c,dc,d 的值使得 TT 的方差最小.
(2)(8分)基于第一问求出的 TT, 给出 θ\theta 的 1−α1-\alpha 置信区间.

Solution: (1) 首先需要 ET=(c+d)θ=θET= (c+d)\theta = \theta, 从而约束为 c+d=1c+d=1. 而目标函数为
f(c,d)=Var(T)=c2σ12n+d2σ22mf(c,d)=Var(T)=c^2\frac{\sigma_1^2}{n}+d^2\frac{\sigma_2^2}{m}. 故问题可以写成

c,d=arg min⁡c,df(c,d) s.t. c+d=1\begin{aligned} c,d = \argmin_{c,d} f(c,d) \ s.t. \ c+d=1 \end{aligned}

这里可以使用拉格朗日乘除法或者二次函数极值, 也可以直接使用柯西不等式有

(nσ12+mσ22)(c2σ12n+d2σ22m)≥(c+d)2=1.\left( \frac{n}{\sigma_1^2}+ \frac{m}{\sigma_2^2}\right)\left( c^2\frac{\sigma_1^2}{n}+d^2\frac{\sigma_2^2}{m}\right) \geq (c+d)^2=1.

等号当且仅当

cσ1nnσ1=dσ2mmσ2\frac{c\frac{\sigma_1}{\sqrt{n}}}{\frac{\sqrt{n}}{\sigma_1}}=\frac{d\frac{\sigma_2}{\sqrt{m}}}{\frac{\sqrt{m}}{\sigma_2}}

时成立. 即 c=nσ22mσ12+nσ22,d=mσ12mσ12+nσ22c=\frac{n\sigma_2^2}{m\sigma_1^2+n\sigma_2^2}, d=\frac{m\sigma_1^2}{m\sigma_1^2+n\sigma_2^2}.

(2) 此时的 T=nσ22mσ12+nσ22Xˉ+mσ12mσ12+nσ22Yˉ∼N(θ,σ12σ22mσ12+nσ22)T=\frac{n\sigma_2^2}{m\sigma_1^2+n\sigma_2^2}\bar{X}+\frac{m\sigma_1^2}{m\sigma_1^2+n\sigma_2^2}\bar{Y}\sim N(\theta,\frac{\sigma_1^2\sigma_2^2}{m\sigma_1^2+n\sigma_2^2}).

故 θ\theta 的 1−α1-\alpha 置信区间为

[T−u1−α/2σ1σ2mσ12+nσ22,T+u1−α/2σ1σ2mσ12+nσ22].\left[ T-u_{1-\alpha/2}\frac{\sigma_1\sigma_2}{\sqrt{m\sigma_1^2+n\sigma_2^2}},T+u_{1-\alpha/2}\frac{\sigma_1\sigma_2}{\sqrt{m\sigma_1^2+n\sigma_2^2}}\right].

五、(15分)设回归模型为 Yi=α+βxi+ϵiY_{i}=\alpha+\beta x_{i}+\epsilon_{i}, 其中 ϵi∼i.i.d.N(0,σ2)\epsilon_{i}\overset{i.i.d.}{\sim} N(0,\sigma^2)，且 σ\sigma 已知. 现在将模型修改为 Yi=α′+β′(xi−xˉ)+ϵiY_{i}=\alpha'+\beta' (x_{i}-\bar{x})+\epsilon_{i}, 记 α^,β^\hat{\alpha},\hat{\beta} 和 α′^,β′^\hat{\alpha'}, \hat{\beta'} 分别为修改前和修改后的MLE.
(1)(5分) 请证明 α^=α′^,β^=β′^\hat{\alpha}=\hat{\alpha'},\hat{\beta}=\hat{\beta'};
(2)(5分) 请求出 α′^,β′^\hat{\alpha'},\hat{\beta'} 的分布;
(3)(5分) 请证明 α′^\hat{\alpha'} 与 β′^\hat{\beta'} 独立.

Solution: (1) Yi∼N(α+βxi,σ2)Y_i\sim N(\alpha+\beta x_{i},\sigma^2), 其似然函数为

L(α,β)=C1exp⁡{−∑i=1n(yi−α−βxi2)2σ2}. L(\alpha,\beta)=C_1\exp\left\{-\frac{\sum_{i=1}^n(y_i-\alpha-\beta x_{i}^2)}{2\sigma^2} \right\}.

从而其对数似然函数为

l(α,β)=log⁡L(α,β)=C2−∑i=1n(yi−α−βxi)22σ2. l(\alpha,\beta)=\log L(\alpha,\beta)=C_2-\frac{\sum_{i=1}^n(y_i-\alpha-\beta x_{i})^2}{2\sigma^2}.

对其求偏导

{∂l∂α=1σ2∑i=1n(yi−α−βxi)=0∂l∂β=1σ2∑i=1nxi(yi−α−βxi)=0⇒{α^=yˉ−β^xˉβ^=lxylxx\begin{cases} \frac{\partial l}{\partial \alpha}=\frac{1}{\sigma^2}\sum_{i=1}^n(y_i-\alpha-\beta x_{i})=0\\ \frac{\partial l}{\partial \beta}=\frac{1}{\sigma^2}\sum_{i=1}^nx_i(y_i-\alpha-\beta x_{i})=0 \end{cases} \Rightarrow \begin{cases} \hat{\alpha} = \bar{y}-\hat{\beta}\bar{x}\\ \hat{\beta} = \frac{l_{xy}}{l_{xx}} \end{cases}

同理, 令 xi′=xi−xˉx_i^{'}=x_i-\bar{x}, 只需要说明 lx′y/lx′x′=lxy/lxxl_{x^{'}y}/l_{x^{'}x^{'}}=l_{xy}/l_{xx}即可. 这是显然的，因为x′ˉ=0\bar{x^{'}}=0.

lxy/lxx=∑i=1n(yi−yˉ)(xi−xˉ)∑i=1n(xi−xˉ)2=∑i=1n(yi−yˉ)(xi′)∑i=1n(xi′)2=lx′y/lx′x′.l_{xy}/l_{xx}=\frac{\sum_{i=1}^n(y_i-\bar{y})(x_i-\bar{x})}{\sum_{i=1}^n(x_i-\bar{x})^2}=\frac{\sum_{i=1}^n(y_i-\bar{y})(x^{'}_i)}{\sum_{i=1}^n(x^{'}_i)^2}=l_{x^{'}y}/l_{x^{'}x^{'}}.

但此时的 xˉ\bar{x} 和 x′ˉ\bar{x^{'}} 不一定相等, 除非 xˉ\bar{x}几乎处处为0. 因此可以发现这一问出错了, 我们只能得到β^=β′^\hat{\beta}=\hat{\beta'}. 只有在xˉ\bar{x}几乎处处为0时, 才有α^=α′^\hat{\alpha}=\hat{\alpha'}.

(2) 由于 α′^\hat{\alpha'} 和 β′^\hat{\beta'} 都是正态分布随机变量的线性组合, 因此其分布还是正态分布. 我们只需要计算其期望和方差即可得到具体分布, 最终有

α′^∼N(α′,σ2n)β′^∼N(β′,σ2lx′x′)\begin{aligned} \hat{\alpha'} &\sim N\left(\alpha^{'},\frac{\sigma^2}{n}\right)\\ \hat{\beta'} &\sim N\left( \beta^{'}, \frac{\sigma^2}{l_{x^{'}x^{'}}}\right) \end{aligned}

(3)茆书内容. 利用 Cov(α′^,β′^)=−x′ˉlx′x′σ2=0Cov(\hat{\alpha'},\hat{\beta'} )= -\frac{\bar{x^{'}}}{l_{x^{'}x^{'}}}\sigma^2=0, 从而 α′^\hat{\alpha'} 与 β′^\hat{\beta'} 独立.

六、(7分) 根据关键码集台 K={xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,wul,zom}K = \{\mathrm{xal, wan, wil,zol, yo,xul, yum, wen,wim,zi,yon,xem, wul,zom}\} 画出建立AVL树的结果.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
R----xal
     L----wen
     |    L----wan
     |    R----wim
     |         L----wil
     |         R----wul
     R----yum
          L----yo
          |    L----xul
          |    |    L----xem
          |    R----yon
          R----zol
               L----zi
               R----zom

七、(8分) 给出一个从 v0v_0 开始到其他各点的最短路径的djikstra算法.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import sys

def dijkstra(graph, v0):
    """
    Dijkstra's algorithm to find the shortest path from v0 to all other vertices.
    
    :param graph: A 2D array where graph[u][v] is the weight of the edge from u to v, or
                  sys.maxsize if there is no edge.
    :param v0: The starting vertex.
    :return: A tuple containing two elements. The first is a list where element i is the
             shortest distance from v0 to i. The second is a list where element i is the
             previous vertex on the shortest path from v0 to i.
    """
    try:
        # 检查graph是否为二维列表
        if not all(isinstance(row, list) for row in graph):
            raise ValueError("Graph must be a 2D list.")

        n = len(graph)

        # 检查v0是否为有效的顶点索引
        if v0 < 0 or v0 >= n:
            raise ValueError(f"Starting vertex {v0} is out of bounds.")

        # 检查边的权重是否有效
        if any(graph[u][v] < 0 for u in range(n) for v in range(n) if graph[u][v] != sys.maxsize):
            raise ValueError("Graph contains negative weights.")

        distances = [sys.maxsize] * n
        distances[v0] = 0
        previous = [None] * n
        visited = [False] * n

        for _ in range(n):
            u = min((v for v in range(n) if not visited[v]), key=lambda v: distances[v])
            visited[u] = True

            for v in range(n):
                if graph[u][v] > 0 and not visited[v] and distances[v] > distances[u] + graph[u][v]:
                    distances[v] = distances[u] + graph[u][v]
                    previous[v] = u

        return distances, previous

    except ValueError as e:
        # 打印错误消息并退出程序
        print(f"Error: {e}")
        sys.exit(1)

# Example usage
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

v0 = 0  # Starting vertex
try:
    shortest_distances, previous_vertices = dijkstra(graph, v0)
    print("Shortest distances:", shortest_distances)
    print("Previous vertices in path:", previous_vertices)
except Exception as e:
    print(f"An error occurred: {e}")

输出样例结果

1
2
Shortest distances: [0, 2, 5, 6, 7]
Previous vertices in path: [None, 0, 1, 0, 1]

八、(10分) 给定原点 v0v_0 ，试用Prim算法求最小生成树，给出结点访问顺序序列.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys

def prim(graph, v0):
    """
    Prim's algorithm to find the minimum spanning tree starting from vertex v0.
    
    :param graph: A 2D array where graph[u][v] is the weight of the edge from u to v, or
                  sys.maxsize if there is no edge.
    :param v0: The starting vertex.
    :return: A list of vertices in the order they are added to the minimum spanning tree.
    """
    n = len(graph)
    in_mst = [False] * n  # Whether the vertex is in the minimum spanning tree
    key = [sys.maxsize] * n  # Key values used to pick minimum weight edge
    parent = [-1] * n  # Array to store constructed MST
    key[v0] = 0  # Make key value of v0 0 so that it is picked first
    mst_order = []

    for _ in range(n):
        # Pick the minimum key vertex from the set of vertices not yet included in MST
        u = min((i for i in range(n) if not in_mst[i]), key=lambda i: key[i])
        in_mst[u] = True  # Add the picked vertex to the MST
        mst_order.append(u)

        # Update key value and parent index of the adjacent vertices of the picked vertex
        for v in range(n):
            if graph[u][v] > 0 and not in_mst[v] and key[v] > graph[u][v]:
                key[v] = graph[u][v]
                parent[v] = u

    return mst_order

# Example usage
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

v0 = 0  # Starting vertex
mst_order = prim(graph, v0)

print("Node visit order for MST:", mst_order)

输出样例结果

1
Node visit order for MST: [0, 1, 2, 4, 3]

九、(10分) 分别用栈和队列进行时空状态搜索并说明有什么不同.

Solution: 在进行状态空间搜索时，栈和队列作为数据结构的选择会导致两种不同的搜索策略：深度优先搜索（DFS）和广度优先搜索（BFS）。这两种策略在时间和空间的使用效率上有所不同，适用于不同类型的问题。

使用栈进行深度优先搜索（DFS）

  1. 工作原理：栈是一种后进先出（LIFO）的数据结构。在DFS中，栈用于存储待探索的节点。当探索一个节点时，该节点的子节点被推入栈中，并在下一步被探索。

  2. 时间和空间特性：

    • 时间效率：DFS通常更快地遍历整个状态空间，但不保证找到最短路径或最优解。
    • 空间效率：DFS通常使用更少的内存，因为它只需要存储一条从根到叶子的路径。

  3. 适用场景：DFS适用于解空间较深或需要遍历整个解空间的问题。

使用队列进行广度优先搜索（BFS）

  1. 工作原理：队列是一种先进先出（FIFO）的数据结构。在BFS中，队列用于存储待探索的节点。当探索一个节点时，该节点的所有子节点被加入队列的尾部，并依次被探索。

  2. 时间和空间特性：

    • 时间效率：BFS通常更快地找到最短路径或最优解，但可能需要更长时间来遍历整个状态空间。
    • 空间效率：BFS可能需要更多内存，因为它需要存储所有已生成但尚未探索的节点。

  3. 适用场景：BFS适用于需要快速找到最短路径的问题，尤其是在状态空间较广的情况下。

比较

  • 搜索深度与广度：DFS深入到每个分支的最深处，而BFS逐层探索状态空间。
  • 路径优化：BFS更有可能找到最短路径，而DFS可能会找到较长的解决路径。
  • 内存使用：DFS在内存使用上更高效，尤其是在解空间非常深但每层分支较少的情况下。BFS在宽但浅的状态空间中效率较高。
  • 实现复杂度：DFS的实现通常更简单，尤其是在递归形式的情况下。BFS的实现相对复杂一些，需要维护一个队列。

选择使用DFS还是BFS取决于具体问题的特点和需求。例如，DFS更适合解空间较深的问题，如解决方案可能在较深的层次中；而BFS更适合寻找最短路径或最优解的情况。

十、(10分) 什么是稳定性和适应性，并解释直接插入排序如何做到以上两点.

Solution: 在排序算法的上下文中，“稳定性”和“适应性”是两个重要的特性。

  1. 稳定性（Stability）：

    • 定义：如果排序算法保证相等的元素在排序前后保持原有的顺序，则该算法是稳定的。
    • 举例：假设有一组记录 [A2, B1, A1, B2]，其中字母代表值，数字代表原始位置。在稳定的排序算法下，排序后相同字母的记录会保持原来的相对位置，例如 [A1, A2, B1, B2]。

  2. 适应性（Adaptivity）：

    • 定义：如果排序算法对已经部分排序的输入数据进行排序时，能够提高其性能，则该算法是适应性的。适应性强的算法在处理部分排序的数据时更高效。
    • 举例：如果输入数据是 [1, 2, 3, 5, 4, 6, 7]，适应性强的算法会利用这种已经部分排序的特性来减少工作量。

直接插入排序

直接插入排序是一种简单的排序算法，具有稳定性和适应性。

  1. 实现稳定性：

    • 在直接插入排序中，新元素总是插入到前面已排序部分的适当位置。
    • 当遇到相等的元素时，新元素会被放置在相等元素的后面，从而保持了它们的相对顺序。
    • 这种做法确保了具有相同值的元素在排序后仍然保持其原有的顺序，从而使算法是稳定的。

  2. 实现适应性：

    • 直接插入排序的性能会随输入数据的初始排序程度而改变。
    • 如果数据已经部分排序，算法会进行较少的比较和移动操作。例如，在最佳情况下（输入数据已经完全排序），直接插入排序只需要进行 (n-1) 次比较和0次移动操作。
    • 这种对输入数据的初始排序状态敏感的特性使得直接插入排序具有适应性。

总结来说，直接插入排序因其能保持相等元素的原始顺序而具有稳定性，且能根据输入数据的部分排序状态调整其性能，从而具有适应性。这两个特性使得直接插入排序在某些情况下（如已部分排序的小数据集）非常有效。

十一、(10分)给定一个有16个关键码的字典.
(1)(5分) 使用二分查找搜索一个关键码时的比较次数.
(2)(5分) 用除余法定义散列函数并设置 M=31M =31, 用开放地址线性探查法建立散列表.

Solution: (1) 二分查找是一种在有序数组中查找特定元素的算法。针对16个元素的数组，最坏情况下的比较次数是确定的。在二分查找中，每次比较都会将搜索区间减半。因此，对于含有16个元素的数组，最多需要进行的比较次数可以通过计算 ( \log_2(16) ) 得出，等于4

(2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random

# 散列函数和散列表大小
M = 31
hash_table = [None] * M

# 除余法定义的散列函数
def hash_function(key):
    return key % M

# 开放地址线性探查法
def linear_probing(hash_table, key):
    index = hash_function(key)
    initial_index = index
    while hash_table[index] is not None:
        index = (index + 1) % M
        if index == initial_index:  # 避免无限循环
            raise Exception("散列表已满")
    hash_table[index] = key

# 随机生成16个关键码
keys = [random.randint(1, 100) for _ in range(16)]

# 构建散列表
for key in keys:
    linear_probing(hash_table, key)

print("散列表:", hash_table)
print("关键码:", keys)

输出结果

1
2
散列表: [62, 31, 95, None, 97, 98, None, None, 39, 40, None, 73, 12, None, None, None, None, None, 80, 19, 20, 82, None, None, None, None, 57, None, None, 29, 60]
关键码: [19, 98, 95, 29, 62, 20, 39, 57, 40, 97, 12, 60, 82, 73, 80, 31]

十二、(10分) 树的先根遍历的递归和非递归.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorder_traversal_recursive(root):
    if root:
        print(root.value)  # 访问根节点
        preorder_traversal_recursive(root.left)  # 遍历左子树
        preorder_traversal_recursive(root.right)  # 遍历右子树

def preorder_traversal_iterative(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.value)  # 访问节点

        # 首先压入右子树，然后是左子树
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

十三、(10分) 求整数列中最大连续子序列和.

Solution: 求解整数序列中最大连续子序列和的一个经典算法是Kadane算法。这个算法非常高效，能在线性时间内解决问题。

算法的基本思想是遍历数组，同时跟踪两个变量：当前位置的最大子序列和和到目前为止的最大子序列和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def max_subarray_sum(nums):
    """
    计算给定整数数组的最大连续子序列和。
    """
    if len(nums) == 0:
        return 0

    max_current = max_global = nums[0]

    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)

    return max_global

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("最大连续子序列和:", max_subarray_sum(nums))

输出样例结果

1
最大连续子序列和: 6