信息与计算科学级数据结构集中上机安排.docVIP

信息与计算科学08级 《数据结构集中上机》安排 一．时间、地点安排 2009-2010第一学期第16周，下表时间段为实验调试时间，其余时间准备。 上午为：8：00~11：00，下午：14：00~17：00；晚上：19：00~22：00 课程编号 专业 班级 人数 周次 教师 机房 时间 041109 信息与计算科学 0430701 27 16 纪良浩 S311B 下午 041109 信息与计算科学 0430702 29 16 纪良浩 S311B 晚上 041205 信息与计算科学 0430703 30 16 黎贵友 S319B 上午 周五检查程序并提交学生按照的具体要求所开发的所有源程序ftp://s@23/《集中上机》-数理学院 二、要求 1、在后面的课题表中列出了多个设计课题，每个课题都有相应的要求或说明。学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题。若学生对课题表以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。 2 、 关于设计的总要求 ：在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 3 、 验收 ：在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 4 、 设计报告 ：设计结束后要写出课程设计报告，以作为整个集中上机评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下： 简述题目要解决的问题是什么，并说明输入和输出数据的形式。 简述存储结构和算法的基本思想。 列出调试通过的源程序。 列出上面程序对应的运行结果。 分析程序的优缺点、时空性能以及改进思想，写出心得体会。 三、成绩评定 ： 课程设计的成绩评定以选定课题的难易度、完成情况和设计报告为依据综合评分。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 三、数据结构集中上机课题表 排序算法性能分析（95分） 编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。校园导航问题设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）和路径长度迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；　　 停车场管理（95分） 问题描述： 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 基本要求 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 测试数据 设n=2，输入数据为：（‘A’,1,5）,（‘A’,2,10）,（‘D’,1,15）,（‘A’,3,20）,（‘A’,4,25）,（‘A’5,30）,（‘D’,2,35）,（‘D’,4,40）,（‘E’,0,0）。其中：‘A’表示到达（arrival）；‘D’表示离去（departure）；‘E’表示输出结束（end）。 实现提示 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 选作内容 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占