数据结构课程设计题目及说明201420151

1、数据结构课程设计序号题 目说 明第一组1-1一元多项式乘法1) 问题描述已知A(x)=a0+a1x+a2x2+anxn和B(x)=b0+b1x+b2x2+bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)*B(x)。2) 基本要求(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。1-2迷你计算器功能要求：（1）计算任意一个算术表达式的加法、减法、除法以及乘法。（2）运算数为整数和小数（3）人机界面自定义，要友好。如用户输入错误在计算之前可以修改。1-3排序算法演示系统1）问题描述设计一个测试程序比较几种内部排序算法的

2、关键字比较次数和移动次数以取得直观感受。2）基本要求(1)实现各种内部排序。包括冒泡排序，直接选择排序，希尔排序，快速排序，堆排序。(2) 待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个)，至少用5组不同的数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3) 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，比较各种排序的优劣。(4) 界面友好，易与操作。采用菜单方式进行选择。1-4通讯录管理1）问题描述编写一个简单的通讯录管理程序。通讯录记录有姓名、地址、电话号码、电子邮箱等4项。2）基本要求程序应提供的基本管理功能如下：（1）添

3、加：增加一个人的记录到通讯录中；（2）显示：在屏幕上显示所以通讯录中的人员信息，应能分屏显示；（3）存储：将通讯录信息保存在一个文件中；（4）装入：即将文件中的信息读入程序；（5）查询：可根据姓名查找某人的相关信息，若找到显示其姓名、地址、电话号码、电子邮箱；（6）修改：可修改一个人的除姓名之外的其他信息；3）测试数据程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。1-5图书管理系统功能要求：（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。(2) 每种书的登记内容包括书号、书名、著作者、现存量和库存量； (3) 对书号建立索引表（线性表）以提高查找效率；(4

4、) 系统主要功能如下： *采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； *借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； *归还：注销对借阅者的登记，改变该书的现存量1-6多项式运算功能要求：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列n,c1,e1,c2,e2,cn,en,其中n是多项式的 项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b；输出相加的多项式（4）多项式a和b相减，建立多项式a-b。输出相加的多项式（5）用带表头结点的单链表存储

5、多项式。1-7公园主要游览景点之间最短距离问题问题描述：图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。公园最短路径问题中的数据元素有：（1）顶点数（2）边数（3）边的长度功能需求：要求完成以下功能：(1) 输出顶点信息：将公园内各景点输出。（2）输出边的信息：将公园内每两个位置（若两个位置之间有直接路径）的距离输出。(3) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；(

6、4) 求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径。（5）删除：删除任意一条边。（6）插入：插入任意一条边。1-8最少换车次数问题1)问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。2)基本要求：求得从站0出发乘公交车至站n-1的最少换车次数。3)设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边<i,j>，权值为1

7、。因此，从站x至站y的最少上车次数对应于图G中从顶点x到顶点y的最短路径长度。第2组2-1文章编辑1)问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。2) 基本要求静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"

8、、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；2-2哈希表设计1)问题描述针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。2)基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。3)测试数据取读者周围较熟悉的30个人名。4)选作内容（1）从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作

9、实验）。（2）研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。（3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。2-3二叉排序树的遍历1)问题描述输入树的各个结点，建立二叉排序树，对建立的二叉排序树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)输入树的各个结点，建立二叉排序树，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。2-4个人帐簿管理系统设计1)问题描述个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教

10、育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。2) 基本要求（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；（3）进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。2-5学分管理程序1) 问题描述请设计一个学生的学分管理程序。假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够

11、毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。学分信息应该包括学号、姓名、课程类别、学分等。2) 基本要求该程序应该具有下列功能：(1) 通过键盘输入多个学生的学分，存入数据文件中； (2) 给定学号，显示某位学生的学分完成情况；(3) 给定某个班级的班号，显示该班所有学生学分完成情况；(4) 给定某位学生的学号，修改该学生的学分信息；(5) 按照某类课程的学分高低进行排序；(6) 提供一些统计各类信息的功能。2-6学生作业完成情况管理程序1)问题描述请设计一个学生作业完成情况管理程序。假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作

