算法设计技能训选题.doc

算法设计技能训练选题表一、选题原则选题的根本原则是数据结构算法实现及在具体问题中的应用。可选择下列与实际应用紧密结合的较综合性的题目，并且鼓励自选题目（自选题必须通过任课教师认可）。要求通过课程设计的实践，在数据结构的表示、数据结构的选择及应用、算法设计与实现等方面加深对数据结构课程基本内容的理解和综合运用能力的提高。选题分组：一人一组，题目多少不限，但是代码编写量有限制，计算机（单招）：650行，计算机（3+4）：650行；计算机（NIIT）：至少800行。二、待选题目1. 学生运动会成绩管理功能：学生运动会成绩数据库系统记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序 ；按系院编号查询；按项目编号查询；按女团体总分排序。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括某个系，5个项目的得分情况，能对文件中的信息进行扩充（追加），修改和删除；进一步要求：完成对多个系，多个项目的得分排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。键盘输入：系院数目，男子项目数女子项目数，（每项目取前三名，分别为10，5，2分）要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 2. 哈夫曼树应用功能： 1从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。3利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：完成功能1；进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。3.图的遍历功能：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。分步实施：1) 初步完成总体设计，搭好框架；完成最低要求：两种必须都要实现，写出画图的思路；进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。4. n维矩阵乘法：A B1功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab1结果。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，可完成2维矩阵的情况；一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。5. 数组应用功能： 按照行优先顺序将输入的数据建成4维数组，再按照列优先顺序输出结果，给出任意处的元素值，并给出对应的一维数组中的序号。分步实施：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：完成第一个功能；进一步要求：进一步完成后续功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 6.n元多项式乘法功能： 完成两个n元多项式作乘法，给出明确的等式形式。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。7.集合运算功能： 使用链表来表示集合，完成集合的合并，求交集等操作。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求： 进一步要求： 要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。8.公园的导游图功能：给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。9. 商店存货管理系统功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。10. 汉诺威塔功能：编程序显示n（n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。分步实施：初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；完成最低要求：建立一个文件，包括某人5个人的情况。进一步要求：有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案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+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相乘,建立乘积多项式ab.(4)多项式的输出形式为类数学表达式.例如,多项式-3x8+6x3-18的输出形式为-3x8+6x3 -18,x15+(-8)x7-14的输出形式为x15-8x7-14.注意,系数值为1 的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项-1x3的输出形式为-x3.(5) 计算器的仿真界面.14.哈夫曼编/编译器1、问题描述：（需求分析和背景意义）利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2、基本要求：（设计阶段，概要设计和详细设计） 一个完整的系统应该具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E编码（Encoding）。 利用建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中正文进行编码，然后将结果存入文件CodeFile中。 （3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件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 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 14、实现提示： （1）编码结果以文本方式存储在文件CodeFile中。 （2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 （3）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。5、选做内容 ： （1）上述文件CodeFile中的每个“0”或“1”实际上占用了一个字节的空间，只起到示意或模拟的作用。为最大限度的利用码点存储能力，试改写你的系统，将编码结果以二进制形式存放在文件CodeFile中。 （2） 修改你的系统，实现对你的系统的原程序的编码和译码（主要是将行尾符编/译码问题）。 （3） 实现各个转换操作的源/目文件，均由用户在选择此操作时指定。15. 稀疏矩阵运算器1、问题描述：（需求分析和背景意义） 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2、基本要求：（设计阶段，概要设计和详细设计） 以“带行逻辑链接信息”的三元组顺表示稀疏矩阵，实现两矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3、测试数据：10 0 0 0 0 80 0 -30 0 00 0 -11 0 -310 0 0 0 0 9-1 0 0 + = 10 0 0 9 -1 00 00 -11 -310 0 0 10-2 3 - =0 -6 08 0 00 1 0 0 0 0 3 0 0 4 2 00 1 0 1 0 0 0 0 04 -3 0 0 10 0 0 8 00 0 1 0 00 0 0 0 70 =4、实现提示： 首先应输入矩阵的行数和列数，并判别两个矩阵的行、列数对于所要求做的运算是否相匹配。可设矩阵的行数和列数均不超过20。 程序可以对输入的三元组进行限制，例如，按行优先。注意研究教科书5.3.2节中的算法，以便提高计算效率。 3、 在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。5、选做内容 ： 1、按教科书5.3.2节中的描述方法，以十字链表表示稀疏矩阵。 2、 增添矩阵求逆的运算，包括不可求逆的情况。在求逆之前，先将稀疏矩阵的内部表改为十字链表。16. 迷宫问题的求解及演示1、问题描述：（需求分析和背景意义） 以一个mn的长方阵表示迷宫,0和1分别表示迷宫中的道路和障碍.设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.2、基本要求：（设计阶段，概要设计和详细设计） 首先实现一个以链表做存储结构的栈类型,然后编写一个求解迷宫的非递归程序.求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向.如:对于下列数据的迷宫,输出的一条通路为(1,1,1),(1,1,2),(2,2,2),(3,2,3),(3,1,2),. 3、测试数据： 迷宫测试数据如下:左上角(1,1)为入口,右下角(8,9)为出口 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000 4、实现提示： 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口的下标为（1，10，出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。5、选做内容 ： （1）编写递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路。17、串基本操作的演示1、问题描述：（需求分析和背景意义） 如果语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试实现串类型，并写一个串的基本操作的演示系统。2、基本要求：（设计阶段，概要设计和详细设计） 在教科书4.2.2节用堆分配存储表示实现HString串的最小操作子集的基础上，实现串抽象数据类型的其余基本操作， （不使用C语言本身提供的串函数）。参数合法性检查必须严格。 说明：（在格式中，表示0个、1个或多个空格所组成的串。串标识表示一个内部名或一个串文字。前者是一个串的唯一标识，是一种内部形式的（而不是字符形式的）标识符。后者是两端由单引号括起来的仅可打印字符组成的序列。串内每两个连续的单引号表示一个单引号符。） 利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直至终止程序的命令为止。命令定义如下：赋值。格式：A串标识回车 用串标识所表示的值建立新串，并显示新串的内部名和串值。如：AHi！判相等。 格式：E串标识1串标识2回车若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。联接。 格式：C串标识1串标识2回车将两串联接产生结果串，它的内部名和串值都显示出来。 （4） 求长度 格式：L串标识回车 显示串的长度。 （5） 求子串 格式：S串标识+数1+数2回车 如果参数合法，则显示子串的内部名和串值。数不带正负号。 （6）子串定位。 格式：I串标识1串标识2回车 显示第二个串在第一个串中首次出现时的位置。 （7）串替换 格式：R串标识1串标识2串标识2回车将第一个串中出现所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。 （8）显示格式：P回车 显示所有在系统中被保持的串的内部名和串值的对照表。 （9）删除格式：D内部名回车 删除该内部名对应的的串，即赋值的逆操作。 （10）退出 格式：Q回车 结束程序的运行。在上述命令中，如果一个自变量是串，则应首先建立它。基本操作函数的结果（即函数值）如果是一个串，则应在尚未分配的区域内新辟空间存放。 3、测试数据： 自定。但要包括以下几组： （1）E 回车，应显示“EQUAL”。（2）Eabc abcd回车，应显示“UNEQUAL”。 （3）C 回车，应显示。 （4）Ia 回车，应报告：参数非法。 （5）Raaa aa b回车，应显示ba （6） Raaabc a aab回车，应显示aabaabaabbc。 （7）Raaaaaaaa aaaa ab回车，应显示abab。 4、实现提示： （1）演示系统的主结构是一个串表头，可定义为： struct HString StrHead100； int CurNum StrHeadList；将各串的头指针依次存于串头数组StrHead中（设串的数目不超过100）。CurNum为系统中现有的串的数目，CurNum+1是可为下一个新串头指针分配的位置。可以取StrHead的元素下标作为所对应串的内部名。（2）应设置一个命令为分析函数，把命令分析结果通过一下类型的一个变量参数返回： typedef struct int CmdNo；/或char类型，为命令号或命令符 int s3； /命令串参数的内部名（最多3个） int num2； / 命令的数值参数（最多2个） ResultType；此函数还在存储结构中建立命令参数中的串。可能再设置一个“取下一个命令参数串”的操作是有益的。注意不要把这里的命令与所有机器的操作系统的命令相混。为了处理简单化，可以不对命令的格式作严格的语法检查。5、选做内容 ： （1）串头表改用单链表实现。 （2）对命令的格式（即语法）作严格检查，是系统既能处理正确的命令，也能处理错误的命令。赘言，语义检查（如某内部名对于能够的串已被删除而无定义等）和基本操作参数合法性检查仍留给基本操作去做。 （3） 支持串名。 将串名（可设不超过6个字符）存于串表头中。命令（1）（3）（5）要增加命令参数结果串名；命令（7）中的串标识1改为串名，并用此名作为结果串名，删除原被替串标识，用串名代替串标识定义和命令解释中的内部名。每个命令执行完毕时立即自动删除无名串。18.内部排序算法比较1、问题描述：（需求分析和背景意义） 在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2、基本要求：（设计阶段，概要设计和详细设计） （1）对以下6中常用的内部算法进行比较：起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序。 （2）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。 （3）最后要对结果作出简单分析，包括对各数据得出结果波动大小的解释。3、测试数据： 由随机数产生器产生。4、实现提示： 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。5、选做内容 ： （1）增加折半插入排序、二路插入排序、归并排序、基数排序等。 （2）对不同的输入表长作实验，观察检查的两个指标相对于表长的变化关系。还可以对稳定性作验证。19.车厢调度问题描述：假设停在铁路调度站入口处的车厢序列的编号一次为1，2，3，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。测试数据自己输入。20. 算术表达式的求值演示1、问题描述：（需求分析和背景意义） 表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型的例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。2、基本要求：（设计阶段，概要设计和详细设计） 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书上的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。3、测试数据： 教科书例3-1的算术表达式3*（7-2），以及下列表达式 8； 1+2+3+4； 88-1*5；1024/4*8； 1024/（4*8）； （20+2）*（6/2）；3-3-3； 8/（9-9）； 2*（6+2*（3+6*（6+6）；（6+6）*6+3）*2+6）*2；4、实现提示： （1） 设置运算符栈和运算数栈辅助分析算符优先关系。 （2） 在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转化成整数形式。 （4）在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。5、选做内容 ： （ 1）扩充运算符集，如增加乘方、单目减、赋值等运算。 （2）运算量可以是变量。 （3）运算量可以是实数类型。 （4）计算器的功能和仿真界面。21. 校园导游咨询1、问题描述：（需求分析和背景意义） 设计一个校园导游程序，为来访的客人提供各种信息查询服务。2、基本要求：（设计阶段，概要设计和详细设计） （1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度的相关信息。 （2）为来访客人提供图中任意景点的相关信息查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。3、测试数据： 由读者根据实际情况指定。4、实现提示： 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。5、选做内容 ： （1）求校园的关节点。 （2）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。 （3） 提供校园图中多个景点的最佳访问路线查询，即求途经这个景点的最佳（短）路径。 （4）校园导游图的景点和道路的修改扩充功能。 （5）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。 （6）扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详导向信息。 （7）实现校园导游图的仿真界面。22. 约瑟夫环的求解及演示1、问题描述：（需求分析和背景意义） 约瑟夫问题的一种描述是:编号为1,2,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人将出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.设计一程序求出出列顺序.2、基本要求：（设计阶段，概要设计和详细设计） 利用单向循环链表存储结构模拟次过程,按照出列的顺序印出个人的编号.3、测试数据： m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序应为6,1,4,7,2,3,5).4、实现提示： 程序运行后,首先要求用户指定初始报数上限,然后读取个人的密码.可设n30.此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限.5、选做内容 ： 向上述程序中添加在顺序结构上实现的部分.23.平衡二叉树操作的演示1、问题描述：（需求分析和背景意义） 利用平衡二叉树实现一个动态查找表。2、基本要求：（设计阶段，概要设计和详细设计） 实现动态查找表的三种功能：查找、插入、删除。3、测试数据：自行设定。4、实现提示： （1）初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树的显示。 （2）平衡二叉树的显示可采用凹入表现形式，也可以采用图形界面画出树行。 （3）、教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为x的结点。如果x不在叶子结点上，则用它的左子树中最大值或右子树中的最小值取代x。如此反复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡交换，可采用插入的平衡变换的反变换（如，左子树变矮对应右子树长高）。5、选做内容 ： （1）合并两棵平衡二叉树。 （2）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。24. 最小生成树问题1、问题描述：（需求分析和背景意义） 若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2、基本要求： （设计阶段，概要设计和详细设计） （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现教材6.5节中定义的抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。（3）以文本的形式输出生成树中各条边以及他们的权值。（a c 3）提示：1、 通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。2、设图的顶点数不超过30个，并为简单起见，网中的权值设成小于100的整数，可利用C语言提供的随机函数产生。3、 图的存储结构的选取和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法也不选用邻接表，而是以存储边（带权）的数组表示图。5、选做内容： 利用堆排序（参见教科书10.4.3节）实现选择权值最小的边。25.马踏棋盘的求解及演示（八皇后）1、问题描述：（需求分析和背景意义） 设计一个国际象棋的马踏遍棋盘的演示程序.基本要求： （设计阶段：概要设计和详细设计） 将马随机放在国际象棋的88棋盘Board88的某个方格中,马按走棋规则进行移动.要求每个方格只进入一次,走遍棋盘上全部64个方格.编制非递归程序,求出马的行走路线,并按求出的马的行走路线,将路线1,2,64依次填入一个88的方阵,输出之.测试数据： 由读者指定.可自行指定一个马的初始位置(i,j),0i,j7.实现提示:下页图显示了马位于方格(2,3)时,8个可能的移动位置.一般来说,当马位于位置(i,j)时,可以走到下列8个位置之一(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1) 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 但是,如果(i,j)靠近棋盘的边缘,上述有些位置可能超出棋盘范围,成为不允许的位置.8个可能位置可以用两个一维数组HTry10.7和HTry20.7来表示:HTry1 0 1 2 3 4 5 6 7-2 -1 1 2 2 1 -1 -2HTry2 0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1位于(i,j)的马可以走到的新位置是棋盘范围内的(i+HTry1h,j=HTry2h),其中h=0,1,7. 每次在多个可走位置中选择其中一个进行试探,其余未曾试探过的可走位置必须用适当结构妥善管理,以备失败时的“回溯”(悔棋)使用.5、选做内容：(1) 求出从某一起点出发的多条以至全部行走路线. (2)探讨每次选择位置的“最佳策略”,以减少回溯的次数. (3)演示寻找行走路线的回溯过程.26.运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；27. 飞机订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；28. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；29. 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 30. 宿舍管理查询软件1) 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：A. 采用交互工作方式B. 建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2) 查询菜单: (用二分查找实现以下操作)A. 按姓名查询 B. 按学号查询 C. 按房号查询3) 打印任一查询结果（可以连续操作）31. 地图着色问题设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。32. 校园导航问题设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。33. 学校超市选址问题（带权有向图的中心点）设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。34. 教学计划编制问题 设计要求：针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。35. 散列法的实验研究散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。36. 图书借阅管理系统 主要分为两大功能：1) 图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；2) 会员管理(增加会员、查询会员、删除会员、借书信息)；37. 学生成绩管理 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。38. 活期储蓄帐目管理 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。39.二叉排序树的实现 用顺序和二叉链表作存储结构，完成学生成绩管理 1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排 序树T；2)对二叉排序树T作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；40.最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。41.通讯录的制作设计目的：用数据结构中的双向链表作数据结构，结合C语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：1)输入信息enter();2)显示信息display( );3)查找以姓名作为关键字 search( );4)删除信息delete( );5)存盘save ( );6)装入load( ) ;设计要求：1)每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项2)作为一个完整的系统，应具有友好的界面和较强的容错能力3)上机能正常运行，并写出课程设计报告42.长途电话区号编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，长途电话区号编码/译码器。【基本要求】1)将权值数据(根据人口决定)存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；【进一步完成内容】1)译码功能；2)显示哈夫曼树；3)界面设计的优化。43.散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。44.走迷宫游戏程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2)迷宫的墙足够结实，老鼠不能穿墙而过；3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5)找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能45.顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。要求： 1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况45.利用栈求表达式的值要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价，可供小学生作业，并能给出分数。46.简易文本编辑器要求：1)具有图形菜单界面；2)查找，替换（等长，不等长），插入（插串，文本块的插入）、块移动（行块，列块移动），删除3)可正确存盘、取盘；4)正确显示总行数。47.二叉树的算法二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是多样的。48.学生搭配问题一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3)尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.49.敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。50.猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到