学年设计II-面向对象课程设计增加选题

计科161面向对象程序设计补充选题1 教学计划编制问题目的：通过对教学计划编制问题的解决达到将所学相关专业知识用于解决实际问题。内容：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 （3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 测试数据 学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见图1。 实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程号与课程号之间的对应关系。 图1 课程先修关系 报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。2 运动会分数统计问题目的：通过对运动会分数统计问题解决达到将所学相关专业知识用于解决实际问题。内容：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）。功能如下：1).可以输入各个项目的前三名或前五名的成绩；2).能统计各学校总分；3).可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。3 校园导游程序目的：通过对校园导游程序的设计与实现达到将所学相关专业知识用于解决实际问题。内容：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。功能要求如下：（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。 报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。4 创建线性表顺序存储类MyArrayList 目的：通过对线性表顺序存储类的创建和应用，增强面向对象程序设计和顺序表的理解与应用实践。内容：（1）MyArrayList存储空间的大小以及存储数据类型根据用户需求自行确定。（2） 提供初始化数据功能（即创建该对象时可以通过指定数组将初始参数传入该对象）（3）提供插入一个元素功能；（4）提供删除一个元素功能；（5）提供根据指定关键字排序功能；（默认升序，也能降序，提供用户自己选择方式。）（6）提供根据指定关键字查找功能，查找结果返回该元素位置，-1表示查找失败。（7）提供两个有序顺序表合并功能；（8）提供根据指定关键字，返回指定第K大的元素位置；（9）提供显示顺序表中各元素功能；（提示：顺序表中元素可能是简单数据类型，也可能是复合数据类型：比如自定义结构体类型，所以有指定关键字一说。）（9）给出各个功能的测试样例。报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。5 创建线性表链式存储类MyLinkList 目的：通过对线性表链式存储类的创建和应用，增强面向对象程序设计和链表的理解与应用实践。内容：（1）MyLinkList提供创建多种类型链表，包括：单链表、双链表，单循环链表，双循环链表。（2） 提供初始化数据功能（即创建该对象时可以通过指定数组将初始参数传入该对象）（3）提供插入一个元素功能；（4）提供删除一个元素功能；（5）提供根据指定关键字排序功能；（默认升序，也能降序，提供用户自己选择方式。）（6）提供根据指定关键字查找功能，查找结果返回该元素指针，NULL表示查找失败。（7）提供两个有序顺序表合并功能； （8）提供根据指定关键字，返回指定第K大的元素指针；（9）提供输出显示链表中各个元素功能；（10）提供释放指定对象功能；（11）给出各个功能的测试样例。报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。6 创建二叉树类MyBinarySearchTree 目的：通过对树型类的创建和应用，增强面向对象程序设计和树型结构的理解与应用实践。内容：（1）MyBinarySearchTree提供根据关键字初始化创建对象功能；用户可以根据选择确认是否创建平衡二叉树（平衡二叉树功能选做）。（2）提供插入一个元素功能；（3）提供删除一个元素功能；（4）提供根据指定关键字查找功能，查找结果返回该元素指针，NULL表示查找失败。（5）显示元素信息：提供从小到大显示二叉树中各个元素功能（默认）；提供从大到小显示二叉树中各个元素的功能；（6）返回指定第K大的元素指针。（7）释放指定对象功能（9）给出各个功能的测试样例。报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。7 创建一个图类MyGraph目的：通过对树型类的创建和应用，增强面向对象程序设计和树型结构的理解与应用实践。内容：（1） MyGraph提供初始化功能，即根据提示输入图的相关数据（图的类型：有向图，无向图；顶点和边，边上是否有权值，有权值，权值需要初始化；存储类型：邻接矩阵，邻接表）。（2） 提供删除一个顶点功能（删除该顶点必须删除与该顶点相连的边）。（3） 删除一条边的功能。（4） 增加一个顶点功能（增加一个顶点的同时，如果有其他相连边，同时还要求提供增加该顶点与其他顶点相连的边）（5） 增加一条边功能。（6） 提供邻接矩阵存储转邻接表存储功能。（7） 提供邻接表存储转邻接矩阵存储功能。（8） 提供求单源点到其他顶点的最短距离功能。（9） 带权值的无向图提供求最小生成树功能。（10） 提供DFS遍历功能。（11） 提供BFS遍历功能。（12） 提供判断一个无向图是否为一笔画图。（13） 给出各个功能测试样例。报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。8 数据处理 目的:通过文件操作和各种排序算法实现,加深文件读写实践训练和排序操作实践,并且对各种排序算法的时间复杂度有更进一步的认识。 内容:user.txt中存放了120万余条用户编号(user_id)、密码(password)的记录。每行包含一条记录，每条记录包含：user_id和password中间为TAB分隔（即C语言中的t）。user_id的范围为：11,230,000password的范围：只包含字母和数字，并且长度处于6,19之间。请作如下处理：（1）读取文件中的密码(password)字段，统计密码出现的次数count，写入文件password.txt。不需要排序。格式：每行一条记录，password和count中间用TAB分隔（即C语言中的t）。（2）读取password.txt，对密码出现次数按照降序排序。分别采用：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序；求出每种排序方法所需要的绝对时间。屏幕上输出各种各种排序的绝对时间。最后屏幕上输出出现次数最多的20个密码及次数。（3）读取user.txt，使用链表存放，使用顺序查找，随机生成2000个user_id（11,230,000之内的），再随机生成20个user_id（大于1,230,000的），输出查找所花总时间。（4）读取user.txt，按照用户id使用二叉排序树存放，随机生成2000个user_id（11,230,000之内的），再随机生成20个user_id（大于1,230,000的），输出查找所花总时间。（5）读取user.txt，先按照user_id排序，结果写入user_sorted.txt。用不同的排序方法分别输出排序所需时间。（如果所花时间过长，请缩小数据范围，并估算最终所需的大概时间）（6）读取user_sorted.txt，使用二分查找，随机生成2000个user_id（11,230,000之内的），再随机生成20个user_id（大于1,230,000的），输出查找所花总时间。（只计算查找的时间）（7）设计一个哈希存储的方案，用来存放password.txt中的数据（关键字为密码）；设计20个存在的密码和不存在的密码，输出该密码和出现的次数，以及查找所花总时间。报告要求： （1）仔细观察设计中的各种现象及出现的问题。分析产生各种现象的原因。寻找解决问题的办法。 （2）报告应至少包括带注释的程序清单、输出的结果及对各种现象的分析意见。9 计算器设计目的:通过设计一个带小数计算功能的自动计算器，提高学生通过所学知识解决实际问题。内容：设计一个“自动计算器”，具体描述如下：（1）需要计算的表达式以文本文件格式存放在TXT文本之中；（2）文本中每一行为一个表达式；（3）表达式中包含运算数、加、减、乘、除等运算符以及圆括号； 比如： （34-72.3）*54.7-82.4 （4）“自动计算器”根据输入待计算的文件名，对文本文件中的每一个表达式进行计算，并将每一个表达式的结果写入原文件名_out.txt文件中, 保存记录时，用覆盖写文件的方法。其每行格式为： 计算表达式 = 计算结果。 比如：原文件为A1.txt 计算输出文件名为： A1_out.txt A1_out.txt文本中格式为： （34-72.3）*54.7-82.4 = -2177.41 所有计算结果如果为小数，保留到小数点后4位。（5）计算完毕后生成一个统计文件，其内容为： 执行运算时间：xxxx-xx-xx hh:mm:ss