数据结构相关习题00001.doc

《数据结构项目实践集中上机》任务书 dasdas三、要求 1、在后面的课题表中列出了多个设计课题，每个课题都有相应的要求或说明。学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题。若学生对课题表以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。 2 、 关于设计的总要求 ：在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 3 、 验收 ：在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 4 、 设计报告 ：设计结束后要写出课程设计报告，以作为整个集中上机评分的书面依据和存档材料。设计报告以规定格式的电子文档书写，排版及图、表要清楚、工整。内容及要求如下： 简述题目要解决的问题是什么，并说明输入和输出数据的形式。 简述存储结构和算法的基本思想。 列出调试通过的源程序。 列出上面程序对应的运行结果。 分析程序的优缺点、时空性能以及改进思想，写出心得体会。 三、成绩评定 ： 课程设计的成绩评定以选定课题的难易度、完成情况和设计报告为依据综合评分，设计报告占30％，设计作品占70％。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 三、数据结构集中上机课题表 排序算法性能分析（95分） 编程实现希尔、快速、堆排序、归并排序算法，并计算每种排序算法的比较、交换次数。要求待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 散列表实现学生情况表（85分） 设有学生情况表，每个记录有下列数据项：学号、姓名、性别、年龄。现使用散列表表示该学生情况表，并采用二次探测法解决冲突。试设计一个系统使之具有下列功能： 从一个文本文件中输入各记录（记录项用空格分隔）来建立散列表 有哪些信誉好的足球投注网站并显示给定学号的学生记录 删除一个学生记录 在多次删除后，重新整理学生情况表； 打印学生情况表 三件有制约关系物品过河问题（75分） 有一人要将自己的兔子、蔬菜和狐狸等三件物品运过河。但过河所用的船每次只能装其中的两件，而这三件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模型，并编程实现这一问题的求解。 设计和实现多项式运算（80分） 实现带头结点的单循环链表表示的多项式 设计和实现多项式相加和相乘运算算法 设计一个测试程序：测试多项式加法和乘法运算。要求： 建立一个多项式 打印（显示）一个多项式 实现两个多项式相加； 实现两个多项式相乘。 在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 迷宫求解（参见教材描述）（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).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称） 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 订票系统（90分） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询： 可以查询某个航线的情况（如，输入航班号，查