12、业的成绩计算出最终的平时成绩（满分100）。作业登记信息应该包含：学号、姓名、10次作业的完成情况。2) 基本要求该程序应该具有下列功能：(1) 通过键盘输入某位学生某次作业的分数；(2) 给定学号，显示某位学生作业完成情况；(3) 给定某个班级的班号，显示该班所有学生的作业完成情况；(4) 给定某位学生的学号，修改该学生的作业完成信息；(5) 给定某位学生的学号，删除该学生的信息；(6) 按学生的最终平时成绩进行排序；(7) 输出平均分数。（8）用数据文件保存作业登记信息。2-7学生籍贯管理系统1)问题描述编制一个学生籍贯信息记录簿，每个学生信息包括：学号、姓名、籍贯、通信地址。2) 基本要

13、求该程序应该具有下列功能：（1）输入学生信息并以磁盘文件保存；（2）读取磁盘文件并显示输出所有学生的籍贯信息；（3）按学号或姓名查询其籍贯；（4）按籍贯查询并输出该籍贯的所有学生；（5）能添加、删除和修改学生的籍贯信息；（6）显示输出天津籍和非天津籍学生的信息并可分别存盘；（7） 按学号进行排序。2-8通信录管理系统1)问题描述设计出模拟手机通信录管理系统，实现对手机中的通信录进行管理。2) 基本要求功能要求：（1）查看功能：选择此功能时，列出下列三类选择。A 工作类 B 家庭类 C 朋友类 ，当选中某类时，显示出此类所有数据中的姓名和电话号码）（2）增加功能：能录入新数据（一个结点包括：姓名

14、、电话号码、分类（可选项有：A 工作类 B 家庭类 C 朋友类）、家庭住址）。例如 杨春商务类 南开区当录入了重复的姓名和电话号码时，则提示数据录入重复并取消录入；当通信录中超过10条信息时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。（3）修改功能：选中某个人的姓名时，可对此人的相应数据进行修改（4） 删除功能：选中某个人的姓名时，可对此人的相应数据进行删除，并自动调整后续条目的编号。第3组3-1串的查找和替换1） 问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。2） 基本要求编写字符串的模式匹配程序，

15、实现字符串的查找替换功能3-2迷宫问题1)问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。2) 基本要求(1) 设计数据结构存储迷宫；(2) 设计存储结构保存从入口到出口的通路；(3) 设计算法完成迷宫问题的求解；(4) 分析算法的时间复杂度。3-3TSP问题（回溯法求解）1) 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员

16、问题，是图问题中最广为人知的问题。2) 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。3-4医院选址问题1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2) 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3-5机器调度问题1)问题描述机器调度是指有m

17、台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业i一旦运行，则需要ti个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。2) 基本要求(1) 建立问题模型，设计数据结构；(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。3-6个人电话号码查询系统1) 问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。

18、2) 基本要求(1)使用文件保存电话号码信息；(2)设计数据结构存储电话号码信息；(3) 提供查询功能：根据姓名实现快速查询；(4) 提供其他维护功能：例如插入、删除、修改等；(5) 按电话号码进行排序。3-7数制转换任意给定一个M进制的数x ，请实现如下要求1)求出此数x的10进制值（用MD表示）2)实现对x向任意的一个非M进制的数的转换。3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。3-8学生搭配1) 问题描述一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,

