数据结构C语言综合训练题目描述

序号项目名称任务描述指导教师英文文本压缩问题描述：利用哈夫曼编码，实现英文文本的压缩和解压缩。基本要求：对于给定的英文文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。能够对于文件的压缩比例进行统计。文本编辑系统（）分别统计出其中英文字母数和空格数及整篇文章总字数；（）统计某一字符串在文章中出现的次数，并输出该次数；（）删除某一子串，并将后面的字符前移。简单算术表达式运算给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。 能够正确处理加减乘除这四种运算； 能够正确处理括号运算。小学生测验系统面向小学 年级学生，随机选择两个整数和加减法形成算式要求学生解答。功能要求：（）电脑随机出道题，每题分，程序结束时显示学生得分；（）确保算式没有超出 年级的水平，只允许进行以内的加减法，不允许两数之和或之差超出 的范围，负数更是不允许的；（）每道题学生有三次机会输入答案，当学生输入错误答案时，提醒学生重新输入，如果三次机会结束则输出正确答案；（）对于每道题，学生第一次输入正确答案得分，第二次输入正确答案得分，第三次输入正确答案得分，否则不得分；（）总成绩以上显示“ ” 显示"O 显示“K 显示"S 以下“I数字游戏的设计实现一个简单的猜数字游戏（）一个四位数，各位上的数字不重复从到。（）按以下提示猜出这个四位数。（）每次猜测输入的数据给出类似的提示*（）其中前的代表你本次猜对了多少个数字。（）其中前的代表你本次猜对的数字并且位置正确的个数。（）给定猜测次数，如果超过次数未猜中，游戏失败。学生成绩管理程序设计一个简单的学生成绩管理程序，要求根据菜单处理相应功能。（）管理功能包括列表、求平均成绩、查找最高分等。（）可按指定的性别或高于指定的个人平均分来筛选列表；（）可按平均成绩排序；（）平均成绩可按个人或科目进行；（）查找可按最高个人平均分进行，或按指定科目的最高分进行；（）每个学生的信息包括：序号、学号、性别、成绩、成绩、

成绩、成绩4（）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除修改学生记录。图书登记管理程序该程序应该具有下列功能：通过键盘输入某本图书的信息；给定图书编号，显示该本图书的信息；给定作者姓名，显示所有该作者编写的图书信息；给定出版社，显示该出版社的所有图书信息；给定图书编号，删除该本图书的信息；提供一些统计各类信息的功能。集合操作用单链表模拟有序集合，实现集合的加入一个兀素、删除一个兀素、集合的交、并、差运算。用单链表存放集合中的元素，链表中的元素按大小存放； 实现集合加入个元素删^除一个元素的元素操作； 实现集合的交、并、差集合操作；树的重构和遍历系统系统菜单信息输入、输出，遍历。个人关系网的设计与实现系统系统菜单信息输入、输出，建图、查询。简单栈和队列演示系统的设计与实现系统菜单信息输入、输出。按每个数的各位值进行排序的系统系统菜单信息输入、输出，排序。学生基本信息管理系统系统菜单信息输入、输出，查询。身份证管理程序该程序应该具有下列功能：通过键盘可以输入身份证信息，大量信息可存放在文件中。身份证包含的信息请参看自己的身份证；给定身份证号码，显示其身份证信息；给定省份的编号，显示该省的人数；给定某区的编号，显示该区的人数；给定身份证号码，可以修改该身份证信息；给定身份证号码，可以删除该身份证信息。学生宿舍管理查询软件设计一个简单的学生宿舍管理查询程序，要求根据菜单处理相应功能。（）建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序（）查询菜单可以用二分查找实现以下操作按姓名查询按学号查询按房号查询等（）可以打印任一查询结果（）每个学生的信息包括：序号、学号、性别、房号、楼号等。

