题目与要求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)分析算法的时间复杂度和空间复杂度。2迷你计算器功能要求：（1）计算任意一个算术表达式的加法、减法、除法以及乘法。（2）运算数为整数和小数（3）人机界面自定义，要友好。如用户输入错误在计算之前可以修改。3排序算法演示系统1）问题描述设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。2）基本要求(1)实现各种内部排序。包括冒泡排序，直接选择排序，希尔排序，快速排序，堆排序。(2)待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个)，至少用5组不同的数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3)演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，比较各种排序的优劣。(4)界面友好，易与操作。采用菜单方式进行选择。4通讯录管理1）问题描述编写一个简单的通讯录管理程序。通讯录记录有姓名、地址、电话号码、电子邮箱等4项。2）基本要求程序应提供的基本管理功能如下：（1）添加：增加一个人的记录到通讯录中；（2）显示：在屏幕上显示所以通讯录中的人员信息，应能分屏显示；（3）存储：将通讯录信息保存在一个文件中；（4）装入：即将文件中的信息读入程序；（5）查询：可根据姓名查找某人的相关信息，若找到显示其姓名、地址、电话号码、电子邮箱；（6）修改：可修改一个人的除姓名之外的其他信息；3）测试数据程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。5图书管理系统功能要求：（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。(2)每种书的登记内容包括书号、书名、著作者、现存量和库存量；(3)对书号建立索引表（线性表）以提高查找效率；(4)系统主要功能如下：①采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；②借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；③归还：注销对借阅者的登记，改变该书的现存量。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）用带表头结点的单链表存储多项式。7公园主要游览景点之间最短距离问题问题描述：图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。公园最短路径问题中的数据元素有：（1）顶点数（2）边数（3）边的长度功能需求：要求完成以下功能：(1)输出顶点信息：将公园内各景点输出。（2）输出边的信息：将公园内每两个位置（若两个位置之间有直接路径）的距离输出。(3)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；(4)求最短路径：输出给定两点之间的最短路径的长度及途经的地点，输出任意一点与其他各点的最短路径。（5）删除：删除任意一条边。（6）插入：插入任意一条边。8最少换车次数问题1)问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。2)基本要求：求得从站0出发乘公交车至站n-1的最少换车次数。3)设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边i,j，权值为1。因此，从站x至站y的最少上车次数对应于图G中从顶点x到顶点y的最短路径长度。9文章编辑1)问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。2)基本要求静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；10哈希表设计1)问题描述针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。2)基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。3)测试数据取读者周围较熟悉的30个人名。4)选作内容（1）从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。（2）研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。（3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。11二叉排序树的遍历1)问题描述输入树的各个结点，建立二叉排序树，对建立的二叉排序树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。2)基本要求(1)用菜单实现(2)输入树的各个结点，建立二叉排序树，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。12个人帐簿管理系统设计1)问题描述个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。2)基本要求（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；（3）进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。13学分管理程序1)问题描述请设计一个学生的学分管理程序。假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。学分信息应该包括学号、姓名、课程类别、学分等。2)基本要求该程序应该具有下列功能：(1)通过键盘输入多个学生的学分，存入数据文件中；(2)给定学号，显示某位学生的学分完成情况；(3)给定某个班级的班号，显示该班所有学生学分完成情况；(4)给定某位学生的学号，修改该学生的学分信息；(5)按照某类课程的学分高低进行排序；(6)提供一些统计各类信息的功能。14学生作业完成情况管理程序1)问题描述请设计一个学生作业完成情况管理程序。假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。作业登记信息应该包含：学号、姓名、10次作业的完成情况。2)基本要求该程序应该具有下列功能：(1)通过键盘输入某位学生某次作业的分数；(2)给定学号，显示某位学生作业完成情况；(3)给定某个班级的班号，显示该班所有学生的作业完成情况；(4)给定某位学生的学号，修改该学生的作业完成信息；(5)给定某位学生的学号，删除该学生的信息；(6)按学生的最终平时成绩进行排序；(7)输出平均分数。（8）用数据文件保存作业登记信息。15学生籍贯管理系统1)问题描述编制一个学生籍贯信息记录簿，每个学生信息包括：学号、姓名、籍贯、通信地址。2)基本要求该程序应该具有下列功能：（1）输入学生信息并以磁盘文件保存；（2）读取磁盘文件并显示输出所有学生的籍贯信息；（3）按学号或姓名查询其籍贯；（4）按籍贯查询并输出该籍贯的所有学生；（5）能添加、删除和修改学生的籍贯信息；（6）显示输出天津籍和非天津籍学生的信息并可分别存盘；（7）按学号进行排序。16等价类实现及其应用1)问题描述某工厂有一台机器能够执行n个任务，任务i的释放时间为ri（是一个整数），最后期限为di（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。2)基本要求使用等价类实现以上机器调度问题，等价类分别采取两种数据结构实现。17串的查找和替换1）问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。2）基本要求编写字符串的模式匹配程序，实现字符串的查找替换功能18迷宫问题1)问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。2)基本要求(1)设计数据结构存储迷宫；(2)设计存储结构保存从入口到出口的通路；(3)设计算法完成迷宫问题的求解；(4)分析算法的时间复杂度。19TSP问题（回溯法求解）1)问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2)基本要求(1)上网查找TSP问题的应用实例；(2)分析求TSP问题的全局最优解的时间复杂度；(3)设计一个求近似解的算法；(4)分析算法的时间复杂度。20医院选址问题1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2)基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度。21机器调度问题1)问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：(1)一台机器在同一时间内只能处理一个作业；(2)一个作业不能同时在两台机器上处理；(3)作业i一旦运行，则需要ti个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。2)基本要求(1)建立问题模型，设计数据结构；(2)设计调度算法，为每个作业分配一台可用机器；(3)给出分配方案。22个人电话号码查询系统1)问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。2)基本要求(1)使用文件保存电话号码信息；(2)设计数据结构存储电话号码信息；(3)提供查询功能：根据姓名实现快速查询；(4)提供其他维护功能：例如插入、删除、修改等；(5)按电话号码进行排序。23数制转换任意给定一个M进制的数x，请实现如下要求1)求出此数x的10进制值（用MD表示）2)实现对x向任意的一个非M进制的数的转换。3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。24学生搭配1)问题描述一班有m个女