19、 本曲没成功配对者坐着等待下一曲找舞伴。2) 基本要求请设计一系统模拟动态地显示出上述过程,要求如下:(1)输出每曲配对情况(2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值(3)尽量设计出多种算法及程序,可视情况适当加分 提示:用队列来解决比较方便.第4组4-1库存管理系统的目的是实现货物的入库和出库，以及存储情况1、 系统管理员可以实现货物的入库和出库管理一般用户可以查询货物的出库个数和存储个数，和货物的信息（比如产地、生产日期等）4-2公交线路调配管理系统系统的目的可以实现对公交车辆的统一管理，以及实时监控各公交线路的情况。1、 可以查

20、询每条线路的出车情况2、 根据线路的回执，可以根据具体情况，增加车辆3、 车辆故障处理4 车辆定期维修4-3超市商品管理系统 系统目的是可以实现对商品信息的查询，以及商品的入库和出库管理。系统管理员可以实现商品的入库和出库管理一般用户可以查询商品的售出和存储个数，和商品的信息（比如价格、产地、生产日期等）4-4考试系统 要求能识别考生，自动随机抽取试题，考试时间到自动交卷，交卷时自动评分。教师能根据教学内容生成或维护试题库，能了解学生学生的考试情况。该考试系统只限单选题、多选题和判断题，它由二个子系统组成：1、报名系统：（1）考生信息录入。（2）准考证号生成。（3）考生信息查询与维护。2、考试

21、系统：考生只需输入准考证，与登录考生信息相符即可开始考试，否则拒绝登录，考试开始时将自动抽取试题，考试时间到自动交卷，交卷时自动评分。3、数据管理：将报名表中的考生信息导入登录表。4、查询与统计：查询已考人员成绩及统计人数。查询零分人员及统计人数。查询未考人员及统计人数。交卷后可查询本考试各题的用户答案与正确答案（注意不同用户的权限）4-5人事工资管理系统 要求对某单位的人事和工资进行管理。1数据管理：职工信息录入、数据更新-包括人员调动、职称、工资和退休等2查询：查个人信息、部门信息、职称情况、入伍时间、工资情况、是否在职等3统计：各部门人数、各类职称人数、统计各类工资总和、科研成果统计等4

22、工资管理5.生成报表：生成各类统计报表、生成每月工资表、生成各类统计报表4-6人口信息管理系统 要求对某一城市的人口情况进行管理1、 常住人口管理（登记、删除、迁入、移出）外来暂住人口管理（登记、信息管理）4-7稀疏矩阵的加法运算输入任意两个系数矩阵A和B，求出它们的和矩阵C。要求：1、输入两个稀疏矩阵的行数、列数以及非零元素，创建稀疏矩阵；2、实现两个系数矩阵的加法运算；3、输出系数矩阵；4、要求分别使用三元组表和十字链表两种数据结构实现。4-8大整数计算器实现大整数（200位以内的整数）的加、减、乘、除运算。说明：由于整型数据存储位数的有限，因此引入串的概念，将整型数据用字符串进行存储，利

23、用字符串的一个字符存储大整数的一位数值，然后根据四则运算规则，对相应位依次进行相应运算，同时保存进位，从而实现大整数的精确运算。第5组5-1电力收费综合管理系统 要求可以对个用户进行电力收费管理1、用电指数查询及收费2、欠费用户管理3、电力故障报警5-2安徽省内汽运公路交通系统系统目的是实现通用查询，主要功能：1、系统管理员管理汽车基本信息。一般用户：只具有查询权限，不具有系统管理权限。2、可搜索从起始站到终点站（用户输入站名拼音或汉字）的所有汽车，向用户发布相关信息（车次、发车和到站时间、里程、票价）。3、可根据给出的区间（用户输入）查询出车次的基本信息（包括发车时间，剩余票数，到站时间、票价等）。5-3多项式求导要求实现一元多项式求导运算，有效字符为变量x，数字0-9，运算符、+、-、*、/，输入的多项式以#结尾。输出结果也为多项式。例如：输入：6x4-32x，输出结果为：24x3-32。5-4马踏棋盘所谓马踏棋盘问题，是指将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个