万年历查询程序实现万年历程序功能要求：（）提供菜单方式选择，假定输入的年份在 年之间。0）输入一个年份，输出是在屏幕上显示该年的日历。（）输入年月，输出该月的日历。如：（）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几；（）输入公历的年月日，输出农历年月日。（）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是年到年。二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。二叉排序树的实现要求：分别以顺序表和二叉链表作为储结构，实现二叉排序树。基本操作有插入、删除。管道铺设施工的最佳方案选择功能：设计一个最佳方案使得这个居民区之间铺设煤气管道所需代价最少。数组编码和解码问题的求解设计与实现设有一个数组 存放的7N素为 之间的整数，且不存在重复数据。例如当 时，有： 。此时，数组的编码定义如下 编码为；编码为：在 … 中比的值小的个数 …上面数组的编码为： 要求如下：给出数组利用求解的编码给出数组的编码后，求出中原数据。简易文本编辑器的设计与实现功能：具有图形菜单界面；查找、替换、块移动（行块，列块移动）、删除；具有基本功能。利用哈希表实现电话号码查找系统功能：建立哈希表。选择不同的哈希函数；选择不同的解决冲突的办法。迷宫问题求解要求：对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。排序算法综合功能：数据随机生成；五种常用排序算法实现；从时间上分析效率并比较。简易通讯录的制作功能：输入信息；显示信息；查找以姓名作为关键字；删除信息；存盘；装入。

图的遍历的实现功能：实现图的深度优先广度优先遍历算法，并输出原图结构及遍历结果。稀疏矩阵运算器的设计与实现功能：压缩存储；矩阵的基本运算（加、乘、求逆）；常规矩阵方式输出。小学生作业题练习系统（利用堆栈实现）功能：建立试题库文件，随机产生个题目；题目涉及加减乘除，带括弧的混合运算；给出分数判定；随时可以退出；保留历史分数，能回顾历史，根据历史分数给出评价。一兀多项式的加法、减法、乘法的实现要求：判定是否稀疏；分别采用顺序和链式存储结构实现；结果 中无重复阶项和无零系数项；要求输出结果的升幂和降幂两种排列情况邻接表克鲁斯卡尔算法的实现要求：根据需要建立图的邻接表存储结构；构造最小生成树，模拟演示生成过程。期刊论文管理程序该程序应该具有下列功能： 通过键盘输入某期刊论文的信息，也可以把大量期刊论文信息放在文件中； 给定期刊论文的论文名称，显示该论文的作者信息，作者单位，发表期刊的名称； 给定作者姓名，显示所有该作者发表的期刊论文情况； 给定期刊名称，显示该期刊的所有论文信息；字符串操作编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。在不使用相关的标准库函数的情况下，完成本任务； 实现两个字符串拼接的函数r 实现字符串拷贝的函数 ；实现字符串查找的函数 ； 实现字符串长度计算的函数 ； 实现字符串查找字符的函数 ； 实现字符串替换的函数; 实现字符串替换字符的函数;单源最短路径求解给定一个带权有向图 V其中每条边的权是个非负实数。另外，还给定中的个顶点，成为源。现在计算从源到其他各顶点的最短路径。路径的长度是指路上各边权值之和。歌手比赛系统设计一个简单的歌手比赛绩管理程序，对次歌手比赛的成绩进行管理功能要求：输入每个选手的数据包括编号、姓名、十个评委的成绩，根据输入计算出总成绩和平均成绩（去掉最高分，去掉最低分）。显示主菜单如下：）输入选手数据2评委打分）成绩排序（按

平均分))数据查询)追加学生数据6写入数据文件)退出系统找数字对输入( )个数字在与之间然后统计出这组数种相邻两数字组成的链环数字对出现的次数。例如：输入： 0示要输入数的数目输出 指 、 数字对出现次数分别为次、次二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。中文文本压缩问题描述：利用哈夫曼编码，实现^文本的压缩和解压缩。基本要求：对于给定的E文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。能够对于文件的压缩比例进行统计。邻接矩阵普利姆算法的实现要求：根据需要建立图的邻接矩阵存储结构；构造最小生成树，模拟演示生成过程。邻接矩阵克鲁斯卡尔算法的实现要求：根据需要建立图的邻接矩阵存储结构；构造最小生成树，模拟演示生成过程。元多项式乘法界面友好，函数功能要划分好总体设计应画一流程图程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。学生成绩管理程序设计一个简单的学生成绩管理程序，要求根据菜单处理相应功能。()管理功能包括列表、求平均成绩、查找最高分等。()可按指定的性别或高于指定的个人平均分来筛选列表；()可按平均成绩排序；

