《2012级计科专业《算法与数据结构》课程设计题》由会员分享，可在线阅读，更多相关《2012级计科专业《算法与数据结构》课程设计题（9页珍藏版）》请在金锄头文库上搜索。
1、2012级计科专业算法与数据结构课程设计题指导教师:宗瑜指导题目：题目1、最小生成树问题问题描述:给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求：(1城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。(2表示城市间距离网的邻接矩阵(要求至少6个城市，10条边(3要求在屏幕上显示得到的最小生成树中包括哪些城市间的道路及其权值，并显示得到的最小生成树的代价。题目2、哈希表的设计与实现问题描述:设计哈希表实现电话号码查询系统。基本要求
2、：(1设每个记录有下列数据项：电话号码、用户名；(2从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；(3采用线性探测再散列处理冲突；(4查找并显示给定电话号码的记录(5查找并显示给定用户名的记录。选做内容:在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法(至少两种，考察平均查找长度的变化。题目3、排序算法包的实现问题描述:用程序实现快速排序、堆排序和归并排序将一组随机数列按非递减的顺序排列。基本要求：(1待排序列为由随机函数生成的一组整数数列。(2程序以用户和计算机的对话方式执行，即在屏幕上显示所能进行的操作，用户根据提示输入相应命令，计算机处理完毕将运算结果在屏幕上显示，并
3、等待用户的后续操作。选做内容:实现希尔排序和基数排序。要求:图形界面设计题目4、任意长的整数加减器问题描述:设计一个程序实现两个任意长的整数的求和运算。基本要求:利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。女口:1,0000,0000,0000,0000。指导教师:金萍指导题目：题目1、迷宫求解问题描述：以一个mn的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求:首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得
4、的通路以三元组(i,j,d的形式输出，其中:(i,j指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的迷宫，输出的一条通路为:(1,1,1,(1,2,2,(2,2,2(3,2,3,(3,1,2,。测试数据：迷宫的测试数据如下：左上角(1,1为入口，右下角(9,8为出口。12345678实现提示:计算机解迷宫通常用的是穷举求解”方法,即从入口出发，顺着某一个方向进行探索,若能走通,则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为(1,
5、1，出口点的下标为(n,n。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。选作内容：(1编写递归形式的算法，求得迷宫中所有可能的通路；(2以方阵形式输出迷宫及其通路。题目2、哈夫曼编码器的实现问题描述:根据输入的字符和对应的权重，生成一棵哈夫曼树,再打印各字符对应的哈夫曼编码。并要求利用建好的哈夫曼树对字符串进行编码，对哈夫曼编码进行译码。实现提示:元素类型选用字符型，对应的权重值选用整型，请从键盘输入。并从键盘输入要编码和译码的字符串或代码串。题目3、校园导游程序问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求：(1
6、设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。001000101101001000000101100101010000(2为来访客人提供图中任意景点相关信息的查询。(3为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的上条最短的简单路径。数据测试:由读者根据实际情况指定。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息。选作内容：(1求校园图的关节点。(2提供图中任意景点问路查询，即求任意两个景点之间的所有路径。(3提供校园图中多个景点的
7、最佳访问路线查询，即求途经这多个景点的最佳(短路径。(4校园导游图的景点和道路的修改扩充功能。题目4、病房管理问题描述:一所医院中可能包括若干个病房，每个病房中又有若干个床位，建立一个简单的医院病房管理程序能够对病人进行出入院和床位分配进行管理。基本要求：此系统应具有如下功能：(1I:初始化(Initialization。建立病房和床位信息。此医院中可能包括若干个病房，而每个病房中又有若干个床位。(2E:住院(enterhospital。在列出的有空位的病房中，选择其一,入住。(3O:出院(Outhospital。选择某一病房中某个病人，令其出院。(4Q:查询(Query。查询每个病房中空床位
8、数,入住病人数;查询整个医院的空床位数和入住病人数。测试数据：建立一个包含3个病房的医院，其中1病房有2张床位,2病房有6张床位,3病房有8张床位;张三和李四住1病房，王五也要住1病房，此时，床位已满,于是将其调入2病房。实现提示：(1可建立若干个不定长链表，每个链表代表一个病房，病房数可用n表示,床位数用m表示。(2判断病房是否住满，直接对m进行操作即可。指导教师:严仍荣指导题目：题目1、舞伴问题问题描述:一班有m个女生、n个男生(m不等于n,举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模
9、拟舞伴配对过程。基本要求:输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号,也可以随机编号，输出每曲配对情况(包括男、女生的姓名、性别和编号。原始数据和结果数据要保存到文件中。测试数据:分别选择男生多于女生、女生多于男生、男女生相等的三组测试数提高要求：计算出任意一位男生(编号为X和任意一位女生(编号为丫,在第K曲配对跳舞的情况。题目2、管道铺设施工的最佳方案问题描述：需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可,假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。基本要求：输入表示小区间关
10、系的图及每条管道的权值，选择出n-1条管道,使总投资最小。图的信息输入一次后，保存到文件中，选择的n-1条管道输出到显示器的同时也保存于文件中。测试用例:任意选择一个图，模拟小区间可能铺设的管道及费用。提高要求:显示原始图及选择n-1条管道后的图。题目3、商店存货管理系统功能:建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：(1初步完成总体设计，搭好框架,确定人机对话的界面，确定函数个数；(2完成最低要求：建立一个文件,包括5个种类的货物情况，能对商品信息进行扩充(追加，修改和删除以及简单的排序；(3进一步要求：扩充商品数量，以及完成系统查询功能。有
11、兴趣的同学可以自己扩充系统功能。要求：1界面友好，函数功能要划分好2总体设计应画一流程图3程序要加必要的注释4要提供程序测试方案题目4、通讯录的制作设计目的：编写一个通讯录管理系统。设计任务:本系统应完成几方面的功能：1输入信息enter（;2显示信息display（;3查找以姓名作为关键字search（;4删除信息delete（;5 存盘save（;6 装入load（;设计要求:1每条信息至包含：姓名（NAME街道（STREET城市（CITY邮编（EIP国家（STATE几项；2作为一个完整的系统，应具有友好的界面和较强的容错能力；3需要链表实现；4上机能正常运行。指导教师：杨洋指导题目：题目
12、1、火车订票系统任务：通过此系统可以实现如下功能：1录入：可以录入车次情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2查询：可以查询某个车次的情况（如，输入车次号，查询起止时间，起止城市，票价，票价折扣，确定是否满座）；可以输入起止城市，查询车次情况；3订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该车次已经无票，可以提供相关可选择；4退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及车次情况，订单要有编号。5修改信息：当信息改变可以修改数据文件要求：根据以上功能说明，设计车次信息，订票信息的存储结构，设计程序完成功能。题目2、数制转换
13、问题任意给定一个M进制的数x，请实现如下要求1求出此数x的10进制值（用MD表示）2实现对x向任意的一个非M进制的数的转换。3至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。题目3、学生成绩管理系统现有学生成绩信息文件1（1.txt），内容自定义学生成绩信息文件2（2.txt）,内容自定义试编写一管理系统，要求如下：1实现对两个文件数据进行合并，生成新文件3.txt2抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3合并后的文件3.txt中的数据按总分降序排序（至少采用两种排序方法实现4输入一个学生姓名后，能查找到此学生的信息并输出结果（至少采用两种查找方法实现5要求使用结构体，链或数组等实现上述要求6采用多种方法且算法正确者，可适当加分.题目4、商品销售管理系统针对某一种行业的库房的产品进销存情况进行管理。基本要求：1采用一定的存储结构对库房的货品及其数量进行分类管理；2可以进行产品类的添加、产品的添加、产品数量的添加；能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；
