医院选址问题数据结构

计算机科学与技术专业数据结构大作业

一、 实验内容概述

n个村庄之间的交通图用有向加权图表示，图中的有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

图1 医院选址加权有向图

测试数据：针对图1，输入以下数据： 输入顶点数： 5 输入顶点对和弧的权值：

1 2 1

2 3 2 3 4 2 3 5 4 4 2 1 4 3 3 5 4 5 0 0 0

1

计算机科学与技术专业数据结构大作业

二、 实验目的概述

“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，“数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计

课程设计任务书

2011—2012学年第1学期

电子与信息工程 系 计算机科学与技术 专业 班级 课程设计名称： 数据结构课程设计 设计题目： 医院选址问题

完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周

一、 二、

设计目的 设计要求

熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

1. 重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； 2. 按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者

与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；

3. 学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； 4. 认真编写课程设计报告。 三、

设计内容 医院选址问题 1. 问题描述

n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？

2. 基本要求

中心医院选址问题

作者 曹彦杰 学号 200807011203 单位：中国石油大学胜利学院

信息与计算科学系 信息与计算科学专业08级2班

摘 要 运用Dijkstra法解决选址问题

一、问题提出

某地区打算建立一中心医院，已知某地区的交通网络如图,其中点代表居民小区，边代表公路，权值为小区间公路距离，为了使各个小区的居民看病最方便，即使离医院最远的小区居民就诊时所走的路程最近，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？

v1310

v34v55934v6

6510 v2v46v8v7二、基本方法

本算法是由E.W.Dijkstra于1959年提出的，可用于求解指定两点s和t间的最短路和指

vv定点s到其余各点的最短路。对于所有的wij优方程，即d(vi,vj)v?0，由动态规划的最优化原理可以得到最

,记

?min{d(vs,vj)?wij},对于i?Vwii?0；对于

i?j，若vij?E,记wij??。由于Dijkstra提出了在所有算出的最短路的权值中，

挑选最短的一个作为从s到该点的最小权值，这就使得本算法的运算量比动态规划算法有所减少，Dijkstra算法被公为目前求无负权网络最短路问题的最好方法

数据结构实验报告

实验名称：实验2 利用栈结构实现八皇后问题

学生姓名： 廖宁

班 级： 2009211114

班内序号： 18

学 号： 09210411

日 期： 2010年11月18日

1．实验要求

八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。

提示：

（1）可以使用递归或非递归两种方法实现。

（2）实现一个关键算法，判断任意两个皇后是否在同一行、同一列和同一斜线上。

2. 程序分析

程序工程包含一个模板类函数实现定义的源文件forthelove.cpp和测试源文件sbsuowang.cpp。

2.1 存储结构

存储结构为栈。

2.2 关键算法分析

(1)

判断在第row行第column列摆放皇后是否非法,采取定行不定列的方法，列相等的算法为position[i]=colume，对角线相等有两种情况：一是position在上则

row-i=colume-position[i];

二是position在下，row-i=position[i]-colume.加入能放皇后，列和对角线上值都不能相等。 具体

德州学院 物理系 2009届 电子信息科学与技术专业 数据结构课程设计

背包问题的求解

摘 要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件

下，追求总的最大收益的资源有效分配问题。

关键词 背包问题； 递归算法

1问题描述

1.1问题描述

背包问题是一种组合优化的NP完全问题。问题可以描述为：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。它主要分为以下几种问题：

（1）0/1背包问题

有n件物品和一个容量为v的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 (2)完全背包问题

有n种物品和一个容量为v的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费

分类号编号

华北水利水电大学

North China Institute of Water Conservancy and Hydroelectric Power

课程设计

题目舞伴问题

院系信息工程学院 专业计算机科学与技术

姓名贾宁

指导教师杨彬

第一章需求分析 ........................................................................................................................ 2

1.1问题描述 ...................................................................................................................... 2 1.2 基本要求 ..................................................................................................................... 2

1.2.1 输入及输出格式

中南民族大学管理学院

学生实验报告

实验项目: 约瑟夫问题 课程名称： 数据结构 年 级：

专 业：信息管理与信息系统 指导教师：

实验地点：管理学院综合实验室 完成日期： 小组成员：

2012 学年至2013 学年度第 1 学期

中南民族大学管理学院学生实验报告

一、实验目的

（1）掌握线性表表示和实现； （2）学会定义抽象数据类型；

（3）学会分析问题，设计适当的解决方案；

二、实验内容

【问题描述】：编号为 1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】：m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5）。

三、实验步骤

（一） 需求分析

对于这个程序来

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

中南民族大学管理学院

学生实验报告

实验项目: 约瑟夫问题 课程名称： 数据结构 年 级：

专 业：信息管理与信息系统 指导教师：

实验地点：管理学院综合实验室 完成日期： 小组成员：

2012 学年至2013 学年度第 1 学期

中南民族大学管理学院学生实验报告

一、实验目的

（1）掌握线性表表示和实现； （2）学会定义抽象数据类型；

（3）学会分析问题，设计适当的解决方案；

二、实验内容

【问题描述】：编号为 1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】：m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5）。

三、实验步骤

（一） 需求分析

对于这个程序来

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集