（）平均成绩可按个人或科目进行；（）查找可按最高个人平均分进行，或按指定科目的最高分进行；（）每个学生的信息包括：序号、学号、性别、成绩、成绩、成绩、成绩4（）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除修改学生记录。数组操作设计菜单处理程序，对一维数组进行不同的操作。（）操作项目包括求数组最大值、最小值、求和、求平均值、排序、二分查找、有序插入；（）设计并利用字符菜单进行操作项目的选择，程序一次运行可根据选择完成一项或多项操作；通过菜单“退出”来结束程序的运行；（）数组的输入、输出可支持命令行输入文件名、界面输入文件名从数据文件中输入和输出；也支持界面录入。打印日历表打印指定年份的公历表和农历表。（）输入年份为 〜 内任一年；（）可以选择输出公历表或农历表；（）农历表包括二十四节气。学生证管理程序该程序应该具有下列功能：通过键盘输入某位学生的学生证信息。学生证包含的信息请参看自己的学生证；给定学号，显示某位学生的学生证信息；给定某个班级的班号，显示该班所有学生的学生证信息；给定某位学生的学号，修改该学生的学生证信息；给定某位学生的学号，删除该学生的学生证信息；提供一些统计各类信息的功能。图书登记管理程序该程序应该具有下列功能：通过键盘输入某本图书的信息；给定图书编号，显示该本图书的信息；给定作者姓名，显示所有该作者编写的图书信息；给定出版社，显示该出版社的所有图书信息；

