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

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

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

三、(15分) 设 $X_1,\cdots, X_N$ 独立同分布于 $U(0,1)$, $X_{(r)}$ 是对应的次序统计量 $(1\leq r\leq N)$. 若 $k$ 为已知常数, 且 $1\leq r_1< r_2< \cdots < r_n\leq N$, 这 $n$ 个下标也已知. 求 $E\left(\prod_{i=1}^nX_{(r_i)}^k \right)$.

四、(15分) 若 $X_{1},X_{2},\dots,X_{n}$ 取自总体 $N(\theta,\sigma_1^2)$, $Y_{1},Y_{2},\dots,Y_{m}$ 取自总体 $N(\theta,\sigma_2^2)$, 其中 $\sigma_1,\sigma_2$ 已知.
(1)(7分) 设 $T=c \bar{X}+d \bar{Y}$ 是 $\theta$ 的无偏估计，求 $c,d$ 的值使得 $T$ 的方差最小.
(2)(8分)基于第一问求出的 $T$, 给出 $\theta$ 的 $1-\alpha$ 置信区间.

五、(15分)设回归模型为 $Y_{i}=\alpha+\beta x_{i}+\epsilon_{i}$, 其中 $\epsilon_{i}\overset{i.i.d.}{\sim} N(0,\sigma^2)$，且 $\sigma$ 已知. 现在将模型修改为 $Y_{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'}$ 独立.

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

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

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

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

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

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

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

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