我国科学院大学历年计算机算法作业和历年习题集.pdf

中 国 科 学 院 大 学 历 年 习 题 习 题 一 复 杂 性 分 析 初 步 1.试 确 定 下 述 程 序 的 执 行 步 数，该 函 数 实 现 一 个 m X n 矩 阵 与 一 个 nX p 矩 阵 之 间 的 乘 法：矩 阵 乘 法 运 算 templatevoid Mult（T*a,T*b,int m,int n,int p）/m X n 矩 阵 a 与 n X p 矩 阵 b 相 成 得 到 m X p 矩 阵 cfor（int i=0；im；i+）for（int j=0；jp；j+）T sum=0；for（int k=0；kn；k+）Sum+=aik*bk j；Ci j=sum；)语 句 s/e 频 率 总 步 数 templatevoid Mult(T*a,T*b,int m,int n,int p)(0 0 0for(int i=0;im;i+)1 m+1 m+lfor(intj=O;jp;j+)1 m*(p+l)m*p+mT sum=0;1 m*p m*pfor(int k=0;kn;k+)1 m*p*(n+l)m*p*n+m*pSum+=aik*bkj;1 m*p*n m*p*nCij=sum;)1 m*p m*p)总 计 2*m*p*n+4*m*p+2*m+l其 中 s/e表 示 每 次 执 行 该 语 句 所 要 执 行 的 程 序 步 数。频 率 是 指 该 语 句 总 的 执 行 次 数。2.函 数 MinMax用 来 查 找 数 组 aO：nT中 的 最 大 元 素 和 最 小 元 素，以 下 给 出 两 个 程 序。令 n 为 实 例 特 征。试 问：在 各 个 程 序 中，a 中 元 素 之 间 的 比 拟 次 数 在 最 坏 情 况 下 各 是 多 少？找 最 大 最 小 元 素 方 法 一 templatebool MinMax(T a,int n,int&Min,int&Max)/寻 找 a0：n-l中 的 最 小 元 素 与 最 大 元 素 如 果 数 组 中 的 元 素 数 目 小 于 1,那 么 还 回 falseif(nl)return false；Min=Max=0；初 始 化 for(int i=l；iai)Min=i；if(aMaxai)Max=i；return true；最 好，最 坏，平 均 比 拟 次 数 都 是 2*n-1_找 最 大 最 小 元 素 方 法 二 templatebool MinMax(T a,int n,int&Min,int&Max)/寻 找 a0：n-l中 的 最 小 元 素 与 最 大 元 素 如 果 数 组 中 的 元 素 数 目 小 于 1,那 么 还 回 falseif(nl)return false；Min=Max=0；初 始 化 for(int i=l；iai)Min=i；else if(aMax005.下 面 那 些 规 那 么 是 正 确 的？为 什 么？1)./()=O(%),g()=O(G()n/5)/g()=O(W)/G()；错 2)./()=0(/()，8()=。(6()=/()/8()=。(/()/6()；错 3)./(n)=O(F(n),gri)=O(G(n)/()/g(n)=0(F(n)/G(n);错 4)./(”)=Q(F(),g()=C(G()n/()/g()=Q(b()/G()；错 5)./()=C(F(),g()=Q(G()n/()/g()=O(F(”)/G()。错 6)./()=0(F(n),g()=(G()n/()/g()=()/G()对 6.按 照 渐 进 阶 从 低 到 高 的 顺 序 排 列 以 下 表 达 式：顺 序：log n”20/1 4几 2 3 n7.1)假 设 某 算 法 在 输 入 规 模 是 时 为 T()=3*2.在 某 台 计 算 机 上 实 现 并 完 成 该 算 法 的 时 间 是 f秒.现 有 另 一 台 计 算 机，其 运 行 速 度 为 第 一 台 的 6 4 倍,那 么，在 这 台 计 算 机 上 用 同 一 算 法 在 f秒 内 能 解 决 规 模 为 多 大 的 问 题？关 系 式 为 时 间 复 杂 度 计 算 步 数*运 行 速 度(时 间/每 步)=运 行 所 需 时 间，即 规 模 时 间 复 杂 度 步 数 原 运 行 速 度 时 间/每 步 总 时 间 nT(”)=3*2t解：设 在 新 机 器 上 f秒 内 能 解 决 规 模 为 机 的 问 题，时 间 复 杂 度 变 为 7(=3*2，由 于 新 机 器 运 行 速 度 提 高 64倍，那 么 运 行 速 度 变 为 褊=*,由 关 系 式 T()*fo=f,0)*3=/,得 3*2n*t0=t,解 得 2)假 设 上 述 算 法 改 良 后，新 算 法 的 计 算 复 杂 度 为 T()=2,那 么 在 新 机 器 上 用 f秒 时 间 能 解 决 输 入 规 模 为 多 大 的 问 题？设 在 新 机 器 上 用 f秒 时 间 能 解 决 输 入 规 模 为 N 的 问 题，那 么 由 于 新 复 杂 度 TN)=N 新 机 器 的 运 行 速 度 为,新=2，64代 入 关 系 式 0(N)*、=f,得 N2*_L=f=3*2*玲 64解 得 3 假 设 进 一 步 改 良 算 法，最 新 的 算 法 的 时 间 复 杂 度 为 T()=8,其 余 条 件 不 变，在 新 机 器 上 运 行，在 f秒 内 能 够 解 决 输 入 规 模 为 多 大 的 问 题？设 可 解 决 的 最 大 时 间 复 杂 度 为 Ma、，那 么 可 解 决 的 最 大 时 间 复 杂 度 为(nax=192*2(n为 原 始 的 输 入 规 模。因 为 丁()=8/稣，且 T()为 常 数 不 随 输 入 规 模 n 变 化，所 以 任 意 规 模 的 n 都 可 在 t秒 内 解 决。8.Fibonacci数 有 递 推 关 系：试 求 出 Fri)的 表 达 式。解：方 法 一：当 1时，由 递 推 公 式 F(n)=F(n-1)+F(H-2)得 特 征 方 程 为 解 得 1+V5 1-V5x 二 2，=2那 么 可 设 由 F(2)=2,F(3)=3,解 得 G=1萼，c2=-24 5故 F(n)=2(当 1)向(上 汽 产 刀,当=0,1时，带 入 验 证 亦 成 立。故 F(n)=-(-2)-(1.)-方 法 二：也 可 直 接 推 导 可 得 可 得 a 1+V5a，B=2，设 b”=aH-a an_x,那 么 么 为 等 比 数 列，先 求 出 加 然 后 代 入 即 可 求 得 明。第 二 章 局 部 习 题 参 考 答 案 L 证 明 以 下 结 论：1 在 一 个 无 向 图 中，如 果 每 个 顶 点 的 度 大 于 等 于 2,那 么 该 该 图 一 定 含 有 圈；2 在 一 个 有 向 图 D 中，如 果 每 个 顶 点 的 出 度 都 大 于 等 于 1,那 么 该 图 一 定 含 有 一 个 有 向 圈。1 证 明：设 无 向 图 最 长 的 迹 尸=匕 匕 九,每 个 顶 点 度 大 于 等 于 2,故 存 在 与 匕 相 异 的 点 V与 匕 相 邻，假 设 VP,那 么 得 到 比 P 更 长 的 迹，与 P 的 取 法 矛 盾。因 此，VeP,是 闭 迹，从 而 存 在 圈 X M V%.证 明*:设 在 无 向 图 G 中，有 n 个 顶 点，m 条 边。由 题 意 知，m=(2n)/2=n,而 一 个 含 有 n 个 顶 点 的 树 有 n-1条 边。因 m=nn-l,故 该 图 一 定 含 有 圈。定 义：迹 是 指 边 不 重 复 的 途 径，而 顶 点 不 重 复 的 途 径 称 为 路。起 点 和 终 点 重 合 的 途 径 称 为 闭 途 径，起 点 和 终 点 重 合 的 迹 称 为 闭 迹，顶 点 不 重 复 的 闭 迹 称 为 圈。2 证 明：设 有 向 图 最 长 的 有 向 迹 P=匕，每 个 顶 点 出 度 大 于 等 于 1,故 存 在 修 为 片 的 出 度 连 接 点，使 得 匕 丫，成 为 一 条 有 向 边,假 设 VWP,那 么 得 到 比 P更 长 的 有 向 迹，与 P 矛 盾，因 此 必 有 VeP,从 而 该 图 一 定 含 有 有 向 圈。2.设 D 是 至 少 有 三 个 顶 点 的 连 通 有 向 图。如 果 D 中 包 含 有 向 的 Euler环 游 即 是 通 过 D 中 每 条 有 向 边 恰 好 一 次 的 闭 迹，那 么 D 中 每 一 顶 点 的 出 度 和 入 度 相 等。反 之，如 果 D 中 每 一 顶 点 的 出 度 与 入 度 都 相 等，那 么 D 一 定 包 含 有 向 的 Euler环 游。这 两 个 结 论 是 正 确 的 吗？请 说 明 理 由。如 果 G 是 至 少 有 三 个 顶 点 的 无 向 图，那 么 G 包 含 Euler环 游 的 条 件 是 什 么？证 明：1 假 设 图 D 中 包 含 有 向 Euler环 游，下 证 明 每 个 顶 点 的 入 度 和 出 度 相 等。如 果 该 有 向 图 含 有 Euler环 游，那 么 该 环 游 必 经 过 每 个 顶 点 至 少 一 次，每 经 过 一 次，必 为“进 一 次 接 着“出 一 次，从 而 入 度 等 于 出 度。从 而，对 于 任 意 顶 点，不 管 该 环 游 经 过 该 顶 点 多 少 次，必 有 入 度 等 于 出 度。2 假 设 图 D 中 每 个 顶 点 的 入 度 和 出 度 相 等，那 么 该 图 D 包 含 Euler环 游。证 明 如 下。对 顶 点 个 数 进 展 归 纳当 顶 点 数 N(D)1=2时,因 为 每 个 点 的 入 度 和 出 度 相 等，易 得 构 成 有 向 Euler环 游。假 设 顶 点 数|v(D)|=k时 结 论 成 立，那 么 当 顶 点 数|v(D)|=k+1时，任 取 丫 丫(口).设 5=以 v 为 终 点 的 边,K=以 v 为 始 点 的 边,因 为 v 的 入 度 和 出 度 相 等，故 S 和 K 中 边 数 相 等。记 6=口-丫.对 G 做 如 下 操 作：任 取 S 和 K 中 各 一 条 边 勺、%,设 在 D 中 勺=叩，e2=vv2,那 么 对 G 和 S做 如 下 操 作 G=G+V,V2)S=S-g,重 复 此 步 骤 直 到 S 为 空。这 个 过 程 最 终 得 到 的 G 有 k 个 顶 点，且 每 个 顶 点 的 度 与 在 G 中 完 全 一 样。由 归 纳 假 设，G 中 存 在 有 向 Euler环 游，设 为 C。在 G 中 从 任 一 点 出 发 沿 C 的 对 应 边 前 行，每 当 遇 到 上 述 添 加 边 vlv2时，都 用 对 应 的 两 条 边 el,e2代 替，这 样 可 以 获 得 有 向 Euler环 游。3 G 是 至 少 有 三 个 顶 点 的 无 向 图，那 么 G 包 含 Euler环 游 等 价 于 G 中 无 奇 度 顶 点。即 任 意 顶 点 的 度 为 偶 数。3.设 G 是 具 有 n 个 顶 点 和 m 条 边 的 无 向 图,如 果 G 是 连 通 的，而 且 满 足 m=n-l,证 明 G 是 树。证 明：思 路 一：只 需 证 明 G 中 无 圈。假 设 G 中 有 圈，那 么 删 去 圈 上 任 一 条 边 G仍 连 通。而 每 个 连 通 图 边 数 e=n(顶 点 数)-1,但 删 去 一 条 边 后 G 中 只 有 n-2条 边，此 时 不 连 通，从 而 矛 盾，故 G 中 无 圈，所 以 G为 树。思 路 二：当“=2 时，m=2 1=1,两 个 顶 点 一 条 边 且 连 通 无 环 路，显 然 是 树。设 当=后 一 1伏 6,左 2 2)时，命 题 成 立，那 么 当“=女 时，因 为 G 连 通 且 无 环 路，所 以 至 少 存 在 一 个 顶 点 匕，他 的 度 数 为 1,设 该 顶 点 所 关 联 的 边 为，=(匕,匕).那 么 去 掉 顶 点 匕 和“，便 得 到 了 一 个 有 k-1个 顶 点 的 连 通 无 向 无 环 路 的 子 图 G,且 G 的 边 数 机=1,顶 点 数=-1。由 于 m二 nT,所 以 加=(-1)-1=-1,由 归 纳 假 设 知，G 是 树。由 于 G 相 当 于 在 G中 为 V2添 加 了 一 个 子 节 点，所 以 G 也 是 树。由 1，2 原 命 题 得 证。4.假 设 用 一 个 x 的 数 组 来 描 述 一 个 有 向 图 的 X”邻 接 矩 阵,完 成 下 面 工 作：1 编 写 一 个 函 数 以 确 定 顶 点 的 出 度，函 数 的 复 杂 性 应 为。()；：2 编 写 一 个 函 数 以 确 定 图 中 边 的 数 目，函 数 的 复 杂 性 应 为。(2)；3 编 写 一 个 函 数 删 除 边(i),并 确 定 代 码 的 复 杂 性。解 答：1 邻 接 矩 阵 表 示 为%X,待 确 定 的 顶 点 为 第 m 个 顶 点 小 int CountVout(int*a,int n,int m)int out=0；for(int i=0；in；i+)if(am-li=l)out+；return out；)2 确 定 图 中 边 的 数 目 的 函 数 如 下：int EdgeNumber(int*a,int n)int num=0；for(int i=0；in；i+)for(int j=0；jn；j+)if(aij=l)num+；return num；3 删 除 边 i,j 的 函 数 如 下:void deleteEdge(int*a,int i,int j)if(ai-lLj-l=O)return；=0；return；代 码 的 时 间 复 杂 性 为(1)5.实 现 图 的 D-搜 索 算 法，要 求 用 SPARKS语 言 写 出 算 法 的 伪 代 码，或 者 用 一 种 计 算 机 高 级 语 言 写 出 程 序。解:D 搜 索 算 法 的 根 本 思 想 是，用 栈 代 替 BFS中 的 队 列，先 将 起 始 顶 点 存 入 栈 中，搜 索 时,取 出 栈 顶 的 元 素，遍 历 搜 索 其 相 邻 接 点，假 设 其 邻 接 点 还 未 搜 索，那 么 存 入 栈 中 并 标 记,遍 历 所 有 邻 接 点 后，取 出 此 时 栈 顶 的 元 素 转 入 下 一 轮 遍 历 搜 索，直 至 栈 变 为 空 栈。Proc DBFS(v)从 顶 点 v 开 场，数 组 visited标 示 顶 点 被 访 问 的 顺 序；PushS(v,S)；/首 先 访 问 V,将 S 初 始 化 为 只 含 有 一 个 元 素 v 的 栈 count：=count+1；visitedv：=count；While S 非 空 dou：=PullHead(S)；count：=count+l；visitedw：=count；区 另 U 队 站;三 进 七 此 先 进 后 出 for邻 接 于 u 的 所 有 顶 点 w doif sw=0 thenPushS(w,S)；/将 w 存 入 栈 Ssw：=1；endifend(forendwhile)endDBFS注：PushS(w,S)将 w 存 入 栈 S；PullHead(S)为 取 出 栈 最 上 面 的 元 素，并 从 栈 中 删 除 Proc DBFT(G,m)为 不 连 通 分 支 数 count：=0；计 数 器，标 示 已 经 被 访 问 的 顶 点 个 数 for i to n dosi：=0；/数 组 s 用 来 标 示 各 顶 点 是 否 曾 被 搜 索，是 那 么 标 记 为 1,否 那 么 标 记 为 0；endfor)for i to m do 遍 历 不 连 通 分 支 的 情 况 if si=0 thenDBFS(i)；endifendforendDBET)6.下 面 的 无 向 图 以 邻 接 链 表 存 储，而 且 在 关 于 每 个 顶 点 的 链 表 中 与 该 顶 点 相 邻 的 顶 点 是 按 照 字 母 顺 序 排 列 的。试 以 此 图 为 例 描 述 讲 义 中 算 法 DFNL的 执 行 过 程。邻 接 链 表 A-B-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0解：初 始 化 数 组 DFN：=0,num=l;A 为 树 的 根 节 点,对 A 计 算 DFNL(A,null),DFN(A):=num=l；L(A):=num=l；num：=l+l=20从 邻 接 链 表 查 到 A 的 邻 接 点 B,因 为 DFN(B)=0,对 B 计 算 DFNL(B,A)DFN(B):=num=2；L(B):=num=2；num:=2+1=3。查 邻 接 链 表 得 到 B 的 邻 接 点 A,因 为 DFN(A)=1M,但 A=A,即 是 B 的 父 节 点，无 操 作。接 着 查 找 邻 接 链 表 得 到 B 的 邻 接 点 C,因 为 DFN(0=0,对 C 计 算 DFNL(C,B)DFN(C):=num=3；L(C):=num=3；num：=3+1=4。查 找 C 的 邻 接 点 B,因 为 DFN(B)=1M,但 8=13,即 是 C 的 父 节 点，无 操 作。接 着 查 找 邻 接 链 表 得 到 C 的 邻 接 点 D,因 为 DFN(D)=0,对 D 计 算 DFNL(D,C),DFN(D):=num=4；L(D):=num=4；num：=4+1=5。查 找 得 D 邻 接 点 C,而 DFN(C)=3力 0,但 C=C,为 D 的 父 节 点，L(D)保 持 不 变。D 的 邻 接 链 表 完 毕，DFNL(D,C)的 计 算 完 毕。返 回 到 D 的 父 节 点 C,查 找 邻 接 链 表 得 到 C 的 邻 接 点 E,因 为 DFN(E)=0,对 E 计 算 DFNL(E,C),DFN(E):=num=5；L(E):=num=5；num：5+1=6；查 找 得 E 邻 接 点 A,因 DFN(A)=1 片 0,又 A声 C,变 换 L(E)=min(L(E),DFN(A)=1。查 找 得 E 邻 接 点 C,因 DFN(C)=30,但 C=C,无 操 作。查 找 得 E 邻 接 点 F,因 DFN(F)=0,对 F 计 算 DFNL(F,E),DFN(F):=num=6；L(F):=num=6；num：=6+1=7；查 找 得 F 邻 接 点 E,因 DFN(E)=540,但=,无 操 作。查 找 得 F 邻 接 点 G,因 DFN(G)=0,对 G 计 算 DFNL(G.F),DFN(G):=num=7；L(G):=num=7；num=7+l=8;查 找 G 邻 接 点 E,因 DFN(E)=5R0,又 E-F,L(G)=min(L(G),DFN(E)=5查 找 得 G 邻 接 点 F,因 DFN(F)=6中 0,但 F=F,无 操 作。G 的 邻 接 链 表 完 毕，DFNL(G,F)的 计 算 完 毕。L(F):=min(L(F),L(G)=min(6,5)=5F的 邻 接 链 表 完 毕,D F N L(F,E)的 计 算 完 毕。L(E)：=min(L(E),L(F)=min(l,5)=1E 邻 接 链 表 完 毕，DENL(E,C)计 算 完 毕。L(C)：=min(L(C),L(E)=min(3,1)=1C 的 邻 接 链 表 完 毕，DFNL(C,B)计 算 完 毕。L(B)：=min(L(B),L(C)=min(2,1)=1查 找 B 的 邻 接 链 表 完 毕，DFNL(B,A)计 算 完 毕。L(A)：=min(L(A),L(B)=1查 找 得 A 的 邻 接 点 E,因 DFN(E)=0,又 E于 null,那 么 L(A)=min(L(A),DFN(E)=l查 找 A 的 邻 接 链 表 完 毕，DFNL(A,nul 1)计 算 完 毕。最 终 结 果 为：深 索 数 DFN,与 最 低 深 索 数 L 如 下 DFN(A)=1,DFN(B)=2,DFN(C)=3,DFN(D)=4,DFN(E)=5,DFN(F)=6,DFN(G)=7L(A)=1；L(B)=1；L(C)=1；L(D)=4；L(E)=1；L(F)=5；L(G)=5.序-M-点 DFN L 栈 顶 一 栈 底 2-连 通 割 点 1 A 1(1,0,0,0,0,0,0)(A,B)2 B 2(1,2,0,0,0,0,0)(B,C),(A,B)3 C 3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)4 D 4(1,2,3,4,0,0,0)(B,C),(A,B)(C,D)；c5 E 5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)6 F 6(1,1,1,4,1,6,0)(F,G),(E,F),(E,A),(B,C),(A,B)7 G 7(1,1,1,4,1,5,5)(E,A),(B,C),(A.B)(G,E),(F,G),(E,F)E8(1,1,1,4,1,5,5)(E,A),(B,C),(A,B)附 课 本 讲 义 程 序 2-3-1对 图 2-3-5的 执 行 过 程 开 场 DFNL(A,*)DFN(A)：=1；L(A)：=1；num：=2；DFN(B)=0,.-.DFNL(B,A)DFN(B)：=2；L(B)：=2；num：=3；,DFN(A)=l*0,但 人=人，不 做 任 何 事 情 DFN(C)=0,.-.DFNL(C,B)DFN(C)：=3；L(C)：=3；num：=4；1 DFN(B)=2M,但 8=8,，不 做 任 何 事 情 DFN(D)=0,.-.DFNL(D,C)DFN(D)：=4；L(D)：=4 DFN(C)；num：=5；DFN(C)=3M,但 C=C,.不 做 任 何 事 情 DFN(E)=O,.DFNL(E.C)DFN(E)：=5；L(E)：=5 DFN(C)；num：=6；DFN(C)=30,但 C=C,DFN(F)=0,.,.DFNL(F,C)DFN(F)：=6；L(F)：=6；num：=7；DFN(A)=1M,A M,L(F)：=min6,1=1；DFN(C)=3M,但 C=C,DFN(G)=O,.,.DFNL(G,F)DFN(G)：=7；L(G)：=7；num：=8；DFN(F)=6wO,但 尸=尸，/DFN(H)=O,.,.DFNL(H,G)DFN(H)：=8；L(H)：=8 DFN(G)；num：=9；弹 出 G,H 边 DFN(G)=7M,但 6=6,DFN(I)=O,.-.DFNLd.G)DFN(I)：=9；L(I)：=9；num：=10；DFN(F)=6却,FHG,L(I)：=min9,6=6；DFN(G)=7wO,但 16,DFN(J)=O,.-.DFNLU,I)DFN(J)：=10；L(J)：=10；num：=ll；DFN(F)=6M,FH I,L(J)：=min10,6=6；DFN(G)=7M,GwI,/.L(J)：=min6,7=6；DFN=9*0,但 1=1,L(I)：=min6,6=6；L(G)：=min7,6=6DFN(F)弹 出(J,G),(J,F),(I,J),(I,F),(G.I),(F,G)边 L(F)：=minl,6=1；L(C)：=min3,1=1；L(B)：=min2,1=1 DFN(A)弹 出(F,A),(C,F),(B,C),(A,B)边 7 对 图 的 另 一 种 检 索 方 法 是 D-Search。该 方 法 与 BFS的 不 同 之 处 在 于 将 队 列 换 成 栈，即 下 一 个 要 检 测 的 结 点 是 最 新 加 到 未 检 测 结 点 表 的 那 个 结 点。1 写 一 个 D-Search算 法;2 证 明 由 结 点 v 开 场 的 D-Search能 够 访 问 v 可 到 达 的 所 有 结 点；3 你 的 算 法 的 时、空 复 杂 度 是 什 么？解：1 同 第 5题，proc DBFS(v)宽 度 优 先 搜 索 G,从 顶 点 v 开 场 执 行，数 组 visited标 示 各 顶 点 被 访 问 的 序 数；数 组 s 将 用 来 标 示 各 顶 点 是 否 曾 被 放 进 待 检 查 队 列，是 那 么 过 标 记 为 1,否 那 么 标 记 为 0；计 数 器 count计 数 到 目 前 为 止 已 经 被 访 问 的 顶 点 个 数，其 初 始 化 为 在 V 之 前 已 经 被 访 问 的 顶 点 个 数 PushS(v,S)；/将 S 初 始 化 为 只 含 有 一 个 元 素 v 的 栈 while S 非 空 dou：=PullHead(S)；count*=count+l；visitedu*=count；for邻 接 于 u 的 所 有 顶 点 w doif sw=0 thenPushS(w,S)；将 w 压 入 栈 中 sw：=1；endifendfor)end(while)endDBFS图 的 D-搜 索 算 法 伪 代 码：proc DBFT(G,v)/county s 同 DBFS中 的 说 明，branch是 统 计 图 G 的 连 通 分 支 数 count:=0；branch*=0；for i to n dosi：=0；将 所 有 的 顶 点 标 记 为 未 被 访 问 endfor)for i to v doif si=0 thenDBFS(i)；branch=branch+l；endif)endfor)endDBFT)2证 明：除 结 点 v 外，只 有 当 结 点 w 满 足 sw=0时 才 被 压 人 栈 中，因 此 每 个 结 点 至 多 有 一 次 被 压 人 栈 中，搜 索 不 会 出 现 重 叠 和 死 循 环 现 象，对 于 每 一 个 V 可 到 达 的 节 点，要 么 直 接 被 访 问，要 么 被 压 入 栈 中，只 有 栈 内 节 点 全 部 弹 出 被 访 问 后，搜 索 才 会 完 毕，所 以 由 结 点 V开 场 的 D-Search能 够 访 问 v 可 到 达 的 所 有 结 点。3：除 结 点 v 外，只 有 当 结 点 w 满 足 sw=0时 才 被 压 入 栈 中，因 此 每 个 结 点 至 多 有 一 次 被 压 人 栈 中。需 要 的 栈 空 间 至 多 是；visited数 组 变 量 所 需 要 的 空 间 为 v;其 余 变 量 所用 的 空 间 为 0(1),所 以 S(T,)=(V)如 果 使 用 邻 接 链 表，for循 环 要 做 d(u)次，而 while循 环 需 要 做 v 次，又 visited、s 和 count的 赋 值 都 需 要 T 次 操 作，因 而 t(v,E)=&(v+)0如 果 采 用 邻 接 矩 阵，那 么 while循 环 总 共 需 要 做/次 操 作，visited、s 和 count的 赋 值 都 需 要 v 次 操 作，因 而 t(v,)=(小)。8.考 虑 下 面 这 棵 假 想 的 对 策 树：解：1)使 用 最 大 最 小 方 法(2-4-2)式 获 取 各 结 点 的 值 S0 Smaxminmaxminmax 22)弈 者 A为 获 胜 应 该 什 么 棋 着?第 三 章 分 治 算 法 习 题 1、编 写 程 序 实 现 归 并 算 法 和 快 速 排 序 算 法 参 见 后 附 程 序 2、用 长 为 100、200、300、400、500、600、700、800、900、1000 的 10 个 数 组 的 排 列 来 统 计 这 两 种 算 法 的 时 间 复 杂 性。有 些 同 学 用 的 微 秒 us用 s 可 能 需 要 把 上 面 的 长 度 改 为 10000,，100000,都 可 以 大 局 部 的 结 果 是 快 速 排 序 算 法 要 比 归 并 算 法 快 一 些。3、讨 论 归 并 排 序 算 法 的 空 间 复 杂 性。解 析：归 并 排 序 由 分 解 与 合 并 两 局 部 组 成，如 果 用 5(n)表 示 归 并 排 序 所 用 的 空 间。那 么 由 MergeSort(low,mid)将 第 一 子 数 组 排 序 S(/2)MergeSort(mid+1,high)将 第 二 子 数 组 排 序 S(n/2)Merge(low,mid,high)/归 并 两 个 已 经 排 序 的 子 数 组 O()a 2”那 么 递 归 推 导 得 又 由 存 储 数 组 长 度 为，那 么 有 S()O(n)因 此，空 间 复 杂 度 为 0()。4、说 明 算 法 PartSelect的 时 间 复 杂 性 为 0(”)证 明：提 示：假 定 数 组 中 的 元 素 各 不 一 样，且 第 一 次 划 分 时 划 分 元 素 u是 第 i小 元 素 的 概 率 为 1/。因 为 Partition中 的 case语 句 所 要 求 的 时 间 都 是。(“)，所 以，存 在 常 数 c,使 得 算 法 PartSelect的 平 均 时 间 复 杂 度()可 以 表 示 为 令 R()=max(C*(n),Jfe C R,试 证 明 R(n)4cn。证 明：令 C：()表 示 n 个 元 素 的 数 组 A 中 寻 找 第 k 小 元 素 的 平 均 时 间 复 杂 度，因 Partition(0,n-1)的 时 间 复 杂 度 是 0(“)，故 存 在 常 数 c,使 得 算 法 PartSelect的 平 均 时 间 复 杂 度 C()可 以 表 示 为 0()W+L Z(n_0+0(/-1)ik kin令 R()=max(C：(),且 不 妨 设 等 式 在 k=kn时 成 立，那 么?()满 足 k以 下 用 第 二 数 学 归 纳 法 证 明 R()C/4,那 么 7?(1)4c当=2 时，7?(2)2c+-/?(l)2c+-4c=4c 成 立。2 2对 于 一 般 的 n,设 对 所 有 小 于 n 的 自 然 数 R()44c 成 立，那 么 得 证。证 明：1 当，=7 时，假 设 数 组 A 中 元 素 互 不 一 样。由 于 每 个 具 有 7 个 元 素 的 数 组 的 中 间 值 u 是 该 数 组 中 的 第 4 小 元 素，因 此 数 组 中 至 少 有 4 个 元 素 不 大 于 u,个 中 间 值 中 至 少 有/7/2 个 不 大 于 这 些 中 间 值 的 中 间 值 丫。因 此，在 数 组 A 中 至 少 有 个 元 素 不 大 于 V。换 句 话 说，A 中 至 多 有 5 12个 元 素 大 于 V。同 理，至 多 有 一+一 个 元 素 小 于 V。这 样，以 v 为 划 分 元 素，产 生 的 新 数 7 75 12 5 12 11组 至 多 有 一+一 个 元 素。当 2 24时，一+一 nQ7 7 7 7 14另 一 方 面，在 整 个 执 行 过 程 中，递 归 调 用 Select函 数 一 次，涉 及 规 模 为 力/7,而 下 一 次 循 环 Loop涉 及 的 数 组 规 模 为 U”。程 序 中 其 他 执 行 步 的 时 间 复 杂 度 至 多 是 n 的 倍 数 C77,用 14T(n)表 示 算 法 在 数 组 长 度 为 n 的 时 间 复 杂 度，那 么 当 2 24时，有 递 归 关 系 用 数 学 归 纳 法 可 以 证 明，T(H)1 4 CHO所 以 时 间 复 杂 度 是 0()。2 2 5 当 r=3时，使 用 上 述 方 法 进 展 分 析，可 知 在 进 展 划 分 后 数 组 A 中 有 至 多*+*士 3 3 6个 元 素。而 递 归 关 系 为 T(n)KTd)+T(3)+c。假 设 通 过 归 纳 法 证 明 出 有 3 6的 形 式，用 数 学 归 纳 法 可 以 证 明，T(n)28CHO所 以 时 间 复 杂 度 是 0()。归 并 排 序 的 C+语 言 描 述#includetemplatevoid MergeSort(T a,int left,int right)；templatevoid Merge(T c,T d,int 1,int m,int r)；templatevoid Copy(T a,T b,int 1,int r)；void main()(int const n(5)；int an；coutz，lnput，n，numbers please：；for(int i=0；in；i+)cinai；/for(int j=0；jn；j+)/bj=aj；MergeSort(a,0,n-1)；coutzzThe sorted array is，zendl；for(i=0；in；i+)coutai；coutendl；)templatevoid MergeSort(T a,int left,int right)/(if(leftright)int i=(left+right)/2；T*b=new T；MergeSort(a,left,i)；MergeSort(a,i+1,right)；Merge(a,b,left,i,right)；Copy(a,b,left,right)；)templatevoid Merge(T c,T d,int 1,int m,int r)int i=l；int j=m+l；int k=l；while(i=m)&(j=r)(if(cim)(for(int q=j；q=r；q+)dk+=cq；)elsefor(int q=i；q=m；q+)dk+=cq；)templatevoid Copy(T a,T b口，int 1,int r)(for(int i=l；i=r；i+)ai=bi；)快 速 排 序 的 C+语 言 描 述#includetemplatevoid Quicksort(T a,int p,int r)；templateint Partition(T a,int p,int r)；void main()(int const n(5)；int an；cout/zInput z，n，numbers please：；for(int i=0；i n；i+)cinai；Quicksort(a,0,n-l)；cout，The sorted array is Xendl；for(i=0；in；i+)coutai，z，z；coutendl；)templatevoid Quicksort(T a,int p,int r)(if(pr)int q=Partition(a,p,r)；Quicksort(a,p,q-1)；Quicksort(a,q+1,r)；)templateint Partition(T a,int p,int r)(int i=p,j=r+l；T x=ap；while(true)(while(a+ix)；if(i=j)break；Swap(ai,ajl)；)ap=aj；aj=x；return j；)templateinline void Swap(T&s,T&t)(T tempos；st；t=temp；)第 四 章 作 业 局