给定图书编号，删除该本图书的信息；提供一些统计各类信息的功能。学生学分管理程序假设每位学生必须完成基础课学分、专业课学分、选修课学分、人文类课程学分、实验性课程学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。该程序应该具有下列功能：通过键盘输入某位学生的学分；给定学号，显示某位学生的学分完成情况；给定某个班级的班号，显示该班所有学生学分完成情况；给定某位学生的学号，修改该学生的学分信息；按照某类课程的学分高低进行排序；提供一些统计各类信息的功能。作业完成情况管理程序假设某门课程一学期要留次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩(满分 0。该程序应该具有下列功能：通过键盘输入某位学生某次作业的分数；给定学号，显示某位学生作业完成情况；给定某个班级的班号，显示该班所有学生的作业完成情况；给定某位学生的学号，修改该学生的作业完成信息；给定某位学生的学号，删除该学生的信息；提供一些统计各类信息的功能。旅店机管理系统旅店收款 机管理系统的简单实现。()前台管理：包括空房分等级显示、入住登记、退房结算、洗衣房管理、娱乐项目管理；()后台管理包括客房预定分析、营业额统计、日报表、月报表、年报表)；()设计数据结构文件来实现数据库管理，包括数据录入、查询、删除、修改、更新。学生通讯录管理系统用链表方式来实现学生通讯录管理系统。()通过定义一个包含学生通讯录(主要包括：学号、姓名、系别、专业、籍贯、家庭住址、

联系电话等）的结构体类型，实现增加学生通讯录的内容、删除某个学生通讯录、输出全部学生通讯录内容、根据用户需求查找某个或某些学生的通讯录内容（如：按系别、专业、学号、姓名等内容进行查找）。（）能够实现以上给定的各项功能，具有方便简洁的操作界面，具有一定的容错性。超长正整数的乘法设计一个算法来完成两个超长正整数的乘法。算法提示：首先要设计一种数据结构来表示一个超长的正整数，然后才能够设计算法。个人电话号码查询系统问题描述：实现简单的个人电话号码查询系统，根据用户输入的信息（如姓名，身份证号，电话号码、邮件地址等）进行快速查询。基本要求： 插入：实现将用户的信息插入到系统中； 删除：删除某个用户的信息；修改：修改某个用户的信息； 查询：根据姓名、身份证号等查询用户信息（包括简单条件查询，组合条件查询、模糊查询等）； 排序：对于用户信息进行排序，提高查询速度； 输出：输出用户信息。提示：在内存中，设计数据结构存储电话号码的信息；在外存中，利用文件的形式来保存电话号码信息，系统运行时，将电话号码信息从文件调入内存来进行插入、查找等操作。如果数据的插入删除频繁，可以考虑采取二叉排序树组织电话号码信息（也可采用较复杂的平衡二叉树），可以提高查找和维护的时间性能。选择不同的排序和查找算法，尽可能提高查找和维护性能。数字文本压缩问题描述：利用哈夫曼编码，实现数字文本的压缩和解压缩。基本要求：对于给定的数字文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。能够对于文件的压缩比例进行统计。订票系统基本要求：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班

票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城巾’，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定），可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号；修改航班信息：当航班信息改变可以修改航班数据文件。学籍管理系统问题描述：建立学籍管理系统，实现对于学生信息的添加和维护管理。基本要求：完成学籍登记表中的下面功能（登记表中包括学号、姓名、性别、出生日期、政治面貌、联系方式、家庭住址等信息）。⑴插入：将某学生的基本信息插入到登记表中；⑵删除：将满足条件的基本信息删除；⑶修改：对基本信息的数据项进行修改；⑷查询：查找满足条件的学生；⑸输出：将登记表中的全部（或满足条件）基本信息输出。提高要求：⑴可以添加课程信息（如开课学期、上课时间、上课地点等信息），学生选课信息，实现学生的选课功能；⑵增加学生成绩信息，可以对学生的成绩进行插入、删除、修改等操作；⑶实现查找某学生的选课记录，课程成绩等；⑷利用二叉排序树、平衡树、排序算法等数据结构知识提高排序和查找速度。提示：⑴学生登记表一般建立后，比较少更改，因此，可以采用顺序表方式建立；⑵学生选课、成绩等信息，一般更改比较频繁，则可以采取链表建立；⑶可以将学生的信息存储到文件中；系统运行时，将信息从文件调入到内存中运行。数字游戏的设计（）一个四位数，各位上的数字不重复从到9l）按以下提示猜出这个四位数。

（）每次猜测输入的数据给出类似的提示。（）其中前的代表你本次猜对了多少个数字。（）其中前的代表你本次猜对的数字并且位置正确的个数。稀疏矩阵的压缩与还原一个矩阵含有非零元素比较少，而零元素相对较多，这样的矩阵称为稀疏矩阵，对稀疏矩阵的存彳诸我们不用完全用一维数组来存储，可以用一个三元组，即任意一个稀疏矩阵可以用一个只有三列的二维数组来存放，要求把给定的稀疏矩阵用为三元组表示；同时把三元组转换为稀疏矩阵形式。文章编辑输入页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过个字符。要求：（）分别统计出其中英文字母数和空格数及整篇文章总字数；（）统计某一字符串在文章中出现的次数，并输出该次数；（）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：分行输出用户输入的各行字符；分行输出全部字母数"数字个数"空格个数"文章总字数输出删除某一字符串后的文章；拓扑排序建立有向无环图，并输出拓扑的序列。随机探测再散列哈希表实现随机探测再散列哈希表的创建与查找公园的导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。分步实施

（1）初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括个景点情况，能完成遍历功能；（3）进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。商店存货管理系统建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：（）初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数；（）完成最低要求：建立一个文件，包括个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；（）进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。运动会分数统计输入，统计，排序，查询，信息存储。二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。链表的综合算法设计设有一职工文件，其结构为：职工号、姓名 、部）号 、工资数 、职工号指针 、部门号指针 、工资数指针 设计一程序，从文件中读取记录到单链表中，并完成如下功能：输入：添加一个职工记录； 输出：输出全部职工记录；按排序：通过 指针将职工记录按从小到大链接起来；按输出：沿 链输出全部职工记录；姓 排序：通过 指针将职工记录按 从小到大链接起来；） 输出：沿 链输出全部职工记录；按 排序：通过 指针将职工记录按 从小到大链接起来；） 输出：沿 链输出全部职工记录；全清：删除职工文件中的全部记录；存贮退出：将单链表中的全部结点存贮到职工文件中，然后退出程序运行。

基于哈希表的身份证查询系统的设计与实现设计一个哈希表，实现个人身份证号码查询系统基本要求：（） 设每个记录有下列数据项：身份证号码，电话号码、用户名、用户住址；（） 从键盘输入各记录，分别以身份证号码和用户名为关键字建立哈希表；设计不同的哈希函数，比较冲突率；在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。（）查找并显示给定电话号码用户名的记录。关键路径问题基本要求：（）对一个描述工程的 网，建立其存储结构；（注：数据的输入可以是键盘输入或文件输入两种方式）（）判断该 网是否能够顺利进行。（）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。（注：结果的输出可以是屏幕输出和文件输出两种方式）邮路问题问题描述：一个邮递员从邮局选好邮件去投递，然后回到邮局。当然他必须经过他所管辖的每条街至少次。请为他设计一条投递路线，使其所行的路程尽可能地短。基本要求：（）设计邮递员的辖区，并将其抽象成图结构进行表示，建立其存储结构。注：数据输入可以是键盘输入和文件输入两种方式（）按照输入邮局所在位置，为邮递员设计一条最佳投递路线，要能考虑到辖区般情况。（）界面要求：有合理的提示和人机交互。

元多项式乘法要求：界面友好，函数功能要划分好总体设计应画一流程图程序要加必要的注释要提供程序测试方案程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。文件目录管理系统问题描述：文件是管理用户信息和使用程序的一种工具。每个文件有唯一的文件名，可以通过文件名访问文件，同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。基本要求：函数功能要划分好，程序要有必要的注释。用户通过界面菜单选择以下操作：()生成文件，选择路径和文件名，实现对文件的生成。()删除文件，对指定文件进行删除操作。()修改文件，对指定文件进行内容修改或者文件名修改。()输出该目录结构。简单算术表达式运算给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。能够正确处理加减乘除这四种运算；能够正确处理括号运算；实现提示：首先将算术表达式转化成逆波兰式，然后针对逆波兰式进行运算。机器人布线布线区域分成mXn的方格阵列。要求确定连接方格到方格的最短布线方案。布线的时候，电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记()，其他线路不允许穿过被

XX：x-X■.XXX：X[-.XXXX.XXX"XD封锁的方格。封锁的方格。用文件保存布线区域，用1分别表示某个格子是否有障碍； 表示起点和终点；给出最短的布线路径长度；用文件保存布线路径，用表示布线的方格。开发计算两个字符串间的编辑距离， 距离和距离的函数。（）编辑距离字符串距离字符串和的编辑距离 表示把字符串转换成所需要的最少操作次数，这些操作字符串距离可以是：插入一个字符，删除一个字符，替换一个字符。显然， 越小，，越相似。可按下列公式计算：

ED(0,0)=0ED(0,i)=ED(i,0)=ifED(i-1,j-1) a=b.ED(i,j)=< iJ11+MIN(ED(i-1,j),ED(i,j-1),ED(i-1,j-1)) a中b、 - i j()相似度字符串和的 相似度是和间的最大相同子串的长度。显然 越大，，越相似。，的相似度定义如下：[0 i=0或j=0LCS(i,j)=11+LCS(i-1,j-1) a=bi jMAX(LCS(i-1,j),LCS(i,j-1)) a丰bij() 相似度设 是字符串中长度为的子串的集合。两个字符串 的 相似度定义如下：7、Nggreim((a)cNgram(b)NG(a,b)= \Ngram(a)uNgram(b)越大，字符串，越相似。字符串操作编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。在不使用相关的标准库函数的情况下，完成本任务；实现两个字符串拼接的函数 ；实现字符串拷贝的函数 t实现字符串查找的函数 ；实现字符串长度计算的函数 ；

实现字符串查找字符的函数 ；实现字符串替换的函数 ；实现字符串替换字符的函数 ；集合操作用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。用单链表存放集合中的元素，链表中的元素按大小存放；实现集合加入个元素删除个元素的元素操作；实现集合的交、并、差集合操作。二次探测再散列哈希表实现二次探测再散列哈希表的创建与查找。跳马在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（）在一步能到达的格子（其中黑色的格子是能到达的位置）。£现有一 大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（）和目标位置（），求出马最少需要多少跳才能从当前位置到达目标位置。（）输入：每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标（）和（）y坐标由开始。（）输出：对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。（）输入样例： 输出样例：

输入样例： 输出样例：俄罗斯方块龙哥小度以地使"序来模■注:根寸()4、落下列的矩时候最爱的游戏就是俄罗斯方块巨于根本来不及将方块转向而仅汴来方块与底下已有方块"拟小时候玩俄罗斯方块的过程■■■■■_■■■■■・表示”落卜来方块”■表示”底下已有方块”再输入的矩阵表示出方块的形状翁入包括两个部分：一来方块的矩阵第一行两个小于阵表示方块表示空三了当年他可是个高手每次游戏他都会选择最快的速仅能够进行左右移动为了能够坚持更久必须尽可能匕表面完全贴合在熟悉掌握程序设计后龙哥想要用程下面请你来帮龙哥参谋一下吧YESNO的整数、由空格隔开从下彳行开始是个行

2底下已有方块的矩阵第3个小于的整数、由空格隔开从下6开始是个行列的矩阵表示方块表示空输入底下已有方块矩阵时需确保不存在朝下的表面()输出：根据落下来方块和底下已有方块的形状若落下来方块的下表面与底下已有方块的上表面可能完全贴合则输出一行"”否则输出一行“O棋盘问题(在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放个棋子的所有可行的摆放方案C

输入：每组数据的第行是两个正整数，k用个空格隔开，表示了将在个的矩阵内描述棋盘，以及摆放棋子的数目。 随后的行描述了棋盘的形状：每行有个字符，其中表示棋盘区域， 表示空白区域（数据保证不出现多余的空白行或者空白列）。输出：对于每一组数据，给出一行输出，输出摆放的方案数目（数据保证 ）。输入样例：输出样例：邻接表普利姆算法的实现要求：根据需要建立图的邻接表存储结构；构造最小生成树，模拟演示生成过程。树转换为二叉树树和二叉树是两种不同的数据结构，树实现起来比较麻烦，二叉树实现起来比较容易，因此可以通过把树转换为二叉树进行处理，处理完后在从二叉树还原为树。树和二叉树的定义及转换请参考（清华版数据结构（）,西安交大版数据结构）要求：实现树与二叉树的相互转换树的前序、后序的递归遍历包含树的创建。

本班同学通讯录设计要求：小巧实用，具有添加，查询和删除功能。姓、名、英文名、 号、电子邮箱、籍贯、电话号码组成，姓名可以由字符和数字混合编码。电话号码可由字符和数字组成。实现功能为：系统以菜单方式工作、信息录入功能、信息浏览功能。输入个人关键字信息（电话籍贯号邮箱等，）能实现查询功能、信息修改功能、系统退出功能。学生成绩管理系统。要求：自制两个学生成绩文件，采用文本格式，要求：实现对两个文件数据进行合并，生成新文件抽取出科成绩中有补考的学生并保存到一个新文件中合并后的文件中的数据按总分降序排序实现输入关键字信息的查询功能。实用结构体，链或数组实现上述要求。关键路径问题要求：（）对一个描述工程的网，应判断其是否能够顺利进行。（）若该工程能顺利进行，输出完成整项工程至少需要多长时间，以及每个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。线性探测再散列哈希表实现线性探测再散列哈希表的创建与查找。班级成绩管理系统对一个有个学生的班级，每个学生有门课程。该系统实现对班级成绩的录入、显示、修改、排序、保存等操作的管理。功能要求：（）本系统采用一个结构体数组，每个数据的结构应当包括：学号、姓名、门课程名称。（）本系统显示这样的菜单：请选择系统功能项：a成绩录入b成绩显示c成绩保存d成绩排序e成绩修改（要求先输入密码）

f成绩统计机房机位预定系统台机器，编号到，从早八点到晚八点。两小时一个时间段，每次可预定一个时间段。功能要求：（）系统以菜单方式工作（）查询，根据输入时间，输出机位信息。（）机位预定，根据输入的时间查询是否有空机位，若有则预约，若无则提供最近的时间段，另：若用户在非空时间上机，则将用户信息列入等待列表。（）退出预定，根据输入的时间，机器号撤销该事件的预定！（）查询是否有等待信息，若有则提供最优解决方案（等待时间尽量短），若无则显示提示信息。万年历查询程序。功能要求：（）提供菜单方式选择（）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几；（）输入公历的年月日，输出农历年月日。（）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是 年到 年。汉诺塔移动输入盘子数（个以上有效），移动速度，开始演示汉诺塔移动的步骤，要求：盘子，AB柱需要自己绘制，初始时盘子在柱上通过柱最终移动到柱上，显示出盘子在几个柱之间的移动过程。运动会比赛计分系统要求：初始化输入：参赛学校总数，男子竞赛项目数，女子竞赛项目数各项目名次取法有如下几种：取前名：第一名得分分，第二名得分，第三名得分，第四名得分，第五名得分1取前名：第一名得分，第二名得分，第三名得分2功能要求：（）系统以菜单方式工作（）由程序提醒用户填写比赛结果，输入各项目获奖运动员信息。

()所有信息记录完毕后，用户可以查询各个学校的比赛成绩()查看参赛学校信息和比赛项目信息等。的实现及分析作为有序链表结构的一种扩展，如下图所示，其中是普通的单链表；而是在次基础上加上第二层( )的额外指针，这些额外的指针指向间隔为的下一个结点， 因此得名；类似的是加上 后的 ；是加上 后的。"rH-H3161d-4Trn-H川d-d.+HI“n-n回 nil■ , *■ )CA 4 *| 4"* -门- T、，HIL1 +*l +*! 41*1-*1与利-|4"— _|—r-| 2r± .1-1-1 2-1± .1—mNIL十卜科印4埼斗#］小阳环」-基本结构示意图上查找的基本思想是先从最高的 层上查找，找到 所在的范围后，再从较低的层次继续重复查找操作，直到 。

Act,7"ifh /{i} t\一出门•；“//1?|4—__K J8L 上 .。 [_1 7： ongina/!isl,17toheinserted■ ■-. ■-— （i— i—r-i i-r-i _— nil_A .__ _L .__ 9_L .__, 17_Li ._._ .__. _J工 .__„I4T:■I4T1+T71T~TITHi?"1g而滤摭诲蹒志1s插入操作的示意图上的删除操作只需直接删除元素即可（包括指针的修整）。构造并实现 的，同时实现双向 的及循环的 D基本要求① 中应包括初始化、查找、插入、删除等基本操作。②分析各基本操作的时间复杂性。③针对个实例实现 的动态演示图形演示）的实现及分析是一类满足特殊条件的路查找树。首先说明路查找树，路查找树是二元查找树的一般化，其结构如下图所示的路查找树：路查找树中的任一结点至多存放个数据，并至多拥有棵子树；每个结点中的数据按升序排列M每个数据 都存在一棵左子树和一棵右子树，如果左子树不空的话，该子树中所有结点的值都小于 如果右子树不空的话，该子树中所有结点的值都大于。

10是满足如下两个条件的路查找树:①所有叶结点的高度相同。②除根之外的所有结点都至少是半满的，即该结点包含或更多的值。下图是一个树的实例。路树的结构示意图基本要求①实现在树上的查找，并分析其时间复杂性。②实现树的，包括其上的基本操作：结点的加入和删除。要求树结构中的或，实现其中的一种即可。实现基本操作的演示。

的实现及分析树是株平衡的二兀查找树。株平衡的二兀树就是指对其每一个结点，其左子树和右子树的高度之差不超过1下图就是一个 树的实例。编写程序实现树的判别；并实现树的，包括其上的基本操作：结点的加入和删除。和的差别就在平衡性上，所以的操作关键要考虑如《可在保持二元查找树定义条件下对二元树进行平衡化。基本要求①编写 树判别程序，并判别一个二元查找树是否为树。二元查找树用其先序遍历结果表示，如：5 2 1 3 7 8②实现树的D包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为 树的操作。汽车租借公司的管理问题描述设计数据结构及算法完成某个汽车租借公司日常工作的组织与管理。该管理系统的基本管理对象为汽车，每台汽车用个 进行唯一标识。每个汽车存在三种可能状态：•可以租借（ ）-已借（ ）.修理中（ ）其中在 队列中汽车应该依据汽车行驶过的路程进行排序，行驶路程最少的汽车排在最前面。在 队列中的汽车应依据其预期返回时间进行排序，排在最前的应是预期最早返回的汽车。课程设计目的使用线性数据结构存储信息，并能够使用上面的基本操作实现事务管理。基本要求①用三个链表组织三种状态的汽车。②能够实现租借的日常事务：引入新车，租借，收费，修理等。③租借收费应根据汽车行驶的路程及借去的时间综合计算得出，路程收费标准如下：

低于 收费 兀以外的路程枚收费 元④汽车根据行驶的路程定期进行维护。⑤还需实现辅助操作：汽车查询，打印全部信息，计算并打印收入、成本及收益。⑥管理系统应有完整地界面（最好是图形化界面）。实现提示主要集中在链表的基本操作上。长整数的加减计算问题描述设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减等基本代数运算。课程设计目的能够使用线性数据结构解决实际问题。基本要求长整数长度在一百位以上。实现两长整数在同余代数下的加、减操作。即实现算法来求解 。输入输出均在文件中。分析算法的时空复杂性。实现提示需将长整数的加法转化为多个一般整数加口法的组合。迷宫的生成与路由问题描述设计算法生成一个X行列的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较包括理论和实验三种方法的时空复杂性。课程设计目的理解栈的使用，理解深广度优先思想，理解问题的理论和实验分析。基本要求①和是用户可配置的，缺省值为和0

迷宫的入口和出口分别在第行和第 行上，随机选择。生成的迷宫要求是连通的。实现图形化界面可用 ,也可用语言的图形库）三种方法的试验比较应该在多个迷宫实例上尤其可以选一些特定的迷宫）实现提示多考虑栈上的运算。使用堆实现一个优先队列问题描述优先队列 是一种可以用于很多场合的数据结构，该结构支持如下几本操作：-将元素插入集合-返回中最小的关键字• - （删除中的最小关键字可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的一部分。此处由于要用堆实现队列，所以堆结构的存储表示要求用数组。课程设计目的堆结构的使用，优先队列的构造。基本要求①给出优先队列的描述，包括队列的逻辑结构及其上基本操作。②以堆结构为辅助结构实现优先队列的存储表示并实现其上的基本操作。③使用优先队列的 实现根据学生成绩对学生信息进行排序输出。④学生信息存放在文本文件中（格式自定，内容自行输入）。实现提示出队、入队需考虑优先性。教学计划编制问题问题描述针对西北农林科技大学信息学院本科课程，依据其相互依赖关系制定课程安排计划，并要求各学期课程数目大致相同且搭配适当。课程设计目的

掌握图上的基本算法，以及集合的划分。基本要求①求解上图的拓扑排序结果。②上述课程在学期上完，要求每学期上课的门数大致一样。③每学期的课程应尽量搭配适当，即在每学期内同一系列的课程不要太多。实现提示在拓扑排序基础上作适当修改。集合的等价划分问题描述构造集合结构的抽象数据型，并在此基础上进行集合的等价划分。课程设计目的掌握集合的表示方法，并设计等价划分算法。基本要求①选择合理的结构完成集合的表示要求以 的形式给出实②在进行等价划分前，等价关系需用户输入从文件输入，格式自定实③需要验证用户输入的关系是否为等价关系。④对集合进行等价划分，且要分析该划分的时空复杂性。实现提示可用树结构来表示集合，如果能进行适当的优化并给出理由和实验分析结果将更好。符号文本压缩问题描述：利用哈夫曼编码，实现符号文本的压缩和解压缩。基本要求：对于给定的符号文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。能够对于文件的压缩比例进行统计。多项式链式存储结构及其代数运算问题描述设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进彳亍不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一个可用空间表i把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这个单链表。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。

（）设计目的掌握循环链表的存储结构及其操作；能够运用循环链表的存储结构表示多项式，并进行代数运算。基本要求设计多项式的存储结构，编写并测试下列函数：和 ，从向可用空间表申请和插入一个多项式结点。e读取个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。，输出多项式，采用能够清楚显示的形式。，计算 。不改变和。，计算 。不改变和。u计算 。不改变和。，计算多项式在某点的值，其中是一个浮点型常量。返回结果为浮点数。，^把存储表示为循环链表的多项式返还给可用空间表。（）实现提示为了进一步简化加法算法，把多项式的头结点的指数域设为稀疏矩阵的完全链表表示及其运算问题描述稀疏矩阵的每个结点包含， ，，和 五个域。用单独一个结点表示个非零项，并将所有结点连接在一起，形成两个循环链表。使得第个表即行表，把所有结点按照行序（同一行内按列序）用 域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。（）设计目的认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。（）读取一个稀疏矩阵建立其完全链表表示

()输出一个稀疏矩阵的内容()删除一个稀疏矩阵()两个稀疏矩阵相加()两个稀疏矩阵相减()两个稀疏矩阵相乘()稀疏矩阵的转置()实现提示