第 1 / 2 页
非代码面试题
显示 20 / 23 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
526完全图 K₅ 上的击中时间随机游走在完全图 K 5（5 个顶点，每对之间有边）上进行。每步等概率移动到 4 个邻居之一。从顶点 u 出发，求首次到达指定顶点 v u 的期望步数。概率简单数值题未尝试免费527环图上到对径顶点的击中时间简单随机游走在环图 C 8（顶点 0,1,\ldots,7 排成圆环）上进行。每步以概率 1/2 顺时针或逆时针移动。从顶点 0 出发，求首次到达对径顶点 4 的期望步数。概率简单数值题未尝试免费528三维超立方体上的击中时间随机游走在三维超立方体 Q 3 上进行：8 个顶点为长度 3 的二进制串，两顶点相邻当且仅当恰好一个坐标不同。每步等概率选一个坐标翻转。从 000 出发，求首次到达 111 的期望步数。概率中等数值题未尝试免费529完全二部图 K₃,₃ 上的击中时间考虑完全二部图 K 3,3 ，两部分为 A=\ a 1,a 2,a 3\ 和 B=\ b 1,b 2,b 3\ ，A 中每个顶点与 B 中每个顶点相连。随机游走每步以概率 1/3 移动到 3 个邻居之一。从 a 1 出发，求首次到达 b 1 的期望步数。概率中等数值题未尝试免费530超立方体 Q₃ 的等效电阻与通勤时间三维超立方体 Q 3（顶点为长度 3 二进制串，边连一位不同的串），每边电阻为 1。 (a) 利用 Q 3 的对称性，计算 000 与 111 之间的等效电阻 R eff (000,111)。 (b) 随机游走的通勤时间满足 C(u,v)=2m R eff (u,v)，其中 m 为边数。求 000 到 111 的通勤时间。概率困难derivation未尝试面试订阅531路径图 P₃ 的覆盖时间随机游走在路径图 P 3（顶点 \ 1,2,3\ ，边 \ 1 - 2, 2 - 3\ ）上。从顶点 1 出发，求访问所有三个顶点的期望步数（覆盖时间）。概率简单数值题未尝试免费532Petersen 图上的击中时间Petersen 图有 10 个顶点、15 条边，是 3-正则且距离传递的，直径为 2。每步等概率移向 3 个邻居之一。从顶点 u 出发，求首次到达与 u 不相邻的指定顶点 v 的期望步数。概率中等数值题未尝试免费533环图上惰性游走的谱雙与混合时间环图 C n 上的惰性随机游走：每步以 1/2 概率停留，各以 1/4 概率移向两个邻居。转移矩阵特征值为 \lambda k= 1 2 (1+\cos(2 k/n))。 (a) 求谱雙 =1-\lambda 1。 (b) 利用 t mix \asymp 1/ 确定 n 时混合时间的阶。概率中等derivation未尝试免费534完全三叉树上从叶到根的击中时间完全三叉树深度为 2：根有 3 个子节点，每个子节点有 3 个叶子，共 13 个顶点。简单随机游走每步等概率移向一个邻居。从一个叶子出发，求首次到达根的期望步数。概率中等数值题未尝试免费535K₂,₃ 上的等效电阻与通勤时间完全二部图 K 2,3 ，部分 A=\ a 1,a 2\ （度 3）和 B=\ b 1,b 2,b 3\ （度 2），每边电阻为 1。 (a) 计算 R eff (a 1,a 2)。 (b) 用 C(u,v)=2m R eff (u,v) 求通勤时间。 (c) 用首步分析计算 h(a 1 a 2) 并验证。概率困难derivation未尝试面试订阅536完全图 K₄ 上的期望回返时间简单随机游走在完全图 K 4 上。每步等概率移向 3 个邻居之一。从顶点 v 出发，求首次返回 v 的期望步数。概率简单数值题未尝试免费537星图 S₅ 上叶之间的击中时间星图 S 5 有中心顶点 c 连接 4 个叶顶点。从叶 \ell 1 出发，求首次到达叶 \ell 2 的期望步数。概率简单数值题未尝试免费539完全图 K₄ 的覆盖时间随机游走在 K 4 上。(a) 求最大击中时间。(b) 用 Matthews 定理给出覆盖时间的界。(c) 精确计算覆盖时间。概率困难derivation未尝试面试订阅5404-环图上的等效电阻与通勤时间环图 C 4，顶点 \ 0,1,2,3\ ，每边电阻为 1。(a) 计算 R eff (0,2)。(b) 求通勤时间。(c) 求 h(0 2) 并验证。概率困难derivation未尝试面试订阅541小图上的平稳分布与回返时间图 G 有四个顶点 \ A,B,C,D\ ，边为 \ A - B, A - C, A - D, B - C\ ，度序列为 (3,2,2,1)。(a) 求平稳分布。(b) 求每个顶点的期望回返时间。概率简单数值题未尝试免费542轮图 W₆ 上的击中时间轮图 W 6 由中心顶点 h 连接 C 5 的 5 个顶点组成。从边缘顶点出发，求首次到达 hub 的期望步数。概率中等数值题未尝试免费543梯子图（2×3 网格）上的击中时间2 3 网格图，顶点排列为两行三列。从角顶点 1（度 2）出发，求首次到达对角顶点 6（度 2）的期望步数。概率中等数值题未尝试免费544菱形图上的击中时间取 K 4 删除边 A - D 得到“菱形图”，5 条边。(a) 求 h(A D)。(b) 求 h(D A)。(c) 计算通勤时间并用等效电阻验证。概率困难数值题未尝试面试订阅545Kₙ 上惰性随机游走的混合时间K n 上的惰性随机游走。(a) 证明转移矩阵有两个不同特征值。(b) 求谱雙并确定混合时间的阶。概率困难derivation未尝试面试订阅546路径图 P₅ 上的击中时间路径图 P 5 上的简单随机游走，顶点 \ 0,1,2,3,4\ 。端点确定性移向唯一邻居，内部顶点等概率左右移动。从 0 出发，求首次到达 4 的期望步数。概率简单数值题未尝试免费