算法与数据结构程序设计题目及要求_070013.doc

2007级 算法与数据结构程序设计 题目 学生班级：070013 指导教师：蒋凌云 日 期：2009年6月22日－6月28日(第19周) 系统平台：Windows 2000，Windows XP 开发工具：Turbo C / Visual C++ 等等 具体要求：用上述系统平台和开发工具完成所分配题目的程序，并撰写报告。 题 目 一：求最大的组合数（E） 题目描述：对输入的若干个数，输出其能组合成的最大的那个数。例如，有四个数123、124、56和90，可以组成的数是 1231245690、1241235690、5612312490、9012312456 和 9056124123 等等，但是，其中最大的就是 9056124123。 基本要求：程序正确，能够输出给出数据的最大组合数 设计提示：算法的思想可以参考《数据结构》中的排序算法（例如壮性良好。 提高要求：程序应保持较小的时间复杂性和空间复杂性。冒泡排序）。 参考资料： 《数据结构—使用C++语言描述》 陈慧南 东南大学出版社 2000. 《C程序设计》 谭浩强 清华大学出版社 2001. 《C++语言程序设计》 郑莉 董渊 清华大学出版社 2002. 题 目 二：joseph环 (E) 题目描述：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 基本要求：程序正确，能够输出正确的出列顺序，并且健壮性良好。 提高要求：程序应保持较小的时间复杂性和空间复杂性。 设计提示： 1、因为n人围坐一圈，并且程序过程中人数不断减少，可利用单向循环链表存储结构模拟此过程。 2、按密码m报数，该人的顺时针后m个人即为出列的人，此时输出此人的编号并将他从链表中删除。 参考资料： 《数据结构—使用C++语言描述》 陈慧南 东南大学出版社 2000. 《C程序设计》 谭浩强 清华大学出版社 2001. 《C++语言程序设计》 郑莉 董渊 清华大学出版社 2002. 题 目 三：智能火车订票系统(M) 题目描述：基于列车时刻表，输入起点和目的地，给出最便宜的出行路线。 基本要求：(1) 打印出起点——终点的全程路线，(途径各站)每段路线的票价，以及总的票价； (2) 路线中不能出现回路； (3) 对输入的错误能做出适当的处理，例如输入一个不存在的站名或者给了一个不合法的输入。 提高要求：(1) 能做出基本的智能判断，比如当有直达列车时，能忽略转车路线，即便该转车路线价格更加便宜； (2) 能有简洁美观的图形化界面。 设计提示：列车时刻表可以体现为文件的形式，从该文件中读取需要的站名和票价信息，也可以直接在程序中定义邻接表或者邻接矩阵来保存相关数据；算法与数据结构主要体现为图的最短路径问题。 参考资料： 《数据结构—使用C＋＋语言描述》 陈慧南 东南大学出版社 2000. 《C程序设计》 谭浩强 清华大学出版社 2001. 《C++语言程序设计》 郑莉 董渊 清华大学出版社 2002. 题 目 四：求解多项式积分（M） 题目描述：输入待求函数，积分上下限，求出结果。 基本要求：(1) 能正确求解多项式的单重和双重积分(存在x和y两个积分变量)； (2) 能处理用户输入错误以及基本的逻辑错误。 提高要求：(1) 能设计出简捷易操作的窗口界面； (2) 能处理多重积分。 设计提示：用链表结构描述多项式。 参考资料： 《数据结构—使用C＋＋语言描述》 陈慧南 东南大学出版社 2000. 《C程序设计》 谭浩强 清华大学出版社 2001. 《C++语言程序设计》 郑莉 董渊 清华大学出版社 2002. 题 目 五：简单优先文法关系矩阵(H) 题目描述：已知文法G[Z]，一共有7个符号：Z、M、L、a、b、(、)，文法之间的关系（规则）如下： Z ∷＝bMb M ∷＝(L|a L∷＝Ma) ∷＝称为“定义为”，把规则分为左部和右部。 关系L的意思是由文法规则左部符号与右部首符号组成的有序偶集合。如上述文法中，Z和b、M和(、M和a、L和M是L关系， 关系R的意思是由文法规则左部符号与右部尾符号组成的有序偶集合, 如上述文法中，Z和b、M和L、M和A、L和）是L关系， 可以通过布尔矩阵表示符号之间是否存在关系。 文法优先关系是指文法符号之间的关系，包括、 · 、· 。 1) S1 S2当且仅当Ｇ中有规则 U∷＝…S1S2…； 2)S1·S2当且仅当Ｇ