算法设计技能训练选题

《算法设计技能训练选题》由会员分享，可在线阅读，更多相关《算法设计技能训练选题（33页珍藏版）》请在金锄头文库上搜索。

1、算法设计技能训练选题一、选题原则选题的根本原则是数据结构算法实现及在具体问题中的应用。可选择下列与实际应用紧密结合的较综合性的题目，并且鼓励自选题目（自选题必须通过任课教师认可） 。要求通过课程设计的实践，在数据结构的表示、数据结构的选择及应用、算法设计与实现等方面加深对数据结构课程基本内容的理解和综合运用能力的提高。对下列题目每个同学的课设任务按下式确定：课设任务=学号%30（班号1）3）30如学号为 xxxxxx0301 的同学应完成任务书 1%30+(3-1)%3)*30=61。二、待选题目0.车厢调度问题描述：假设停在铁路调度站入口处的车厢序列的编号一次为 1，2，3，n。设计一个程序

2、，求出所有可能由此输出的长度为 n 的车厢序列。1. 学生运动会成绩管理功能：学生运动会成绩数据库系统记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括 50、100、200，400，1500 米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序 ；按系院编号查询；按项目编号查询；按女团体总分排序。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括某个系，5 个项目的得分情况，能对文件中的信息进行扩充（追加） ，修改和删除；进一步要求：完成对多个系，

3、多个项目的得分排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。键盘输入：系院数目，男子项目数女子项目数， （每项目取前三名，分别为 10，5，2 分）要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 2. 哈夫曼树应用功能： 1从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树并将它存于文件 hfmTree 中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2利用已经建好的哈夫曼树（如不在内存，则从文件 htmTre

4、e 中读入） ，对文件 ToBeTran中的正文进行编码，然后将结果存入文件 CodeFile 中，并输出结果，将文件 CodeFile 以紧凑格式先是在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrint中。3利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中，并输出结果。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：完成功能 1；进一步要求：完成功能 2 和 3。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的

5、注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。3.图的遍历功能：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。分步实施：1) 初步完成总体设计，搭好框架；完成最低要求：两种必须都要实现，写出画图的思路；进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。4. n 维矩阵乘法：A B1功能：设计一个矩阵相乘的程序，首先从键盘输入两个

6、矩阵 a，b 的内容，并输出两个矩阵，输出 ab1 结果。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，可完成 2 维矩阵的情况；一步要求：通过键盘输入维数 n。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。5. 数组应用功能： 按照行优先顺序将输入的数据建成 4 维数组，再按照列优先顺序输出结果，给出任意处的元素值，并给出对应的一维数组中的序号。分步实施：1初步完

7、成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：完成第一个功能；进一步要求：进一步完成后续功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 6.n 元多项式乘法功能： 完成两个 n 元多项式作乘法，给出明确的等式形式。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。进一步要求：实现三元二次多项式的乘法。有兴趣的同

8、学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。7.集合运算功能： 使用链表来表示集合，完成集合的合并，求交集等操作。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求： 进一步要求： 要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。8.公园的导游图功能：给出一

9、张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边） 。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括 5 个景点情况，能完成遍历功能；进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。9. 商店存货管理系

10、统功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括 5 个种类的货物情况，能对商品信息进行扩充（追加） ，修改和删除以及简单的排序；进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。10. 汉诺威塔功能：编程序显示 n（n0)个人按顺

11、时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 是停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括某人 5 个人的情况。进一步要求：有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程

12、序测试方案5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。13.一元稀疏多项式计算器1、问题描述：（需求分析和背景意义）设计一个一元稀疏多项式简单计算器.2、基本要求：（设计阶段，概要设计和详细设计）一元稀疏多项式简单计算器的基本功能是:(1)输入并建立多项式;(2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,cn,en,其中 n 是多项式的项数,ci 和 ei 分别是第 i 项的系数和指数,序列按指数降序排列 ;(3)多项式 a 和 b 相加,建立多项式 a+b;(4)多项式 a 和 b 相减,建立多项式 a-b.3、测试数据：(2x+

13、5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(6x-3-x+4.4x-2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(x+x3)+(-x-x3)=0(x+x100)+(x100+x200)=(x+2x100+x200)(x+x2+x3)+0=x+x2+x3互换上述测试数据中的前后两个多项式4、实现提示：用带表头结点的单链表存储多项式5、选做内容 ：(1)计算多项式在 x 处的值.(2)求多项式 a 的导函数 a.(3)多项式 a 和 b 相乘,建立乘积多项式

14、 ab.(4)多项式的输出形式为类数学表达式.例如,多项式-3x8+6x3-18 的输出形式为-3x8+6x3 -18,x15+(-8)x7-14 的输出形式为 x15-8x7-14. 注意,系数值为 1 的非零次项的输出形式中略去系数 1,如项 1x8 的输出形式为 x8,项-1x3 的输出形式为-x3.(5) 计算器的仿真界面.15.哈夫曼编/编译器1、问题描述：（需求分析和背景意义）利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息

15、的信道） ，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编 /译码系统。2、基本要求：（设计阶段，概要设计和详细设计）一个完整的系统应该具有以下功能：（1）I：初始化（Initialization） 。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。 （2）E 编码（Encoding） 。 利用建好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入） ，对文件 ToBeTran 中正文进行编码，然后将结果存入文件 CodeFile 中。 （3）D：译码（Decoding） 。利用已建好的哈夫曼树将文件 C

16、odeFile 中的代码进行译码，结果存入文件 TextFile 中。 （4）P 印代码文件（Print ） 。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。 同时将此字符形式的编码文件写入文件 CodePrin 中。 （5）T 印哈夫曼树（Tree printing） 。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此文字符形式的哈夫曼树写入文件 TreePrint 中。3、测试数据： （1）利用教科书例 6-2 中的数据调试程序。 （2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE ”。字符 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 1