设计报告内容要求.doc

设计报告内容要求1. 课程设计题目2. 姓名、学号、班级、日期3. 课程设计内容描述:4. 需求(输入、输出、功能、测试数据)5. 实现思想、算法描述6. 使用说明7. 调试说明8. 实现代码(带注释)1. 一元稀疏多项式计算器问题描述 设计一个一元稀疏多项式简单计算器。基本要求一元稀疏多项式简单计算器的基本功能是：（1） 输入并建立多项式；（2） 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，,cn，en，其中n是多项式的项数，ci，ei，分别是第i项的系数和指数，序列按指数降序排序；（3） 多项式a和b相加，建立多项式a+b；（4） 多项式a和b相减，建立多项式a-b；（5） 计算多项式在x处的值；（6） 计算器的仿真界面（选做） 2. 迷宫问题问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求（1） 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路一三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2） 编写递归形式的算法，求得迷宫中所有可能的通路；（3） 以方阵形式输出迷宫及其通路（选做）3. 哈夫曼编/译码器问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。基本要求一个完整的系统应具有以下功能：（1） I：初始化（Initialization）。从终端读入字符集大小n及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。（2） C：编码（Coding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。（3） D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。（4） P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的编码文件写入文件codeprint中。（5） T：打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。4. 教学计划编制问题问题描述 大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求（1） 输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。（2） 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是是课程尽可能地集中在前几个学期中。（3） 若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。5. 成绩分析问题问题描述 录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。基本要求（1） 通过键盘输入个学生的多门课程的成绩，建立相应的文件input.dat。（2） 对文件input.dat中的数据进行处理，要求具有以下功能：1） 按各门课程成绩排序，并生成相应的文件输出。2） 计算每人的平均成绩，按平均成绩排序，并生成文件。3） 求出各门课程的平均成绩、最高分、最低分、不及格人数、6069分人数、7079分人数、8089分人数、90分以上人数。4） 根据姓名或学号查询某人的各门课成绩，重名情况也能处理（3） 界面美观6. 二叉排序树与平衡二叉树的实现问题描述 分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡二叉树的操作。基本要求（1） 用二叉链表作存储结构。1） 以回车符（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；2） 对二叉排序树T作中序遍历，输出结果；3） 计算二叉排序树T查找成功的平均查找长度，输出结果；4） 输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历（执行操作2）；否则，输出信息“无x”；5） 用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；6） 计算平衡的二叉排序树BT的平均查找长度，输出结果。（2） 用顺序表（一维数组）做存储结构。1）以回车符（n）为输入结束标志，输入数列L，生成一棵二叉排序树T；2）对二叉排序树T作中序遍历，输出结果；3）计算二叉排序树T查找成功的平均查找长度，输出结果；4）输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历（执行操作2）；否则，输出信息“无x”；7. 图的基本操作与实现问题描述 自选存储结构，实现对图的操作。基本要求（1） 自选存储结构，输入含n个顶点（用字符表示顶点）和e条边的图G；（2） 求每个顶点的度，输出结果；（3） 指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列（提示：使用一个栈实现DFS）；（4） 指定任意顶点x为初始顶点，对图G作BFS遍历，输出BFS顶点序列（提示：使用一个队列实现BFS）；（5） 输入顶点x，查找图G：若存在含x的顶点，则删除该结点及与之相关联的边，并作DFS遍历（执行操作3）；否则，输出信息“无x”；（6） 判断图G是否是连通图，输出信息“YES”/“NO”；（7） 如果选用的存储结构是邻接矩阵，则用邻接矩阵的信息生成图G的邻接表，即复制图G，然后再执行操作2）；反之亦然。（8） 自选图的其他任意一种操作实现之。8. 全国交通咨询模拟问题描述 处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能地短，出门旅游的旅客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编织一个全国城市间的交通资讯程序，为旅客提供两种或三种最优决策的交通咨询。设计要求（1） 提供对城市信息进行编辑（如添加或删除）的功能。（2） 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3） 提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。（4） 旅途中耗费的总时间应该包括中转站的等候时间。（5） 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或那一次班机到何地。实现提示（1） 对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。（2） 以邻接表座交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。（3） 增加旅途中转次数最少的最优决策。9. 内部排序算法的性能分析问题描述 设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。基本要求（1） 对冒泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较。（2） 待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。（3） 输出比较结果。选做内容（1） 对不同表长进行比较。（2） 验证各算法的稳定性。（3） 输出界面的优化。10. 背包问题的求解问题描述假设有一个能装入总体积为T的背包和n件体积分别为w1，w2，wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积1,8,4,3,5,2时，可找到下列4组解：（1,4,3,2）（1,4,5）（8,2）（3,5,2）实现提示 可利用回溯法的涉及思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品装入背包，假设一选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不适合”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。11. 简单个人图书管理系统的设计与实现问题描述学生在自己的学习和生活中会拥有很多的书籍，对购买的书籍进行分类和统计是一种良好的习惯。这样可以便于对这些知识资料的整理和查询使用。如果用文件来存储相关书籍的各种信息，包括分类、购买日期、价格、简介等，辅之以程序来使用这些文件对里面的书籍信息进行统计和查询的工作将使这种书籍管理工作变得轻松而有趣。简单个人书籍管理系统的开发就是为了解决这个实际问题的。这个系统具备如下的功能：（1） 存储书籍各种相关信息。（2） 提供查找功能，按照多种关键字查找需要的书籍，查找成功后可以修改记录的相关项。（3） 提供排序功能，按照多种关键字对所有的书籍进行排序，例如按照价格进行排序。（4） 其他辅助的维护工作。数据结构设计由于书籍的册数较多，而且要在程序不再运行的时候仍然要保持里面的数据，所以采用文件的形式放到外存储器中，需要操作时，从文件中调入内存来进行查找和排序的工作。12. 简易电子表格的设计问题描述 设计一个支持基本计算统计功能和其他一些表格管理/处理功能的计算机软件，使用户可在该软件的支持下，用互交方式进行表格建立、数据输入、数据编辑及其他一些表格操作。基本要求（1） 建立表格：建立空白表格，同时在屏幕上显示，使其处于可输入数据状态。（2） 输入数据与编辑数据：通过键盘将数据输入到显示在屏幕上的电子表格上，同时要支持基本的数据输入编辑。（3） 基本统计计算：统计计算的种类包括：合计、求平均、求最大/小统计计算方式；表格按行/列统计计算；表格按块统计计算。（4） 排序：使任一行/列中的数据按大小（升或降）排列，对字符串型数据，还要可选大小写敏感。（5） 表格保存：使电子表格存储在磁盘上（磁盘文件），并可随时读入，供继续处理。（6） 数据复制：将表格中任一块数据，复制到另一块中。复制到目标块时，对目标块中原内容，可选择下列几种处理方式：代替、相加、相减、按条件替换。（7） 公式支持：单元格内可输入公式（表达式），使对应单元格的最终内容为公式的计算结果，公式最基本的形式是算术计算公式，公式中可以按名引用其他单元格。13. 停车场模拟管理程序的设计与实现问题描述设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该车辆开出大门，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走，试设计这样一个停车厂模拟管理程序。为了以下描述的方便，停车厂的停车场用“停车位”进行叙述，停车厂的便道用“便道”进行叙述。14. 农夫过河问题的求解问题描述 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，则狼不吃白菜。请求出农夫将所有的东西运过河的方案。数据结构设计求解这个问题的简单方法是步步进行试探，每步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。现在问题变成：从初的状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。实现上述求解的搜索过程可以采用两种不同的策略：一种广度优先搜索，另一种深度优先搜索。这里介绍在广度优先搜索方法中采用的数据结构设计。广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里，由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各种情况的处理。这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及己被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000到1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来实现。顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做route。route的每个分量初始值为-1。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后可以利用route顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。 在具体应用时，采用链队和顺序队均可，为叙述的方便，不妨设为使用顺序队。15. 电话号码查询系统问题描述 设计散列表实现电话号码查找系统。基本要求（1） 设每个记录有下列数据项： 电话号码、用户名、地址；（2） 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；（3） 采用一定的方法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户名的记录。整个系统必须满足系统功能要求；设计不同的散列函数，比较冲突率；在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。16. 跳表（Skip List）的实现与分析基本要求 构造并实现跳表（Skip List）的ADT ADT中应包括初始化、查找、插入、删除等基本操作。 分析各基本操作的时间复杂性。 针对一个实例实现Skip List的动态演示(图形演示)。 17. B-树的实现及分析基本要求 实现在B-树上的查找，并分析其时间复杂性。 实现B-树的ADT，包括其上的基本操作：结点的加入和删除。 要求B-树结构中的M=3或5，实现其中的一种即可。 实现基本操作的动态演示(图形演示)。 18. AVL树的实现及分析。基本要求 编写AVL树判别程序，并判别一个二叉搜索树是否为AVL树。二叉搜索树用其先序遍历结果表示，如：5，2，1，3，7，8。 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除； 实现基本操作的动态演示(图形演示)。19. 长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 长整数长度在一百位以上。 实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, ab mod n, ab mod n。 输入输出均在文件中。 分析算法的时空复杂性。 实现提示 需将长整数的加法转化为多个一般整数加法的组合。 20. 公交线路上优化路径的查询 问题描述 最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为： 线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 例如：63：A(32,45)；B(76,45)；C(76,90)；N(100,100)。1元。5分钟。1/每分钟。 假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。 对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径等等。 基本要求 根据上述公交线路的输入格式，定义并建立合适的图模型。 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x元。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 (4) 实现提示 需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。 21. 文档集合上的查询 问题描述 设计数据结构完成在一个文档集合的存储，并构造算法实现其内容的查询。该设计包括三个部分： (一)应用数据结构完成文档集合的内容(基于单词的)存储，并为下一步的查询建立索引。 (二)就单个单词的查询请求，设计算法进行查询。 (三)对多个单词通过AND和OR构造的复杂查询进行处理(此处可只做两个单词的情况)。 具体情形如下面的例子： Example Doc1: I like the class on data structures and algorithms. Doc2: I hate the class on data structures and algorithms. Doc3: Interesting statistical data may result from this survey. Here are the answers to some queries: Query 1: data Doc1, Doc2, Doc3 Query2: data AND structures Doc1, Doc2 Query 3: like OR survey Doc1, Doc3 文档集合上的查询实例 基本要求 文档集合中的文档数不能少于20个。 数据结构的设计以及查找算法的构造应考虑如何最大程度的提高查询效率。 查询效率的提高应是综合多种查询的，而不是只针对一种查询的优化。 给出查询效率的模拟实验数据。 实现提示 AND和OR查询可转变为单个单词查询结果的组合。 22. 应用堆实现一个优先队列并实现作业的优先调度 问题描述 优先队列priority queue是一种可以用于很多场合的数据结构，应用堆结构设计并实现一个优先队列。应用该优先队列实现作业的优先调度： 一个作业ti =（si，ei），si为作业的开始时间（进入时间），ei为作业的结束时间（离开时间）。作业调度的基本任务是从当前在系统中的作业中选取一个来执行，如果没有作业则执行nop操作。本题目要求的作业调度是基于优先级的调度，每次选取优先级最高的作业来调度，优先级用优先数（每个作业一个优先数pi）表征，优先数越小，优先级越高。作业ti进入系统时，即si时刻，系统给该作业指定其初始优先数pi = ei - si，从而使越短的作业优先级越高。该优先数在作业等待调度执行的过程中会不断减小，调整公式为：pi = pi - wi，其中的wi为作业ti的等待时间：wi = 当前时间-si。一旦作业被调度，该作业就一直执行，不能被抢占，只有当前执行作业指向完成时，才产生下一轮调度。所以可以在每次调度前动态调整各作业的优先数。 编程实现这样一个作业调度系统。 基本要求 给出优先队列的ADT描述，包括队列的逻辑结构及其上基本操作。 以堆结构为辅助结构实现优先队列的存储表示并实现其上的基本操作。 作业集合中的各作业随机生成，根据作业的s属性和e属性动态调整作业队列，不断加入作业，作业结束删除作业。 要对作业调度的结果给出清晰的输出信息，包括：何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等。 23. LZW压缩算法及应用 基本要求 在一个文本文件上实现LZW压缩和解压缩，其中每个字符就是该文本的8位ASCII码。 在实现LZW过程中需要仔细考虑如何在编译表中找到匹配或找不到匹配，需要注意匹配算法的时间、空间开销。 (选做)应用LZW算法实现256色灰度BMP图像文件的压缩和解压缩。 24. 应用等价类生成随机迷宫并寻找迷宫路径问题描述：使用等价类来构造一个NN的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷宫上寻找迷宫路径。该设计共包含如下四个部分： 等价类数据结构的设计和实现 构建随机迷宫 寻找迷宫路径 将迷宫和路径用图形方式画出 用图形方式将上述算法获得的随机迷宫及其上的最短路径画出。用线段来表示迷宫中的墙，用在每个方格中心的点来表示路径。 25. 约瑟夫环(学号： 问题描述：编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，以单循环链表为存储结构设计一个程序以求出出列各人的编号的序列。26. 最小生成树问题(学号： 问题描述：给定一个地区的n个城市间的距离网（要求至少6个城市，10条边），用Prim算法和Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。（分别使用Prim算法和Kruskal算法）27. 交通咨询模拟(学号： 问题描述：建立一个模拟的交通网络（用有向网来表示），编程实现从某个城市出发到另一个城市所需的最短时间及路径。28. 哈夫曼编码译码器(学号： 问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。29. 纸牌游戏(学号： 问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 30. 排序算法(学号： 问题描述：在教材中，各种内排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和移动次数，以取得直观感受。基本要求：设待排序表的表长不小于1000；其中的数据使用随机数，对表中数据使用各种常的内排序方法进行排序；至少使用5组不同的输入数据作比较，比较的指标为每种算法中关键字参与的比较、移动次数（关键字交换计为3次移动）。最后要求对结果作出简单分析，包括对各组数据得出结果波动大小的解释。31. 拓扑排序问题(学号： 问题描述：任意给定一个AOV网络，编写程序检测其是否存在有向回路？ 31. 文章编辑(学号： 问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；32. 订票系统(学号： 此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件问题描述：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 33. 集合运算(学号： 问题描述：编制一个能演示执行集合的并、交和差运算的程序。34. 马踏棋盘 问题描述设计一个国际象棋的马踏遍棋盘的演示程序 设计要求 输入：设计程序按要求输入马的初始位置（相应的坐标） 输出：程序的设计完成后应给出马从初始位置走遍棋盘的过程，并按照求出的行走路线的顺序，将数字1,2，。，64依次填入一个8*8的方阵并输出。 数据结构使用的数据结构是栈。利用顺序栈来实现。此问题是指将马随机放在国际象棋的8*8棋盘的某个方格中，按规则马走日字进行移动。要求每个方格只进入一次，走遍64个方格。从用户给出的初始位置开始判断，按顺时针顺序每次产生一个路点，验证是新路点，则入栈，重复进行。如果一个路点的可扩展路点为0。进行回溯。35. 八皇后问题(学号： 问题描述：设在初始状态下在国际象棋棋盘上无任何棋子（皇后），然后顺序在第1行，第2行，第8行上放置棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足三个限制条件，即任何两个棋子不得放在同一行、或同一列，或同一斜线上。编写一个算法，求解并输出此问题的所有合