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