下载文档原格式
数据结构课程设计题目一、题目背景在现代科技发展的背景下，数据结构作为计算机科学的重要基础课程，对于培养学生的编程思维、数据处理能力具有重要的作用。
本篇课程设计将围绕数据结构的实际应用，设计一个能够提升学生数据结构理论与实践能力的题目。
二、题目描述你需要设计一个软件，实现以下功能：能够记录学生信息并进行相关的数据操作。
具体要求如下：1. 学生信息包括：学生学号、姓名、性别、年龄、身高、体重等基本信息；2. 软件需要实现以下操作：a. 添加学生信息：可以手动添加每个学生的详细信息，并将其记录到数据库中；b. 删除学生信息：能够根据学号或姓名删除指定学生的信息；c. 修改学生信息：能够根据学号或姓名修改指定学生的信息；d. 查询学生信息：能够按照学号、姓名、性别、年龄等条件进行学生信息的查询，并将结果以列表形式展示；e. 统计学生信息：能够统计学生的平均年龄、平均身高、平均体重等统计数据，并展示在界面上；f. 数据导入导出：能够将学生信息导入/导出到文件或数据库中，实现数据的持久化存储。
三、设计思路为了实现上述功能，你可以采用以下的设计思路：1. 数据结构选择：可以使用链表、数组、树等数据结构存储学生信息，具体根据功能需求来选择合适的数据结构；2. 界面设计：考虑采用图形界面或者命令行界面，以提供方便的操作方式；3. 数据存储：可以使用文件、数据库等方式进行数据的存储和读取，以实现数据的持久化；4. 算法设计：在实现功能的过程中，需要考虑合适的算法来实现快速的查找、删除和修改等操作；5. 错误处理：在设计过程中，需要考虑各种可能的错误情况，并进行相应的处理和提示。
四、实施步骤为了顺利完成该课程设计，你可以按照以下步骤进行：1. 分析题目需求：仔细阅读以上题目描述，明确实现各项功能的具体要求；2. 设计数据结构：选择合适的数据结构来存储学生信息，考虑数据的增删改查等操作的效率；3. 设计算法：根据功能需求，设计相应的算法来实现各项操作；4. 实现界面：根据选择的界面方式，设计相应的图形界面或命令行交互界面；5. 实现功能：按照题目要求，逐个实现各项功能，并进行测试；6. 完善细节：对界面进行美化，完善用户交互体验，处理各种错误情况；7. 测试与调试：对整个软件进行全面的测试，并进行调试修复可能存在的问题；8. 编写报告：撰写课程设计报告，详细记录设计过程、实现方法、遇到的问题以及解决方案等。
福建工程学院课程设计课程：数据结构课程设计题目： 1.综合应用2.折半查找3.快速排序专业：软件工程班级：1101座号：3110305129姓名：潘聪2012 年 6 月26 日设计题目1：综合应用一、问题描述有N名学生，每名学生含有如下信息：学号、姓名、某四门课的成绩，并计算其总分，用一结构数组表示之。
然后实现以下功能：（1）将这些数据存放至文件stuf.dat中；（2）将文件中的数据读出至结构数组中，并显示之；（3）输出总分最高分和最低分的名字；（4）输出总分在340分，单科成绩不低于80分的名单；（5）求出各科平均分数；（6）按总分排名；（7）输出补考名单。
二、解决问题的算法思想描述（1）子函数：首先确定需要的子函数，总共7个，对应的功能分别是题目要求的七项（2）主函数：主函数中，要设计出易于使用的人机界面，就必须要用到switch 。
（3）文件的存放读取，必须要用到文件的函数，fopen，fread，fclose等。
（4）把每个学生的信息定义在一个结构数组中，利用结构数组更加方便。
（5）各科成绩排名用冒泡排序即可。
（6）输出总分，补考名单，各科的平均分都比较简单。
三、设计1. 数据结构的设计和说明//定义结构体typedef struct{int num; //学号char name[10]; //姓名int score1; //语文int score2; //数学int score3; //物理int score4; //化学}student;student stu[MAX]; //结构数组2．模块结构图及各模块的功能：3. 关键算法的设计（必须画出流程图）打印最高成绩和最低成绩的名单算法流程图：四、测试数据及测试结果：五、课程设计总结注意细节方面，任何一个小问题都不能忽视，才能最终解决问题。
六、关键源程序的清单关键算法一：按照总成绩排名：void paiming(){read();student x;int sum[MAX],t=0,i,m,n,j;for(i=0;i<MAX; i++){sum[i]=stu[i].score1+stu[i].score2+stu[i].score3+stu[i].score4;}for(m=0;m<MAX-1;m++)for(n=m+1;n<MAX;n++)if(sum[n]>sum[m]){t=sum[n];sum[n]=sum[m]; //总成绩交换sum[m]=t;x=stu[n];stu[n]=stu[m]; //总成绩对应的学生也要同时交换stu[m]=x;}printf("学号\t姓名\t语文\t数学\t英语\t物理\t总分\t名次\n");for(j=0;j<MAX;j++){printf("%-8d%-8s%-8d%-8d%-8d%-8d%-8d%-8d\n",stu[j].num,stu[j].name,stu[j].score1,stu[j].sc ore2,stu[j].score3,stu[j].score4,sum[j],j+1);}}关键算法二：打印出最高成绩和最低成绩的姓名：void maxmin(){int sum[MAX],i,j,m=0,n=0,max,min;read();for(i=0;i<MAX; i++){sum[i]=stu[i].score1+stu[i].score2+stu[i].score3+stu[i].score4;} //求书每个人的总分max=min=sum[0]; //用一维数组保存成绩，并且先令第一位学生的成绩作为最高分和最低分for(j=0;j<MAX;j++){if(sum[j]>max){m=j;max=sum[j]; //定义变量m，n分别保存最高分和最低分的下标}else if(sum[j]<min){n=j;min=sum[j];}}printf("\n最高分：%s 总分%d\n",stu[m].name,sum[m]);printf("\n最低分：%s 总分%d\n\n",stu[n].name,sum[n]);}设计题目2：折半查找一、问题描述用折半查找法，实现对任意一组数据的查找。
数据结构课程设计实例100例1. 设计一个简单的栈数据结构。
2. 实现一个简单的队列数据结构。
3. 设计一个链表数据结构。
4. 实现一个二叉树数据结构。
5. 设计一个哈希表数据结构。
6. 实现一个图数据结构。
7. 设计一个堆数据结构。
8. 实现一个优先队列数据结构。
9. 设计一个有向图数据结构。
10. 实现一个循环链表数据结构。
11. 设计一个红黑树数据结构。
12. 实现一个字典数据结构。
13. 设计一个AVL树数据结构。
14. 实现一个散列表数据结构。
15. 设计一个双端队列数据结构。
16. 实现一个字典树数据结构。
17. 设计一个多叉树数据结构。
18. 实现一个最小生成树算法。
19. 设计一个并查集数据结构。
20. 实现一个图的遍历算法。
21. 设计一个迪杰斯特拉算法。
22. 实现一个Floyd算法。
23. 设计一个拓扑排序算法。
24. 实现一个最短路径算法。
25. 设计一个Kruskal算法。
26. 实现一个插入排序算法。
27. 设计一个快速排序算法。
28. 实现一个希尔排序算法。
29. 设计一个选择排序算法。
30. 实现一个冒泡排序算法。
31. 设计一个堆排序算法。
32. 实现一个归并排序算法。
33. 设计一个桶排序算法。
34. 实现一个基数排序算法。
35. 设计一个计数排序算法。
36. 实现一个递归算法。
37. 设计一个动态规划算法。
38. 实现一个回溯算法。
39. 设计一个哈夫曼编码算法。
40. 实现一个最大子序列和算法。
41. 设计一个最长递增子序列算法。
42. 实现一个最长公共子序列算法。
43. 设计一个贪婪算法。
44. 实现一个深度优先搜索算法。
45. 设计一个广度优先搜索算法。
46. 实现一个信号量算法。
47. 设计一个分治算法。
48. 实现一个枚举算法。
49. 设计一个置换算法。
50. 实现一个位运算算法。
51. 设计一个红黑树插入算法。
52. 实现一个二进制查找算法。
53. 设计一个最小堆插入算法。
济南大学 - 计11 - 数据结构课程设计题目济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目带结点记录的线性链表操作的实现设计小组成员设计目的：掌握线性链表的建立；掌握线性链表的结点定义；掌握线性链表的基本操作。
设计内容：利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、显示、保存、退出，并能在屏幕上输出操作前后的结果。
设计要求： 1. 结点定义包括：书名，作者，出版社，ISBN(13位，主关键码) 2. 查询包括：按书名查询、按作者查询、按书号查询。
作者相同是列出全部记录，作者和书名能实现模糊查询（含有某些子串的）。
3. 书写设计报告，叙述主要算法。
参考文献： 1. 严蔚敏, 陈文博. 数据结构及应用算法教程, 清华大学出版社, 2021 2. 严蔚敏. 数据结构（C语言版）, 清华大学出版社, 2021 3. 朱振元. 数据结构――C++语言描述, 清华大学出版社, 2021 4. 潘玉奇, 刘明军. 程序设计基础(C语言)实验指导, 清华大学出版社, 2021 济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目带结点记录的集合操作的实现设计小组成员设计目的：掌握用线性链表表示的集合的建立；掌握线性链表的结点定义；掌握集合的基本操作。
设计内容：利用线性链表实现集合操作，具体功能：集合的输入、显示、元素排序、交、差、并、对称差、程序退出，并能在屏幕上输出操作前后的结果。
设计要求： 1. 结点定义包括：英语词汇(主关键码)，词性，汉语 2. 基本操作：输入两个集合，按英语词条对两个集合进行排序、交集、差集、并集、对称差集的求解。
3. 书写设计报告，叙述主要算法。
参考文献： 1. 严蔚敏, 陈文博. 数据结构及应用算法教程, 清华大学出版社, 2021 2. 严蔚敏. 数据结构（C语言版）, 清华大学出版社, 2021 3. 朱振元. 数据结构――C++语言描述, 清华大学出版社, 2021 4. 杨波, 刘明军. 程序设计基础(C语言), 清华大学出版社, 2021 5. 潘玉奇, 刘明军. 程序设计基础(C语言)实验指导, 清华大学出版社, 2021 济南大学信息科学与工程学院数据结构课程设计Practicum for Data Structure课程设计题目表达式求值（计算器）设计小组成员设计目的：熟悉栈类型的数据结构和运算符重载。
算法与数据结构课程设计一、线性表题1、建立一个单链表，显示链表中每个节点的数据，并做删除和插入处理。
例：（掌握线性表在链式存储结构下的基本运算的实现。
）1、功能（1）建立以带头结点的单链表（2）显示链表中每个结点的数据（3）在单链表中指定位置插入指定数据并输出单链表中所有数据（4）删除单链表中指定的结点并输出单链表中所有数据2、输入要求输入单链表中所有数据，插入的数据元素的位置、值，要删除的数据元素的位置。
3、测试数据单链表中所有数据：12，23，56，21，8，10，15，67，90，32插入的数据元素的位置、值：1，28要删除的数据元素的位置：10[概要设计]（1）算法思想：由于在操作过程中要进行插入、删除操作，为运算方便，选用单带头结点的单链表作数据元素的存储结构。
对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。
（2）数据结构单链表结点类型：typedef struct Node{ int data;struct node *next;}ListNode;带头结点的单链表类型定义：typedef ListNode *LinkList;（3）模块划分：①建立点头结点的单链表CreatLinkList;②显示链表中每个结点的数据PrintList；③在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList;④删除单链表中指定的结点并输出单链表中所有数据DeleteList;⑤主函数mian()，功能是给出测试数据值，建立测试数据值的带头结点的单链表，调用PrintList函数、InsertList函数、DeleteList函数实现问题要求。
[详细设计] 见程序LinkList.c题2、约瑟夫环（Joseph）问题的一种描述是：编号1，2，┉，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数），一开始，任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
安徽大学计算机科学与技术学院网络工程《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：38.病人看病模拟程序姓名：院系：计算机科学与技术学院专业：年级：学号：指导教师：20_10__年__9_月__27_日安徽大学计算机科学与技术学院网络工程专业数据结构课程设计结果评定目录1 课程设计的目的 (1)2 需求分析 (1)3 课程设计报告内容 (2)3.1 概要设计 (2)3.2 详细设计 (2)3.3 函数调用关系图 (4)3.4 程序清单 (5)3.5 运行结果 (5)4 总结 (7)参考文献 (7)附录 (8)38.病人看病模拟程序1.课程设计的目的一般来讲，课程设计实验要复杂一些，深度更广并且更加接近实用。
目的是通过课程设计的综合训练，培养我们实际分析问题、编程和动手能力，使我们对数据结构进行更深一层的了解，培养我们对学习数据结构这门课程的兴趣，也为以后的大学毕业设计论文打下了一个初步的基础。
其基本目的有：（1）基本掌握面向过程程序设计的基本思路和方法；（2）达到熟练掌握数据结构的基本知识和技能；（3）能够利用所学的基本知识和技能，解决简单的程序设计问题。
2.需求分析编写一个程序，反映病人到医院看病，排队看医生的情况。
在病人排队过程中，主要重复两件事：（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。
（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。
要求模拟病人等待就诊这一过程。
程序采用菜单方式，其选项及功能说明如下：（1）排队——输入排队病人的病历号，加入到病人排队队列中。
（2）就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除。
（3）查看排队——从队首到队尾列出所有的排队病人的病历号。
（4）不再排队，余下顺序就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行。
（5）下班——退出运行。
3.课程设计报告内容3.1概要设计：（1）.抽象数据类型图的定义如下：此程序采用队列数据结构，存储结构为单链表，采用此种结构一方面可以减少数据复杂程度，增加系统稳定性；另一方面，利用动态分配内存的方法，便于内存管理，充分利用内存空间。
数据结构课程设计题目及要求一、要求本次课程设计可以从以下的题目中任选其一，每个题目基本实现的要求是：有菜单功能有读写数据存盘功能成品应包括以下内容：程序设计书（Word格式）。
包括程序设计目标、问题描述、需求分析、概要设计、详细设计、源程序清单（要求格式整齐400行以上，要有注释说明）、软件说明书（给出软件如何使用，使用时的注意事项）、测试报告（每个函数的功能测试，输入条件，输出结果）和课程设计总结。
2、可执行程序源代码。
3、答辩时使用的ppt。
二、设计题目题目一：仓库管理系统（线性表应用）[问题描述]建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物以及建立新的仓库存储系统。
[实现提示]可以采用双向链表的存储结构，如可定义如下的存储结构：typedef struct dnode /*定义双向链表结构体*/{int number; /*货物编号*/char name[max]; /*货物名称*/int counter; /*货物数量*/struct dnode *prior,*next; /*定义两指针，分别指向其前驱和后继*/}dlnode;题目二：单位员工通讯录管理系统（线性表应用）[问题描述]为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。
其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。
[实现提示]可以采用单链表的存储结构，如可定义如下的存储结构：typedef struct { /*员工通讯信息的结构类型定义*/char num[5]; /*员工编号*/char name[10]; /*员工姓名*/char phone[15]; /*办公室电话号码*/char call[15]; /*手机号码*/}DataType;/*通讯录单链表的结点类型*/typedef struct node{ DataType data; /*结点的数据域*/struct node *next; /*结点的指针域*/}ListNode,*LinkList;题目三: 哈夫曼编码/译码系统（树应用）[问题描述]利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。
选题一：迷宫与栈问题【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【任务要求】1)首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i，j，d）的形式输出。
其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
2)编写递归形式的算法，求得迷宫中所有可能的通路。
3)以方阵形式输出迷宫及其通路。
【测试数据】迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。
出口出口选题二：算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。
写一个程序，实现基于二叉树表示的算术表达式的操作。
【任务要求】假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。
实现以下操作：1)ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。
2)WriteExpre(E)—用带括弧的中缀表达式输出表达式E。
3)Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。
4)Value(E)—对算术表达式E求值。
5)CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）【测试数据】1)分别输入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。
2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。
选题三：银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：00am，关门5：00pm）起不断有客户进入银行。
数据结构课程设计题目课程设计题一：线性表子系统一．设计目的：1.掌握线性表的特点2.掌握线性表的顺序存储结构和链式存储结构的基本运算3.掌握线性表的基本操作二．设计内容和要求：1.设计一个选择式菜单。
线性表子系统******************************************************* 1 ……建表** 2 ……插入** 3 ……删除** 4 ……显示** 5 ……查找** 6 ……求表长** 0 ……返回*******************************************************请选择菜单号（0…6）：2.采用单链表创建线性表。
3.在线性表中实现插入、删除元素，显示线性表中所有元素，查找元素和求线性表长的基本操作。
课程设计题二：栈子系统一．设计目的：1.掌握栈的特点及其描述方法2.掌握链式存储结构实现一个栈3.掌握链栈的各种基本操作4.掌握栈的典型应用的算法二．设计内容和要求：1.设计一个选择式菜单。
栈子系统****************************************************** * 1 ……入栈* * 2 ……出栈* * 3 ……显示* * 4 ……数制转换* * 0 ……返回* ****************************************************** 请选择菜单号（0…4）：2.设计一个整型数据元素的链栈。
3.编写入栈、出栈和显示栈中全部元素的程序。
4.编写一个把十进制数转换成八进制数的应用程序。
课程设计题三：队列子系统一．设计目的：1.掌握队列的特点及其描述方法2.掌握链式存储结构实现一个队列3.掌握队列的各种基本操作4.掌握队列简单应用的算法二．设计内容和要求：1.设计一个选择式菜单。
队列子系统******************************************************* 1 ……入队** 2 ……出队** 3 ……读队首元素** 4 ……显示** 5 ……报数问题** 0 ……退出*******************************************************请选择菜单号（0…5）：2.设计一个整型数据元素的链队列。
数据结构课程设计题目以下7个题目任选其一。
1．排序算法比较利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且（1）统计每一种排序上机所花费的时间。
（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。
（3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动)。
（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。
2．图的深度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。
画出搜索顺序示意图。
3．图的广度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。
画出搜索顺序示意图。
4．二叉树的遍历对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
画出搜索顺序示意图。
5．链表操作利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
画出搜索顺序示意图。
6．一元稀疏多项式简单计数器（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。
序列按指数降序排列。
（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。
（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。
用带头结点的单链表存储多项式。
测试数据：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。
《算法与数据结构》课程设计题目学生从下列题目中自主选择任意一个题目，集中在一周之内（共24学时），完成设计和调试任务。
题目一：图结构及其应用：熟悉图的各种存储结构（特别是邻接矩阵和邻接表）。
设计一个交通咨询系统，用两种方法求得最短路径。
此外建立一个AOE网，求得关键路径。
题目二、航班信息的查询与检索：综合利用排序和查找的方法进行设计，可以涉及到文件的一般概念。
题目三、实现图书管理信息系统的设计。
这是一个数据结构的综合使用，涉及的知识比较全面，特别是对文件的使用更为全面。
题目四：二叉搜索树：各种搜索树效率比较题目要求：本题目要求对普通的二叉搜索树、A VL树分别实现指定操作，并分析比较这二种不同数据结构对应的一系列插入和删除操作的效率。
要求测试对N个不同整数进行下列操作的效率：●按递增顺序插入N个整数，并按同样顺序删除；●按递增顺序插入N个整数，并按相反顺序删除；●按随机顺序插入N个整数，并按随机顺序删除；要求N从1000到10000取值，并以数据规模N为横轴，运行时间为纵轴，画出二种不同数据结构对应的操作效率比较图。
题目五：并查集：检查网络题目要求：给定一个计算机网络及机器间的双向连线链表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机若存在一条连线路径，也可以进行间接的文件传输。
请设计算法和程序进行判断：任意指定两台计算机，它们之间是否可以进行文件传输？输入要求：输入由若干组测试数据组成。
对于每一组测试，第1行包含一个整数N（≦10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。
接下来的几行输入格式为I C1 C2或者C C1 C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试完毕。
输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。
当读到S时，检查整个网络。
若网络中任意两台机器间都可以传输文件，则在一行中输出“The network in connected,”，否则输出“There are k components.”，其中k是网络中连通集的个数。
两组测试数据之间请输出一空行分隔。
题目六：网络流：宇宙旅行题目要求：在走遍了地球上的所有景点以后，旅游狂人开始计划他的宇宙旅行项目。
经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数的列表。
当旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客驻留，旅客必须立刻转乘另一艘飞船离开，所以空间站不能接待超过自己最大容量的旅客流。
为了估计预算，现在旅游狂人需要知道终点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。
输入要求：输入由若干组测试数据组成。
每组测试数据的第1行包含旅行的起点星球和终点星球的名称和一个不超过500的正整数N（N为0标志全部测试结束，不要对该数据做任何处理）。
接下来的N行里，数据格式为：source i ,destination i,capacity i,其中source i和destination i 是卫星空间站的名称或起点、终点星球的名称，正整数capacity i是飞船从source i到destination i 一次能运载的最大旅客流量。
每个名称是由A-Z之间3个大写字母组成的字符串，例如ZJU。
测试数据中不包含任何到达起点星球的信息以及任何从终点星球出发的信息。
输出要求：对每一组测试，在一行里输出终点星球接待站应具有的最小容量，使得每艘飞船在到达时都可以保证让全部旅客下船。
题目七：最小生成树：室内布线题目要求：装修新房子是一项颇为复杂的工程，现在需要写个程序帮助房主设计室内布线的布局。
首先，墙壁上插座的位置是固定的。
插座间需要有电线相连，而且要布置得整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。
房主要求知道，要将所有插座连通，自己需要买的电线的最短长度。
另外，别忘了每个房间都有门，电线不可以穿门而过。
下图给出了一个有4插座的房间的电线布局。
输入要求：输入由若干组测试数据组成。
每组数据的第1行包含房间的长、宽、高和插座的个数N（N为一个不超过20的正整数）。
接下去的N行中，第i行给出第i个插座的位置坐标（x i,y i,z i）; 最后一行包含4个3元组（x1,y1,z1）…(x4,y4,z4),分别是长方形门框的4个角的三维坐标。
4个数字全部为0表示全部测试结束，不要对该数据做任何处理。
注意：这里假设长方体形状的房间完全位于三维直角坐标系的第一象限内，并且有一个角落在原点上。
地板位于x-y平面。
题目数据保证，每个插座仅属于四面墙中的一面，门上没有插座。
要求每段电线的两端必须仅与插座连接，电线之间不能互相交叉焊接。
输出要求：对每一组测试，在一行里输出要将所有插座连通需要买的电线的最短整数长度。
题目八：分治法：最小套圈设计题目要求：套圈游戏是游乐场中常见的游戏之一，其规则为：游戏者将手中的圆环套圈投向场中的玩具，被套中的玩具就作为奖品奖给游戏者。
现给定一个套圈游戏场的布局，固定每个玩具的位置，请你设计套圈的半径尺寸，使得它每次最多只能套中一个玩具。
但同时为了让游戏看起来更具有吸引力，这个套圈的半径又需要尽可能大。
把问题进一步简化，假设每个玩具都是平面上的一个没有面积的点，套圈是简单的圆。
一个玩具被套住，是指这个点到圆心的距离严格小于圆半径。
如果有两个玩具被放在同一个位置，那么输出的圆半径是0。
输入要求：输入由若干组是数据组成。
每组数据的第1行包含一正整数N（2≤N≤100000），代表场地中玩具的个数。
接下来有N行输入，每行包含一个玩具的x和y坐标。
当N为0时，表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组测试，在一行里输出符合设计要求的套圈的半径，精确到小数点后两位。
题目九：动态规划：商店购物题目要求：某商店促销中为顾客提供各种优惠，把若干种商品分成一组降价销售。
例如一朵花原价2元，一只花瓶原价5元，而用优惠券可以用5元买3朵花，用10元买2只花瓶加1朵花。
这时顾客买3朵花和2只花瓶只须付14元---用第2种优惠组合买2只花瓶加1朵花，再用原价买2朵花，所付费用最少。
请编写程序帮助收银员计算顾客所购商品应付的最少费用。
假定顾客手中优惠券都有充分多张，可将同一种券反复用任意多次。
例如，给定优惠券上写明3朵花售5元，则顾客买6朵花时可将此券用2次，只需付10元。
注意：收银员不能改变顾客的购物种类和数量，即使增加某些商品会使付款总数减少，也不允许收银员做任何改变。
输入要求：输入由2部分组成。
第1部分包含10000种商品的名称和价格，每一行以下列各式给出：［商品名称］价格其中商品名称由不超过60个字符切不包括“［”和“］”的字符串组成，价格是非负实数。
接下来的输入由若干组测试数据组成。
每组数据包含一张优惠券的N种组合优惠的描述和顾客购物清单。
其中优惠券的描述按如下格式给出：N（≤20）是优惠券中的商品组合方法的个数。
下面有N行，每行给出m［商品1］*n1 ［商品2］*n2…［商品m］* n m总价格表示该组合包含m种商品，其中商品i必须买n i（≤9）件，总的优惠价格是非负数实数总价格。
任何一张优惠券中涉及的不同商品数（N种组合涉及的所有商品数）不超过6件。
例如，样例输入中的21［flower］*3 5.002［flower］*1［vase］*2 10.00表示该优惠券包含2种组合方式，即：可以用5元买3朵花，用10元买2只花瓶加1朵花。
顾客购物清单的描述按如下格式给出：L（≤30）是不同商品的个数。
下面有L行，每行给出［商品名称］购买数量（≤9）例如输入例子中的2［flower］ 3［vase］ 2 表示该顾客要买3朵花和2只花瓶。
当N为负数时表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组测试，在一行里输出顾客应付的最少费用，精确到分。
题目十：熊猫烧香题目要求：“熊猫烧香”是在网络中传播的一种著名病毒，因为图标是一只可爱的熊猫而得名。
该病毒比较难以处理的一个原因是它有很多变种。
现在某实验室的网络就不幸感染了这种病毒。
从图中可以看到，实验室的机器排列为一个M行N列的矩阵，每台机器只和它相邻的机器直接相连。
开始时有T台机器被感染，每台遭遇的熊猫变种类型都不同，分别记为Type1, Type2…, Type t。
每台机器都具有一定级别的防御能力，将防御级别记为L（0＜L＜1000）。
“熊猫烧香”按照下列规则迅速在网络中传播：病毒只能从一台被感染的机器传到另一台没有被感染的机器。
如果一台机器已经被某个变种的病毒感染过，就不能再被其他变种感染。
病毒的传播能力每天都在增强。
第1天，病毒只能感染它可以到达的、防御级别为1的机器，而防御级别大于1的机器可以阻止它从自己出继续传播。
第D天，病毒可以感染它可以到达的、防御级别不超过D的机器，而只有防御级别大于D的机器可以组织它从自己出继续传播。
在同一天之内，Type1变种的病毒先开始传播，感染所有它可能感染的机器，然后是Type2变种、Type3变种……依次进行传播。
以下图为例说明传染的过程。
本题的任务是：当整个网络被感染后，计算有多少台机器被某个特定变种所感染。
输入要求：输入由若干组测试数据组成。
每组数据的第1行包含2个整数M和N（1≤M，N ≤500），接下来是一个M×N的矩阵表示网络的初始感染状态，其中的正、负数的意义如题目描述中所定义。
下面一行给出一个正整数Q，是将要查询的变种的个数。
接下去的Q行里，每行给出一个变种的类型。
当M或N为0时，表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组测试，在一行里输出被某个特定变种所感染的机器数量。
题目十一：神秘国度的爱情故事题目要求：某个太空神秘国度中有很多美丽的小村，从太空中可以想见，小村间有路相连，更精确一点说，任意两村之间有且仅有一条路径。
小村A中有位年轻人爱上了自己村里的美丽姑娘。
每天早晨，姑娘都有去小村B里的面包房工作，傍晚6点回到家。
年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。
问题是，他不能确定小村C是否在小村B到小村A之间的路径上。
你可以帮他解决这个问题吗？输入要求：输入由若干组测试数据组成。
每组数据的第1行包含-正整数N（1≤N≤50000），代表神秘国度中小村的个数，每个小村即从0到N-1编号。
接下来有N-1行输入，每行包含一条双向道路的两个端点小村的编号，中间用空格分开。
之后一行包含一正整数M（1≤M≤500000），代表着该组测试问题的个数。
