1 课程设计任务书 2 0 1 1 —2 0 1 2 学 年 第 1 学 期 电 子 与 信 息 工 程 系 计 算 机 科 学 与 技 术 专 业 班 级 课 程 设 计 名 称 ： 数 据 结 构 课 程 设 计 设 计 题 目 ： 医 院 选 址 问 题 完 成 期 限 ： 自 2012 年 1 月 2 日 至 2012 年 1 月 6 日 共 1 周 一 、 设 计 目 的 熟 悉 各 种 数 据 结 构 和 运 算 ， 会 使 用 数 据 结 构 的 基 本 操 作 解 决 一 些 实 际 问 题 。 二 、 设 计 要 求 1. 重 视 课 程 设 计 环 节 ， 用 严 谨 、 科 学 和 踏 实 的 工 作 态 度 对 待 课 程 设 计 的 每 一 项 任 务 ； 2. 按 照 课 程 设 计 的 题 目 要 求 ， 独 立 地 完 成 各 项 任 务 ， 严 禁 抄 袭 ； 凡 发 现 抄 袭 ， 抄 袭 者与 被 抄 袭 者 皆 以 零 分 计 入 本 课 程 设 计 成 绩 。 凡 发 现 实 验 报 告 或 源 程 序 雷 同 ， 涉 及 的全 部 人 员 皆 以 零 分 计 入 本 课 程 设 计 成 绩 ； 3. 学 生 在 接 受 设 计 任 务 后 ， 首 先要 按 设 计 任 务 书的 要 求 编写设 计 进程 表； 4. 认真编写课 程 设 计 报 告 。 三、 设 计 内容 医 院 选 址 问 题 1. 问 题 描述 n 个村庄之间的 交通图可以 用 有向网图来表示， 图中边上的 权值表示从村庄i到村庄j 的 道路长度 。 现 在 要 从这n 个村庄中选 择一 个村庄新建一 所医 院 ， 问 这所医 院 应建在 哪个村庄， 才能使 所有的 村庄离医 院 都比较近？ 2. 基 本 要 求 (1) 建立 模型， 设 计 存储结 构 ； (2) 设 计 算 法完 成 问 题 求 解 ； (3) 分 析算 法的 时间复杂度 。 3. 设 计 思想 医 院 选 址 问 题 实 际 是求 有向图中心点的 问 题 。 首 先定义顶点的 偏心度 。 设 图G=（V， E）， 对 任 一 顶点k， 称 E(k)=max{d(i, k)}（i∈V）为顶点k 的 偏心度 。显然， 偏心度 最小的 顶点即为图G 的 中心点。 如图7(a)所示是一 个带权有向图， 其各 顶点的 偏心度 如图(b)所示。 1 2 3 4 5 1...
