资源描述
1、 填 空 题1、 算 法 的 复 杂 性 是 算 法 效 率 2、 的 度 量 ， 是 评 价 算 法 优 劣 的 重 要 依 据 。1、 设 n为 正 整 数 ， 利 用 大 “ O( )” 记 号 ， 将 下 列 程 序 段 的 执 行 时 间 表 示 为 n的 函 数 ， 则 下 面 程 序 段 的 时 间 复 杂 度 为 O(n )2、 。 i=1; k=0;while(i du+wu,v 2.then dv=du+wu,v pv=u dijkstra(G,w,s) 1. init-single-source(G,s) 2. S= 3. Q=VG4.while Q do u=min(Q) S=S u for each vertex v adju /所 有 u的 邻 接 点 v do relax(G,v,w) 2、 某 工 厂 预 计 明 年 有 N个 新 建 项 目 ， 每 个 项 目 的 投 资 额 wk及 其 投资 后 的 收 益 vk已 知 。 投 资 总 额 为 C， 问 如 何 选 择 项 目 才 能 使 总 收 益 最 大 。Invest-Program( ) for (j=0;j=C;j+) （ 5） mnj=0; for (j=wn;j1;i-) int jMax=min(wi-1,c); for(j=0;j=jMax;j+) mij= （ 6） mi+1j ; for (j=wi;j=w1 ) m1c=max(m1c,m2c-w1+v1); 3、 N后 问 题(1)用 二 维 数 组 ANN存 储 皇 后 位 置 ,若 第 i行 第 j列 放 有 皇 后 ,则 Ai j为 非 0值 ,否 则 值 为 0。(2)分 别 用 一 维 数 组 MN、 L2*N-1、 R2*N-1表 示 竖 列 、 左 斜 线 、 右 斜 线 是 否 放 有 棋 子 ， 有 则 值 为 1,否 则 值 为 0。for(j=0;j 0 ） i=1 /从 串 首 开 始 找while ( (ilength(n) /删 去 串 首 可 能 产 生 的 无 用 零输 出 n; 五 、 请 你 阐 述 prim算 法 的 基 本 思 想 。 并 给 出 下 图 的 最 小 生 成 树 （ 要 求 画 出 生 成 树 ， 分 析 过 程 可 以 省 略 ） （ 本 题 10分 ） prim算 法 的 基 本 思 想 是 ： 设 G=(V,E)是 连 通 带 权 图 ， V=1,2, ,n。首 先 置 U=1， 然 后 ， 只 要 U是 V的 真 子 集 ， 就 作 如 下 的 贪 心 选 择 ： 选 取 满 足 条 件 i U， j V-U， 且 cij最 小 的 边 ， 将 顶 点 j添 加 到 U中 。 这 个 过 程 一 直 进 行 到 U=V时 为 止 。 在 这 个 过 程 中 选 取 到 的 所 有 边 恰 好 构 成 G的 一 棵 最 小 生 成 树 。（ 5 分 ） 最 小 生 成 树 如 下 ： 六 、 算 法 分 析 题 （ 本 题 10分 ）数 字 全 排 列 问 题 ： 任 意 给 出 从 1 到 N的 N个 连 续 的 自 然 数 的 各 种 排 列 。 如 N=3 时 ， 共 有 以 下 6 种 排 列 方 式 ： 1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1 。 算 法 描 述 如 下 。画 出 N=3 时 递 归 调 用 时 堆 栈 变 化 情 况 ,写 出 相 对 应 i,j的 值 。 设 数 组 b 的 初 始 值 为 1 ， 2 ， 3 。p erm(in t b , in t i) in t k ,j;if(i=N) 输 出 ；else fo r(j=i;j=n u m;j+) 输 出 2 ， 1 ， 3 (5 )i=3 ,j=2 (4 )i=1 ,j=2(3 ) i=3 ,j=3 (1 ) i=1 ,j=1 弹 出 、 清 空 输 出 1 ， 3 ， 2 输 出 1 ， 2 ， 3 (2 ) i=3 ,j=2 (7 )i=1 ,j=3 输 出 2 ， 3 ， 1 (6 )i=3 ,j=3(9 )i=3 ,j=3 输 出 3 ,2 ,1(8 )i=3 ,j=2 输 出 3 ,1 ,2 swap (b i,b j); p erm(b ,i+1 ); swap (b j,b i); /* 初 始 调 用 时 i = 1 ;* / 答 案 ： p erm(in t b , in t i) in t k ,j;if(i=N) 输 出 b 数 组 各 元 素 值 ；else fo r(j=i;j=N;j+) swap (b i,b j); p erm(b ,i+1 ); (1 )(2 )(3 )(4 )(5 )(6 )(7 )(8 )(9 ) swap (b j,b i); /* 初 始 调 用 时 i = 1 ;* / 1、 简 答 题 ：1. 算 法 重 要 特 性 是 什 么 ？ 确 定 性 、 可 实 现 性 、 输 入 、 输 出 、 有 穷 性2. 算 法 分 析 的 目 的 是 什 么 ？ 分 析 算 法 占 用 计 算 机 资 源 的 情 况 ， 对 算 法 做 出 比 较 和 评 价 ， 设 计出 额 更 好 的 算 法 。 3. 算 法 的 时 间 复 杂 性 与 问 题 的 什 么 因 素 相 关 ？ 算 法 的 时 间 复 杂 性 与 问 题 的 规 模 相 关 ， 是 问 题 大 小 n的 函 数 。 4 算 法 的 渐 进 时 间 复 杂 性 的 含 义 ？ 当 问 题 的 规 模 n趋 向 无 穷 大 时 ， 影 响 算 法 效 率 的 重 要 因 素 是 T(n) 的 数 量 级 ， 而 其 他 因 素 仅 是 使 时 间 复 杂 度 相 差 常 数 倍 ， 因 此 可 以 用T(n)的 数 量 级 (阶 )评 价 算 法 。 时 间 复 杂 度 T(n)的 数 量 级 (阶 )称 为 渐 进 时 间 复 杂 性 。5. 最 坏 情 况 下 的 时 间 复 杂 性 和 平 均 时 间 复 杂 性 有 什 么 不 同 ？ 最 坏 情 况 下 的 时 间 复 杂 性 和 平 均 时 间 复 杂 性 考 察 的 是 n固 定 时 ， 不 同 输 入 实 例 下 的 算 法 所 耗 时 间 。 最 坏 情 况 下 的 时 间 复 杂 性 取 的 输 入实 例 中 最 大 的 时 间 复 杂 度 ： W(n) = max T(n， I) , I Dn平 均 时 间 复 杂 性 是 所 有 输 入 实 例 的 处 理 时 间 与 各 自 概 率 的 乘 积 和 ： A(n) = P(I)T(n， I) I Dn6. 简 述 二 分 检 索 （ 折 半 查 找 ） 算 法 的 基 本 过 程 。 设 输 入 是 一 个 按 非 降 次 序 排 列 的 元 素 表 Ai： j 和 x， 选 取A(i+j)/2与 x比 较 ， 如 果 A(i+j)/2=x， 则 返 回 (i+j)/2， 如 果 A(i+j)/2x， 则 Ai： (i+j)/2-1找 x， 否 则 在 A (i+j)/2+1： j找 x。 上 述 过 程 被 反 复 递 归 调 用 。 回 溯 法 的 搜 索 特 点 是 什 么7. 背 包 问 题 的 目 标 函 数 和 贪 心 算 法 最 优 化 量 度 相 同 吗 ？ 不 相 同 。 目 标 函 数 ： 获 得 最 大 利 润 。 最 优 量 度 ： 最 大 利 润 /重 量比 。 8. 采 用 回 溯 法 求 解 的 问 题 ， 其 解 如 何 表 示 ？ 有 什 么 规 定 ？问 题 的 解 可 以 表 示 为 n元 组 ： （ x 1,x2, xn） ， xi Si, Si为 有 穷集 合 ， x i Si, （ x1,x2, xn） 具 备 完 备 性 ， 即 （ x1,x2, xn） 是 合理 的 ， 则 （ x 1,x2, xi） (in)一 定 合 理 。9. 回 溯 法 的 搜 索 特 点 是 什 么 ？ 在 解 空 间 树 上 跳 跃 式 地 深 度 优 先 搜 索 ， 即 用 判 定 函 数 考 察 xk的 取 值 ， 如 果 xk是 合 理 的 就 搜 索 xk为 根 节 点 的 子 树 ， 如 果 xk取 完 了 所 有 的 值 ， 便 回 溯 到 xk-1。10. n皇 后 问 题 回 溯 算 法 的 判 别 函 数 place的 基 本 流 程 是 什 么 ？ 将 第 K行 的 皇 后 分 别 与 前 k-1行 的 皇 后 比 较 ， 看 是 否 与 它 们 相 容 ， 如果 不 相 容 就 返 回 false， 测 试 完 毕 则 返 回 true。 11 . 为 什 么 用 分 治 法 设 计 的 算 法 一 般 有 递 归 调 用 ？ 子 问 题 的 规 模 还 很 大 时 ， 必 须 继 续 使 用 分 治 法 ， 反 复 分 治 ， 必 然 要 用 到 递 归 。12 为 什 么 要 分 析 最 坏 情 况 下 的 算 法 时 间 复 杂 性 ？ 最 坏 情 况 下 的 时 间 复 杂 性 决 定 算 法 的 优 劣 ， 并 且 最 坏 情 况 下 的 时 间复 杂 性 较 平 均 时 间 复 杂 性 游 可 操 作 性 。 13 . 简 述 渐 进 时 间 复 杂 性 上 界 的 定 义 。T(n)是 某 算 法 的 时 间 复 杂 性 函 数 ， f(n)是 一 简 单 函 数 ， 存 在 正 整 数 No和 C， n No， 有 T(n)f(n)， 这 种 关 系 记 作 T(n)=O(f(n)。14 . 二 分 检 索 算 法 最 多 的 比 较 次 数 ？ 二 分 检 索 算 法 的 最 多 的 比 较 次 数 为 log n 。15 . 快 速 排 序 算 法 最 坏 情 况 下 需 要 多 少 次 比 较 运 算 ？ 最 坏 情 况 下 快 速 排 序 退 化 成 冒 泡 排 序 ， 需 要 比 较 n2次 。16. 贪 心 算 法 的 基 本 思 想 ？ 是 一 种 依 据 最 优 化 量 度 依 次 选 择 输 入 的 分 级 处 理 方 法 。 基 本 思 路是 ： 首 先 根 据 题 意 ， 选 取 一 种 量 度 标 准 ； 然 后 按 这 种 量 度 标 准 对 这 n个 输 入 排 序 ， 依 次 选 择 输 入 量 加 入 部 分 解 中 。 如 果 当 前 这 个 输 入 量 的 加入 ， 不 满 足 约 束 条 件 ， 则 不 把 此 输 入 加 到 这 部 分 解 中 。 17 回 溯 法 的 解 （ x1,x2, xn） 的 隐 约 束 一 般 指 什 么 ？ 回 溯 法 的 解 （ x1,x2, xn） 的 隐 约 束 一 般 指 个 元 素 之 间 应 满 足 的 某 种 关 系 。1 8 . 阐 述 归 并 排 序 的 分 治 思 路 。 将 数 组 一 分 为 二 ， 分 别 对 每 个 集 合 单 独 排 序 ， 然 后 将 已 排 序 的 两 个序 列 归 并 成 一 个 含 n个 元 素 的 分 好 类 的 序 列 。 如 果 分 割 后 子 问 题 还 很 大 ， 则 继 续 分 治 ， 直 到 一 个 元 素 。19. 快 速 排 序 的 基 本 思 想 是 什 么 。 快 速 排 序 的 基 本 思 想 是 在 待 排 序 的 N个 记 录 中 任 意 取 一 个 记 录 ， 把该 记 录 放 在 最 终 位 置 后 ， 数 据 序 列 被 此 记 录 分 成 两 部 分 。 所 有 关 键 字 比 该 记 录 关 键 字 小 的 放 在 前 一 部 分 ， 所 有 比 它 大 的 放 置 在 后 一 部 分 ， 并 把该 记 录 排 在 这 两 部 分 的 中 间 ， 这 个 过 程 称 作 一 次 快 速 排 序 。 之 后 重 复 上 述 过 程 ， 直 到 每 一 部 分 内 只 有 一 个 记 录 为 止 。20. 什 么 是 直 接 递 归 和 间 接 递 归 ？ 消 除 递 归 一 般 要 用 到 什 么 数 据 结 构 ？ 在 定 义 一 个 过 程 或 者 函 数 的 时 候 又 出 现 了 调 用 本 过 程 或 者 函 数 的成 分 ， 既 调 用 它 自 己 本 身 ， 这 称 为 直 接 递 归 。 如 果 过 程 或 者 函 数 P调 用 过 程 或 者 函 数 Q， Q又 调 用 P， 这 个 称 为 间 接 递 归 。 消 除 递 归 一 般 要 用 到栈 这 种 数 据 结 构 。 21. 什 么 是 哈 密 顿 环 问 题 ？ 哈 密 顿 环 是 指 一 条 沿 着 图 G的 N条 边 环 行 的 路 径 ， 它 的 访 问 每 个 节 点 一 次 并 且 返 回 它 的 开 始 位 置 。22. 用 回 溯 法 求 解 哈 密 顿 环 ， 如 何 定 义 判 定 函 数 ？ 当 前 选 择 的 节 点 Xk是 从 未 到 过 的 节 点 ,即 Xk Xi(i=1,2, ,k-1)， 且 C(Xk-1, Xk) ， 如 果 k=-1， 则 C(Xk, X1) 。23. 请 写 出 prim算 法 的 基 本 思 想 。 思 路 是 ： 最 初 生 成 树 T为 空 ， 依 次 向 内 加 入 与 树 有 最 小 邻 接 边 的n-1条 边 。 处 理 过 程 ： 首 先 加 入 最 小 代 价 的 一 条 边 到 T， 根 据 各 节 点 到 T 的 邻 接 边 排 序 ， 选 择 最 小 边 加 入 ， 新 边 加 入 后 ， 修 改 由 于 新 边 所 改 变 的邻 接 边 排 序 ， 再 选 择 下 一 条 边 加 入 ， 直 至 加 入 n-1条 边 。 2、 复 杂 性 分 析1、 MERGESORT(low， high) if lowM then return endif a a+i i i+1 ; repeat end i 1 ;s 0 时 间 为 ： O(1) while i n do 循 环 n次 循 环 体 内 所 用 时 间 为 O(1) 所 以 总 时 间 为 :T(n)=O(1)+ nO(1)= O(n) 3、 procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) v A(m);i m loop loop i i+1 until A(i) v repeatloop p p-1 until A(p) v repeat if ixmax then xmax A(i); j i;endif repeatend MAX xmax A(1);j 1 时 间 为 ： O(1) for i 2 to n do 循 环 最 多 n-1次 所 以 总 时 间 为 : T(n)=O(1)+ (n-1)O(1)= O(n) 6、 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low 1;high n while low high do mid |_(low+high)/2_| case :xA(mid):low mid+1 :else:j mid; return endcase repeat j 0 end BINSRCH log2n+13、 算 法 理 解 1、 写 出 多 段 图 最 短 路 经 动 态 规 划 算 法 求 解 下 列 实 例 的 过 程 ， 并 求 出最 优 值 。 52 8 63 1 74 各 边 的 代 价 如 下 ： C(1,2)=3， C(1,3)=5 ， C(1,4)=2C(2,6)=8 ， C(2,7)=4 ， C(3,5)=5 ， C(3,6)=4， C(4,5)=2， C(4,6)=1C(5,8)=4， C(6,8)=5 ， C(7,8)=6 Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ， D5=8Cost(3,6)= C(6， 8)+0=5, D6=8 Cost(3,5)= C(5， 8)+0=4 D7=8 Cost(2,4)= minC(4， 6)+ Cost(3,6), C(4， 5)+ Cost(3,5) = min1+ 5, 2+4=6 D4=6 Cost(2,3)= minC(3， 6)+ Cost(3,6) = min4+5=9 D3=5 Cost(2,2)= minC(2， 6)+ Cost(3,6), C(2， 7)+ Cost(3,7) = min8+5, 4+6=10 D2=7 Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) = min3+10, 5+9,2+6= 8 D1=41 4 6 8 2、 写 出 maxmin算 法 对 下 列 实 例 中 找 最 大 数 和 最 小 数 的 过 程 。数 组 A=(48,12,61,3,5,19,32,7) 写 出 maxmin算 法 对 下 列 实 例 中 找 最 大 数 和 最 小 数 的 过 程 。数 组 A=() 1、 48,12,61,3, 5,19,32,72、 48,12 61,3 5,19 32,7 3、 48 61, 12 3 19 32， 5 74、 61 32 3 5 5、 61 9.给 出 5个 数 (3,6,9,1,7),M=13， 用 递 归 树 描 述 sumofsub算 法 求 和 数 =M 的 一 个 子 集 的 过 程 。1 ， 2 8 ， 0 2 ， 2 5 ， 3 3 ， 1 9 ， 3 4 ， 1 0 ， 1 2 1、 快 速 排 序 算 法 对 下 列 实 例 排 序 ， 算 法 执 行 过 程 中 ， 写 出 数 组 A第 一 次 被 分 割 的 过 程 。A=(65,70,75,80,85,55,50,2) (1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 8 65 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 2 2、 归 并 排 序 算 法 对 下 列 实 例 排 序 ， 写 出 算 法 执 行 过 程 。 A=(48,12,61,3,5,19,32,7) 12,48 ,3,61 ,5,19 ,7,32 3, 12, 48, 61 ,5, 7, 19， 32 3,5, 7,12， 19， 32， 48,613、 对 于 下 图 ， 写 出 图 着 色 算 法 得 出 一 种 着 色 方 案 的 过 程 。 23 1 4 4、 写 出 归 并 排 序 算 法 对 下 列 实 例 排 序 的 过 程 。 (6,2,9,3,5,1,8,7) 调 用 第 一 层 次 6,2,9,3 5,1,8,7 分 成 两个 子 问 题 调 用 第 二 层 次 6,2 9,3 5,1 8,7 分 成 四 个 子 问 题 调 用 第 三 层 次 6 2 9 3 5 1 8 7 分 成 八 个 子 问 题 调 用 第 四 层 次 只 有 一 个 元 素 返 回 上 一 层 第 三 层 归 并 2 ,6 3, 9 1,5 7,8 返 回 上 一 层第 二 层 归 并 2 ,3,6, 9 1,5,7,8 返 回 上 一 层 第 一 层 归 并 1, 2 ,3, 5 ,6, 7, 8,9 排 序 结 束 ，返 回 主 函 数 5、 写 出 用 背 包 问 题 贪 心 算 法 解 决 下 列 实 例 的 过 程 。 P=(18,12,4,1) W=(12,10,8,3) M=25 实 例 符 合 P(i)/W(i) P(i+1)/W(i+1)的 顺 序 。 CU 25,X 0 W1100时 m(x)=x-10;当 x100) return(x-100);else y=m(x+11); return (m(y); 15、 设 计 一 个 算 法 在 一 个 向 量 A中 找 出 最 大 数 和 最 小 数 的 元 素 。Void maxmin(A,n) Vector A;int n; int max,min,i; max=A1;min=A1;for(i=2;imax)max=Ai;else if(Aicu then exit endif X(i) 1 cu cu-W(i) repeat end GREEDY-KNAPSACK 根 据 算 法 得 出 的 解 ： X=（ 1,1,1,1,1,0,0） 获 利 润 52， 而 解（ 1,1,1,1, 0, 1,0） 可 获 利 润 54 因 此 贪 心 法 不 一 定 获 得 最 优 解 。 4. 设 计 只 求 一 个 哈 密 顿 环 的 回 溯 算 法 。 Hamiltonian(n)k 1; xk 0; While k0 do xk xk+1; while B(k)=false and xk n do xk xk+1; repeat If xk n then if k=n then print x; return else k k+1; xk 0; endif else k k-1 endifrepeat end procedure B(k) Gxk-1,xk 1 then return false; for i 1 to k-1 do if xi=xk then return false;endif repeat return true; 5 利 用 对 称 性 设 计 算 法 ， 求 n=2k（ K为 正 整 数 ） 的 皇 后 问 题 所 有 解 。procedure NQUEENS1(n) a 0 /计 数 器 清 零X(1) 0； k 1 /k是 当 前 行 ； X(k)是 当 前 列 / While k0 do /对 所 有 的 行 执 行 以 下 语 句 /1) X(k) X(k)+1 /移 到 下 一 列 / While X(k) n and not PLACE(k) do2) X(k) X(k)十 l if X(k) n then if k=n / thenprint(X)， a a+1 /找 到 一 个 解 计 数 器 a加 1/ if a=n/2 then return / 找 到 n/2个 解 算 法 结 束 3) else k k+1； X(k) 0； 4) else k k 1 /回 溯 / end NQUEENS
展开阅读全文