2012级计科数据结构课程设计教学大纲.docVIP

《数据结构与算法课程设计 课程英文名称：Curriculum-design of Data Structures and Algorithms 课程类别：实践教学 周　　数：2 学 分：2 适用专业：计算机科学与技术 一、课程设计的性质、目的 对学生数据结构知识的全面综合训练，把书上学到的知识用于解决实际问题、培养今后软件开发工作所需的动手实践能力，包括问题分析、总体结构设计，用户界面的设计、程序设计时的基本技能和技巧，以及一整套软件工作规范的训练和团体协作精神的培养。 二、 课程设计基本要求 （1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； （4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 三、课程设计教学内容 根据教材《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，或选择下列与实际应用紧密结合的较综合性的题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。以下列出一些可供选择的题目： 1.一元多项式的运算 设计要求：计算任意两个一元多项式的加法、减法以及乘法。 2.算术表达式求值 设计要求：将任意一个算术表达式转化为逆波兰表示，并根据逆波兰表示计算表达是的值。 3.舞伴问题 假定在一舞会上，男士排成一队，女士排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。 设计要求：模拟上述舞伴系统，并能计算对于任何男士A和女士B在哪一轮舞曲中的k次跳舞？ 4.集合的等价划分 设计要求：对于任何一个集合及其上的一个等价关系（要验证此关系的等价性），给出该集合的等价划分。 5. 简易家谱系统 设计要求：输入家族成员情况，建立树结构，统计家族成员人数，能查询家族成员辈份情况。 6. 哈夫曼树的应用 设计要求：针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。 7.地图着色问题 设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。 8.小型文本编辑器 设计要求：设计一个文本编辑器，使其具有通常编辑器（如Notepad）具备的功能。 9.校园导航问题 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 10.学校超市选址问题（带权有向图的中心点） 设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。 11.教学计划编制问题 设计要求：针对计算机本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。 12. 哈希表及其应用 建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求：使用哈希查找表存储信息；实现查找、插入、删除、统计、输出等功能； 13.关键路径 设计要求：对于任何大型工程项目（由若干小工程组成），求其关键路径。 14.最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。 15. 二叉排序树与平衡二叉排序树基本操作的实现 设计要求：用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作。 16. 运动会成绩管理系统 设计要求：学生运动会成绩数据库系统记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序 ；按系院编号查询；按项目编号查询；按女团体总分排序。 17．哈夫曼树的应用 设计要求：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件