附件一、软件实习2（数据结构）要求1. 学生必须仔细阅读软件实习2（数据结构）方案，认真主动完成软件实习2（数据结构）的要求。
有问题及时主动通过各种方式与教师联系沟通。
2. 学生要发挥自主学习的能力，充分利用时间，安排好软件实习的时间计划，并在软件实习过程中不断检测自己的计划完成情况，及时向教师汇报。
3. 软件实习2（数据结构）按照教学要求需要两周时间完成，两周中每天至少要上2小时的上机来调试C或C++语言设计的程序。
学院安排上机时间学生不得缺席。
二、上交相关内容要求上交的成果的内容必须由以下三个部分组成，缺一不可。
1. 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2. 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3. 软件实习2（数据结构）报告，格式如下。
一、封面课程名：软件实习2课程号：19ZZ0009b-0学号：姓名：二、目录如：1、停车场管理 (1)2、线索二叉树 (10)三、内容1、停车场管理（一）设计题目（二）需求分析在该部分中叙述，每个模块的功能要求。
（三）概要设计算法设计说明（包括算法设计思想、算法设计分析、流程图等）、每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
（四）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。
要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
（五）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
2、线索二叉树（一）设计题目（二）需求分析……四、总结软件实习2（数据结构）过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在软件实习2（数据结构）过程中对《数据结构》课程的认识等内容。
软件实习2（数据结构）任务书学期：13-14-2 班级：计算机12455361/2一、软件实习2（数据结构）目的软件实习2（数据结构）是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
本软件实习的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、设计要求1、通过这次软件实习，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2、学生必须仔细研读软件实习2（数据结构）要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。
3、本次软件实习按照教学要求需要在二周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好软件实习的时间计划，并在软件实习过程中不断检测自己的计划完成情况，及时地向指导教师汇报。
4、编程语言任选。
三、设计选题选题说明：前面5个为必做题（全做可达60分），后面题目为选做题，根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，确保及格，力争多做。
1、集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。
【基本要求】(1) 集合的元素限定为小写字母字符[…a‟..‟z‟] 。
(2) 演示程序以用户和计算机的对话方式执行。
【实现提示】以链表表示集合。
【选作内容】(1) 集合的元素判定和子集判定运算。
(2) 求集合的补集。
(3) 集合的混合运算表达式求值。
(4) 集合的元素类型推广到其他类型，甚至任意类型。
2、病人就医管理【问题描述】病人到医院看病，排队看医生的情况，在病人排队过程中，主要发生两件事：（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。
（2）护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。
试为医院编制按上述要求进行管理的模拟程序。
【基本要求】程序采用菜单方式，其选项及功能说明如下：（1）排队------输入病人的病历号，加入到病人排队队列中（2）就诊-------病人排队队列中最前面的病人就诊，并将其从队列中删除。
（3）查看排队------从队首到队尾列出所有的排队病人的病历号。
（4）下班---------退出运行。
3、校园导游咨询【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。
4、散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。
【基本要求】（1) 设每个记录有下列数据项：用户名、电话号码、地址；（2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；（3) 采用一定的方法解决冲突；（4) 查找并显示给定电话号码的记录；【选作内容】（1) 系统功能的完善；（2) 设计不同的散列函数，比较冲突率；（3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
5、排序综合【问题描述】利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
【基本要求】（1）至少采用三种方法（希尔排序、快速排序、堆排序）实现上述问题求解；（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；（3）统计每种算法所用的比较次数和交换次数，最后列表显示；（4）如果采用4种或4种以上的方法者，可适当加分。
6、一元稀疏多项式的计算（*）【问题描述】实现两个多项式的运算（相加、相减）。
【基本要求】（1）按照指数降序排列建立并输出多项式（2）完成两个多项式的相加、相减，并将结果输出（3）以链式存储结构实现多项式。
7、停车场管理（*）【问题描述】设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
试为停车场编制按上述要求进行管理的模拟程序。
【基本要求】以栈模拟停车场，以队列模拟车场外的便道。
每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。
栈以顺序存储结构实现，队列以链表结构实现。
8、纸牌游戏（*）【问题描述】编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？【基本要求】至少采用两种不同的数据结构的方法实现。
9、敢死队问题（*）【问题描述】有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。
如果前一个战士没完成任务，则要再派一个战士上去。
现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。
如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。
以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
【基本要求】至少采用两种不同的数据结构的方法实现。
10、猴子选大王（*）【问题描述】一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
【基本要求】（1）输入数据：输入m,n。
m,n 为整数，n<m（2）输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能（3）至少采用两种不同的数据结构的方法实现。
11、文章编辑（*）【问题描述】输入一页文字（静态存储一页文章，每行最多不超过80个字符，共N行），程序可以统计出文字、数字、空格的个数。
【基本要求】（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
（4）存储结构使用线性表，分别用几个子函数实现相应的功能；（5）输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
（6）输出形式：1）分行输出用户输入的各行字符；2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"3）输出删除某一字符串后的文章；12、迷宫求解（*）【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【基本要求】（1）首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。
（2）求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。
13、走迷宫游戏（*）【问题描述】程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。
游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。