1.舞伴问题问题描述：一班有m个女生、n个男生(m不等于n),举办一场舞会。男女生分别编号坐在舞池两边的椅子上，每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号），并能够处理异常情况，如文件为空、只有男生或只有女生等情况。原始数据和结果数据必须保存到文件中。测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据。提高要求：计算出任意一位男生(编号为X)和任意一位女生(编号为Y),在第K曲配对跳舞的情况。考核要求：用队列表示男、女学生，能够从文件中读取数据，文件中至少包括三组测试数据，分别为男生多于女生、女生多于男生、男女生人数相等。顺序输入舞曲的编号，对于每支舞曲，输入配对跳舞的男、女学生信息，并把本支舞曲的配对情况保存到文件中。完成上述任务，成绩为及格。在完成考核要求（1）的基础上，能够直接输出第K支舞曲的配对情况，且完成质量好，成绩为中等。
3.计算表达式的值(*)问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运算符（包括：“+”、“-”、“*”、“/”、“%”（求余运算）、“^”（乘幂运算））和括号，编写程序计算表达式的值。基本要求：从键盘输入一个正确的中缀表达式，计算后缀表达式的值，且能够实现将中缀表达式转换为对应的后缀表达式。对于表达式中的简单错误，能够给出提示，并给出错误信息；表达式中可以包括单个字母表示的变量。测试数据：任意选取一个符合题目要求的表达式。提高要求：实现一个包含简单运算和函数运算且有图形用户界面的小型计算器。考核要求：表达式中的数据可以是整数或小数，达到基本要求，成绩为中等及以下。在达到基本要求的基础之上，完成提高要求，且质量较好，难度较大，成绩可以酌情为良好或优秀。
5.家族族谱问题（*）问题描述：人类学家对于家族族谱很感兴趣，研究人员搜集了一些家族的家谱进行研究。由于人员太多只能用计算机辅助处理，研究人员将家谱转换为文本文件，下面为家谱的一个实例：
JohnRobertFrankAndrewNancyDavidRose
家谱文件中，每一行代表一个人名，第一行的名字是家族最早的祖先，家谱仅包含最早祖先的后代。每个人的子女比父母右缩两个空格。基本要求：按示例输入家族关系，建立家族族谱；输入任意两个人名，能判断出两个人的关系（双亲和子女的关系，兄弟姐妹的关系，祖父母和孙辈的关系）；事先有存好的家谱图的文件，从文件中读取后再对（2）进行判断。提高要求：（4）输入两个人之间的关系能判断关系是否准确，例如输入：NancyistheparentofRose,能给出True的判断；陈述句的格式如下：
XisachildofYXistheparentofYXisasiblingofYXisadescendantofYXisanancestorofY
（5）判断关系的陈述句存在文件中，从文件中读取后依次给出True或False的判断。测试数据：要求至少建立5层的家族关系。考核要求：达到基本要求（1）～（3），成绩为中等，否则向下浮动；达到提高要求（4）（5）成绩为良好。
6.铺设地下管道问题（*）问题描述：某城市要给该地区铺设地下管道，现有该地区n个管道口之间的距离网，假设铺设管道的经济代价与其距离成正比，设距离一千米其代价为十万元，要求计算使地下管道连通的最小代价。基本要求：地下管道的网络图采用邻接矩阵或邻接表表示，若管道口之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求显示得到一种铺设方案包括了哪些管道，并求出其代价。要求至少10个管道口，20条管道。提高要求：（3）给出所有代价最低的管道铺设方案；（4）假设某个管道堵塞了，现在要马上铺设临时管道，给出临时管道的铺设方案，并求出铺设了临时管道后其代价。考核要求：达到基本要求（1）～（2），成绩为中等，否则向下浮动；达到提高要求（3）（4），且质量较好，成绩酌情为良好。
12.迷你搜索引擎（）**问题描述：实现一种简单的搜索引擎功能，快速满足多达10^3条关键字查询请求。给出正整数N(≤100),为文档总数。随后按以下格式输入每个文档的内容:第一行给出文件的标题,随后给出不超过100行的文件正文,最后在一行中只给出一个字符“#”,表示文件结束。在N个文档内容结束之后,给出查询总数M(≤10^3),随后M行,每行给出不超过10个英文单词,其间以空格分隔,每个单词不超过10个英文字母,不区分大小写。针对每一条查询,在一行中输出包含全部该查询单词的文件总数，并输出这些文档的标题;如果总数为0,则输出“NotFound”。基本要求：（1）建立单词与文档的一种索引数据结构（例如：倒排索引）,索引结构中不仅要记录该单词出现在哪些文档里,还要记录出现在该文档的哪几行；（2）能够正确输出所查询的关键字所包含的文档；(3)能够通过文件读取的方式实现上述功能，即文档和关键字都通过文件读取方式操作；（4）能够实现搜索的and功能，即找到同时满足多行查询条件的文档，并实现上述全部要求。测试数据：学生可以自己建立所需要的测试数据。考核要求：完成任务（1）～（2），成绩为良好；完成任务（3）～（4），成绩为优秀。
15.社交网络图中的结点“重要性”计算（**）问题描述：在社交网络中，个人（结点）通过某些关系（边）联系起来，某些人之间有关联，而某些人之间没有。根据结点所处位置不同，其在网络中体现的重要性也不尽相同。“紧密度中心性”是用来衡量一个结点到达其它结点“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地到达网络中的其它结点，因而在网络的传播中有更重要的价值。在有N个结点的网络中，结点的“紧密中心性”定义为到其余所有结点的最短距离的平均值的倒数。
测试数据：输入若干行数据，每一行输入2个数字分别代表两个结点之间有边连接。基本要求：给定一个无权值的无向图以及其中的一组结点，要求结点个数N至少为9个，计算每个结点的紧密度中心性，并求出网络传播中最重要的结点。把结点之间的关系存入文件中，从文件中调入数据并求出网络传播中最重要的结点；（3）把结点之间的关系用图表形式显示出来，且界面设计效果较好。考核要求：能解决（1）可为中等，解决(1)（2）酌情为良好，解决（1）-（3）酌情为优秀。提示：结点多而边少可考虑使用邻接表存储数据，因边没有权值可利用广度优先搜索确定最短路径，也可当作权值为1的带权图利用求最短路径的算法求解。
16.城市的水网设计问题（**）问题描述：假设某城市规划新区，需要设计新区水网系统，以满足整个新区未来的水需求。新区由多个区域组成，每个区域都有一定数量的居民。为了给每个区域提供清洁的水，需要设计一个网络系统，包括泵站和管道，将水从水源地输送到各个区域。要求你设计一个算法，用于找出从泵站到各个区域最短的配送路线。基本要求：1.要求新区包括的区域不少于10个，通过文件读入泵站、各个区域的邻接和距离信息；2.使用一种存储结构来表示泵站和各个区域的距离信息。3.输出最短距离的管道铺设方案；提高要求：1.随机生成泵站、各个区域的邻接和距离信息；2.使用两种存储结构来表示水网。考核要求：达到基本要求1～3，成绩为良好，否则向下浮动；达到提高要求，且实现效果较好，可以为优秀。
备注：
四、应阅读的基本文献王红梅编著.数据结构——从概念到c实现（第2版），清华大学出版社，2023.3袁嵩.数据结构实践教程.华中科技大学出版社，2019.10严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,2011.11殷人昆等.数据结构（用面向对象方法与C++描述）（第2版）.清华大学出版社，2012.9
五、考核方式（包括总成绩的组成及分配比例）课程设计总成绩=平时成绩（20%）+报告（20%）+代码验收（40%）+答辩（20%）题目中给出的考核要求，相应的成绩仅仅是上机验收部分，课程设计总成绩要结合学生的实践能力、独立分析解决问题的能力、团队合作能力和创新精神，总结报告和答辩水平以及学习态度综合考评。其中团队合作需要学生每组填写“项目实施进度管理表”（见附件1），根据完成情况进行成绩评定；总结报告格式见附件2，学生打印总结报告时，需将《数据结构与算法》课程设计考核表（见附件3）一并打印，并反面装订。