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

信息与计算科学08级 《数据结构集中上机》安排 一．时间、地点安排 2009-2010第一学期第16周，下表时间段为实验调试时间，其余时间准备。 上午为：8：00~11：00，下午：14：00~17：00；晚上：19：00~22：00 课程编号 专业 班级 人数 周次 教师 机房 时间 信息与计算科学 27 16 纪良浩 S311B 下午 信息与计算科学 29 16 纪良浩 S311B 晚上 信息与计算科学 30 16 黎贵友 S319B 上午 周五检查程序并提交学生按照题目的具体要求所开发的所有源程序和设计报告。 此安排表见： HYPERLINK ftp://s@23/ ftp://s@23/《集中上机》-数理学院 二、要求 1、在后面的课题表中列出了多个设计课题，每个课题都有相应的要求或说明。学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题。若学生对课题表以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。 2 、 关于设计的总要求 ：在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 3 、 验收 ：在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 4 、 设计报告 ：设计结束后要写出课程设计报告，以作为整个集中上机评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下： 简述题目要解决的问题是什么，并说明输入和输出数据的形式。 简述存储结构和算法的基本思想。 列出调试通过的源程序。 列出上面程序对应的运行结果。 分析程序的优缺点、时空性能以及改进思想，写出心得体会。 三、成绩评定 ： 课程设计的成绩评定以选定课题的难易度、完成情况和设计报告为依据综合评分。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 三、数据结构集中上机课题表 排序算法性能分析（95分） 编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 校园导航问题（95） 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）和路径长度，输出图形表示。 散列表实现学生情况表（85分） 设有学生情况表，每个记录有下列数据项：学号、姓名、性别、年龄。现使用散列表表示该学生情况表，并采用二次探测法解决冲突。试设计一个系统使之具有下列功能： 从一个文本文件中输入各记录（记录项用空格分隔）来建立散列表 有哪些信誉好的足球投注网站并显示给定学号的学生记录 删除一个学生记录 在多次删除后，重新整理学生情况表； 打印学生情况表 三件有制约关系物品过河问题（90分） 有一人要将自己的兔子、蔬菜和狐狸等三件物品运过河。但过河所用的船每次只能装其中的两件，而这三件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模型，并编程实现这一问题的求解。 设计和实现多项式运算（85分） 实现带头结点的单循环链表表示的多项式 设计和实现多项式相加和相乘运算算法 设计一个测试程序：测试多项式加法和乘法运算。要求： 建立一个多项式 打印（显示）一个多项式 实现两个多项式相加； 实现两个多项式相乘。 在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 迷宫求解（参见教材描述）（85分） 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；　　 运动会分数统计（95分） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20） 功能要求：1).可以输入各个项目的前三名或前五名的成绩； 2)．能统计各学校总分， 3)．可以按学校编号、学校总分、男女团体总分排序输出； 4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的