课程设计题目 一、必做题。 1、链表排序 任务 ： （1）从文件读入 30 个无序整数，建立一个单链表，排序输出、再倒序输出。 （2）从文件 A 读入 30 个无序整数，建立一个递增的单链表 A 并输出，从文件 B 读入 30 个无序整数，建立一个递 增的单链表 B 并输出，在 A 中求递增的并集。 （3）从文件读入 30 个学生成绩（0-100 之间），建立一个双向循环链表并输出，调整链表顺序，使所有的及格成绩 排在不及格成绩之前，并输出。 2、二叉树的应用 任务 ：编程实现二叉树的建立，层次遍历，（递归和非递归方法）先序、中序、后序，二叉树的高度、宽度。二叉 排序树的建立、插入、删除； 基本要求：从文件中读入建树信息，树的节点数目不小于 20 个，树的高度不小于 5； 3、校园局域网布线和游历问题 任务 ：用无向网表示你所在学校的主要建筑平面图，图中顶点表示主要建筑，图中的边表示建筑之间的道路，存 放路径长度信息。要求能够建立校园局域网，所花的代价最小；给出任意建筑之间游历的最短路径。 基本要求： （1） 原始数据存在文件中，方便读入； （2） 建筑物点不小于 20 个，边不小于 30 个； （3） 分别用广度优先和深度优先的方法遍历图，起始点定为 1 号教学楼； （4） 建立校园局域网，要求所花的代价最小； （5） 查询从 1 号教学楼到其他各点的最短路径； （6） 查询图中任意两个建筑间的最短路径。 4、Hash 表应用 任务 ：设计散列表实现电话号码查找系统。 基本要求： 1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘或文件输入各记录，不少于 30 个，以电话号码为关键字建立散列表； 3) 采用链地址的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5、排序算法比较 任务 ：利用随机函数产生 10 个样本（其中之一已为正序，之一为倒序），每个样本有 20000 随机整数，利用直接 插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序（递归和非递归），基数排序八种排序 方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间 二、选做题。 1、 运动会分数统计 任务：参加运动会有 n 个学校，学校编号为 1……n。比赛分成 m 个男子项目，和 w 个女子项目。项目编号为男子 1…… 

m，女子 m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分 分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=10 , w=8 , n=15） 功能要求： 1).可以输入各个项目的前三名或前五名的成绩； 2).能统计各学校总分（用链表）； 3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）； 4).可按学校编号查询学校某个项目的情况；可按项目编号查询前三或前五名的学校。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。 测试数据：要求使用 1、全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结 果请在上交的资料中写明； 2、 迷宫求解 任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出 （最佳路径）； 要求：以较为直观的方式显示结果 3、 Huffman 编码 任务 ：对一篇英文文章，统计各字符出现的次数，实现 Huffman 编码； 要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现； 4、营业窗口队列模拟 任务：实现具有 n（n=3）个窗口的现实队列模拟，统计每人的等待时间。 要求： 1). 随机产生顾客的到达时间和服务时间存盘。 2). 利用存盘数据实现队列的插入和删除。 2). 当有顾客离开时，根据队列长度调整队尾。 3). 考虑顾客中途离队的情况。 4). 考虑顾客具有优先级的情况。 5、公交线路提示 任务：建立南京主要公交线路图。 要求：输入任意两站点，给出最佳的乘车线路和转车地点。 路线信息可上网查询 6、家谱管理系统 任务：实现具有下列功能的家谱管理系统 功能要求： 1). 输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、 健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。 2). 实现数据的存盘和读盘。 3). 以图形方式显示家谱。 4). 显示第 n 代所有人的信息。 5). 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。 

6). 按照出生日期查询成员名单。 7). 输入两人姓名，确定其关系。 8). 某成员添加孩子。 9). 删除某成员（若其还有后代，则一并删除）。 10).修改某成员信息。 11).按出生日期对家谱中所有人排序。 12).打开一家谱时，提示当天生日的健在成员。 要求：建立至少 30 个成员，以较为直观的方式显示结果，并提供文稿形式以便检查。 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能。 存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用 1、 全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写 明； 7、算术表达式求值 任务： 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正 整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4） #。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 要求： （1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 8、电子小字典 任务：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。 数据结构：键树 9、稀疏矩阵相乘 任务：以三元组形式存储稀疏矩阵，实现矩阵相乘 10、平衡二叉树 任务：平衡二叉树的建立、结点的插入和删除。 11、B-树 任务：3 阶 B-树的结点的插入和删除。 12、编写“连连看”程序。 13、……（自选合适的题目） 成绩评定细则：（优、良、中、及格、不及格五等级） 1. 正确性：程序是否可以运行，结果是否正确（20%） 2. 功能的完备性：是否实现要求的所有子功能（20%） 3. 课程设计报告中的算法说明，课程设计报告中总结（20%） 4. 独立完成情况( 40%） 

加分项目： 1.工作量和选题难度 2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进，关键位置适量注释等 3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.健壮性：异常处理的情况 5.界面的设计：可视化界面，或者交互良好的 DOS 界面 6. ……（自荐加分项目） 代码量要求：>=2500 行。 代码总量 = 课设题目 1 代码量 + 课设题目 2 代码量…… 若代码总量低于 2500 行，则成绩按比例打折。 编程语言：C 或 C++语言 编程环境：Microsoft Visual C++ 6.0 检查方式:一对一上机检查 总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性，程序的结构是否合理；根据实际情况进行 详细的程序代码检查。 时间安排： 1 上机时间安排 2 课程设计检查时间 3 课程设计报告上交时间 课程设计报告要求： 1.课程设计报告封面：包括课题名称、班级、学号、学生姓名、成绩和指导教师； 2.课程设计报告目录：每部分内容所在页码； 3.需求分析：给出每道题的需求； 4.概要设计：给出每道题采用的数据结构，算法设计思想，算法的时间复杂度； 5.详细设计：给出每道题的源程序，并在必要的代码处给出注释； 6.功能测试：给出每道题的测试数据和结果； 7.完成情况：每道题完成部分和未完成部分，自己最满意的部分； 8.代码量：每道题代码的行数和总行数； 9.心得体会：包括课程设计设中遇到的问题，如何解决，编程的体验，感想和建议； 10.课程设计报告的电子文档在检查后一周内上交班长。