数据结构与C语言综合训练_题目描述.doc

数据结构与C语言综合训练实习序号项目名称任务描述指导教师1英文文本压缩问题描述：利用哈夫曼编码，实现英文文本的压缩和解压缩。基本要求：对于给定的英文文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：(1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。(2)能够对于文件的压缩比例进行统计。2文本编辑系统（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。3简单算术表达式运算给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。(1)能够正确处理加减乘除这四种运算；(2)能够正确处理括号运算。4小学生测验系统面向小学12年级学生，随机选择两个整数和加减法形成算式要求学生解答。功能要求：（1）电脑随机出10道题，每题10分，程序结束时显示学生得分；（2）确保算式没有超出12年级的水平，只允许进行50以内的加减法，不允许两数之和或之差超出050的范围，负数更是不允许的；（3）每道题学生有三次机会输入答案，当学生输入错误答案时，提醒学生重新输入，如果三次机会结束则输出正确答案；（4）对于每道题，学生第一次输入正确答案得10分，第二次输入正确答案得7分，第三次输入正确答案得5分，否则不得分；（5）总成绩90以上显示“SMART”,80-90显示“GOOD”，70-80显示“OK”,60-70显示“PASS”，60以下“TRY AGAIN”。5数字游戏的设计实现一个简单的猜数字游戏（1）一个四位数，各位上的数字不重复,从1到9。（2）按以下提示猜出这个四位数。 （3）每次猜测输入的数据给出类似的提示*A*B。（4）其中A前的*代表你本次猜对了多少个数字。 （5）其中B前的*代表你本次猜对的数字并且位置正确的个数。（6）给定猜测次数，如果超过次数未猜中，游戏失败。6学生成绩管理程序设计一个简单的学生成绩管理程序，要求根据菜单处理相应功能。（1）管理功能包括列表、求平均成绩、查找最高分等。（2）可按指定的性别或高于指定的个人平均分来筛选列表；（3）可按平均成绩排序；（4）平均成绩可按个人或科目进行；（5）查找可按最高个人平均分进行，或按指定科目的最高分进行；（6）每个学生的信息包括：序号、学号、性别、成绩1、成绩2、成绩3、成绩4；（7）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除/修改学生记录。7图书登记管理程序该程序应该具有下列功能：(1) 通过键盘输入某本图书的信息；(2) 给定图书编号，显示该本图书的信息；(3) 给定作者姓名，显示所有该作者编写的图书信息；(4) 给定出版社，显示该出版社的所有图书信息；(5) 给定图书编号，删除该本图书的信息；(6) 提供一些统计各类信息的功能。8集合操作用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。(1)用单链表存放集合中的元素，链表中的元素按大小存放；(2)实现集合加入一个元素删除一个元素的元素操作；(3)实现集合的交、并、差集合操作；9树的重构和遍历系统系统菜单,信息输入、输出，遍历。10个人关系网的设计与实现系统系统菜单,信息输入、输出，建图、查询。11简单栈和队列演示系统的设计与实现系统菜单,信息输入、输出。12按每个数的各位值进行排序的系统系统菜单,信息输入、输出，排序。13学生基本信息管理系统系统菜单,信息输入、输出，查询。14身份证管理程序该程序应该具有下列功能：(1) 通过键盘可以输入身份证信息，大量信息可存放在文件中。身份证包含的信息请参看自己的身份证；(2) 给定身份证号码，显示其身份证信息；(3) 给定省份的编号，显示该省的人数；(4) 给定某区的编号，显示该区的人数；(5) 给定身份证号码，可以修改该身份证信息；(6) 给定身份证号码，可以删除该身份证信息。15学生宿舍管理查询软件设计一个简单的学生宿舍管理查询程序，要求根据菜单处理相应功能。（1）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序 （2）查询菜单: (可以用二分查找实现以下操作)A. 按姓名查询 B. 按学号查询 C. 按房号查询等（3）可以打印任一查询结果（4）每个学生的信息包括：序号、学号、性别、房号、楼号等。16万年历查询程序实现万年历程序功能要求：（1）提供菜单方式选择，假定输入的年份在1940-2040年之间。（2）输入一个年份，输出是在屏幕上显示该年的日历。（3）输入年月，输出该月的日历。如：（4）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几；（5）输入公历的年月日，输出农历年月日。（6）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是1940年到2040年。17二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。18二叉排序树的实现要求：分别以顺序表和二叉链表作为储结构，实现二叉排序树。基本操作有插入、删除。19管道铺设施工的最佳方案选择功能：设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最少。20数组编码和解码问题的求解设计与实现设有一个数组A: array0.N-1;存放的元素为0-N-1(1N=10)之间的整数，且不存在重复数据。例如当N=6时，有：A=(4,3,0,5,1,2)。此时，数组A的编码定义如下:A0编码为0；Ai编码为：在A0,A1,Ai-1中比Ai的值小的个数(i=1,2,N-1)上面数组A的编码为：B=(0,0,0,3,1,2)要求如下：给出数组A, 利用C 求解A的编码.给出数组A的编码后，求出A中原数据。21简易文本编辑器的设计与实现功能：具有图形菜单界面；查找、替换、块移动（行块，列块移动）、删除；具有基本功能。22利用哈希表实现电话号码查找系统功能：建立哈希表。选择不同的哈希函数；选择不同的解决冲突的办法。23迷宫问题求解要求：对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。24排序算法综合功能：数据随机生成；五种常用排序算法实现；从时间上分析效率并比较。25简易通讯录的制作功能：输入信息； 显示信息； 查找以姓名作为关键字； 删除信息； 存盘； 装入。26图的遍历的实现功能：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。27稀疏矩阵运算器的设计与实现功能：压缩存储；矩阵的基本运算（加、乘、求逆）；常规矩阵方式输出。28小学生作业题练习系统（利用堆栈实现）功能：建立试题库文件，随机产生n个题目； 题目涉及加减乘除，带括弧的混合运算；给出分数判定； 随时可以退出； 保留历史分数，能回顾历史，根据历史分数给出评价。29一元多项式的加法、减法、乘法的实现要求：判定是否稀疏；分别采用顺序和链式存储结构实现；结果M(x)中无重复阶项和无零系数项；要求输出结果的升幂和降幂两种排列情况30邻接表克鲁斯卡尔算法的实现要求：根据需要建立图的邻接表存储结构；构造最小生成树，模拟演示生成过程。31期刊论文管理程序该程序应该具有下列功能：(1) 通过键盘输入某期刊论文的信息，也可以把大量期刊论文信息放在文件中；(2) 给定期刊论文的论文名称，显示该论文的作者信息，作者单位，发表期刊的名称；(3) 给定作者姓名，显示所有该作者发表的期刊论文情况；(4) 给定期刊名称，显示该期刊的所有论文信息；32字符串操作编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。(1)在不使用相关的标准库函数的情况下，完成本任务；(2)实现两个字符串拼接的函数strcat(str1, str2)；(3)实现字符串拷贝的函数strcpy(str1,str2)；(4)实现字符串查找的函数strcstr(str1,str2)；(5)实现字符串长度计算的函数strlen(str1)；(6)实现字符串查找字符的函数strcchar(str1,c)；(7)实现字符串替换的函数strcreplacestr(str1,str2,str3)；(8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)；33单源最短路径求解给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，成为源。现在计算从源到其他各顶点的最短路径。路径的长度是指路上各边权值之和。34歌手比赛系统设计一个简单的歌手比赛绩管理程序，对一次歌手比赛的成绩进行管理功能要求：1.输入每个选手的数据包括编号、姓名、十个评委的成绩，根据输入计算出总成绩和平均成绩（去掉最高分，去掉最低分）。2.显示主菜单如下：1）输入选手数据 2）评委打分 3）成绩排序（按平均分）4）数据查询 5）追加学生数据 6）写入数据文件7）退出系统35找数字对输入N（2=N=100）个数字(在0与9之间),然后统计出这组数种相邻两数字组成的链环数字对出现的次数。例如：输入：N=20 表示要输入数的数目0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9输出(7,8)=2 (8,7)=3指(7,8)、(8,7)数字对出现次数分别为2次、3次36二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。37中文文本压缩问题描述：利用哈夫曼编码，实现中文文本的压缩和解压缩。基本要求：对于给定的中文文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：(1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。(2)能够对于文件的压缩比例进行统计。38邻接矩阵普利姆算法的实现要求：根据需要建立图的邻接矩阵存储结构；构造最小生成树，模拟演示生成过程。39邻接矩阵克鲁斯卡尔算法的实现要求：根据需要建立图的邻接矩阵存储结构；构造最小生成树，模拟演示生成过程。40n元多项式乘法(1) 界面友好，函数功能要划分好(2) 总体设计应画一流程图(3) 程序要加必要的注释(4) 要提供程序测试方案(5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。41学生成绩管理程序设计一个简单的学生成绩管理程序，要求根据菜单处理相应功能。（1）管理功能包括列表、求平均成绩、查找最高分等。（2）可按指定的性别或高于指定的个人平均分来筛选列表；（3）可按平均成绩排序；（4）平均成绩可按个人或科目进行；（5）查找可按最高个人平均分进行，或按指定科目的最高分进行；（6）每个学生的信息包括：序号、学号、性别、成绩1、成绩2、成绩3、成绩4；（7）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除/修改学生记录。42数组操作设计菜单处理程序，对一维数组进行不同的操作。（1）操作项目包括求数组最大值、最小值、求和、求平均值、排序、 二分查找、有序插入；（2）设计并利用字符菜单进行操作项目的选择，程序一次运行可根据选择完成一项或多项操作；通过菜单“退出”来结束程序的运行；（3）数组的输入、输出可支持命令行输入文件名、界面输入文件名从数据文件中输入和输出；也支持界面录入。43打印日历表打印指定年份的公历表和农历表。（1）输入年份为19902050内任一年；（2）可以选择输出公历表或农历表；（3）农历表包括二十四节气。44学生证管理程序该程序应该具有下列功能：(1) 通过键盘输入某位学生的学生证信息。学生证包含的信息请参看自己的学生证；(2) 给定学号，显示某位学生的学生证信息；(3) 给定某个班级的班号，显示该班所有学生的学生证信息；(4) 给定某位学生的学号，修改该学生的学生证信息；(5) 给定某位学生的学号，删除该学生的学生证信息；(6) 提供一些统计各类信息的功能。45图书登记管理程序该程序应该具有下列功能：(1) 通过键盘输入某本图书的信息；(2) 给定图书编号，显示该本图书的信息；(3) 给定作者姓名，显示所有该作者编写的图书信息；(4) 给定出版社，显示该出版社的所有图书信息；(5) 给定图书编号，删除该本图书的信息；(6) 提供一些统计各类信息的功能。46学生学分管理程序假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。该程序应该具有下列功能：(1) 通过键盘输入某位学生的学分； (2) 给定学号，显示某位学生的学分完成情况；(3) 给定某个班级的班号，显示该班所有学生学分完成情况；(4) 给定某位学生的学号，修改该学生的学分信息；(5) 按照某类课程的学分高低进行排序；(6) 提供一些统计各类信息的功能。47作业完成情况管理程序假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。该程序应该具有下列功能：(1) 通过键盘输入某位学生某次作业的分数；(2) 给定学号，显示某位学生作业完成情况；(3) 给定某个班级的班号，显示该班所有学生的作业完成情况；(4) 给定某位学生的学号，修改该学生的作业完成信息；(5) 给定某位学生的学号，删除该学生的信息；(6) 提供一些统计各类信息的功能。48旅店POS机管理系统旅店收款POS机管理系统的简单实现。（1）前台管理：包括空房分等级显示、入住登记、退房结算、洗衣房管理、娱乐项目管理；（2）后台管理包括客房预定分析、营业额统计、日报表、月报表、年报表）；（3）设计数据结构文件来实现数据库管理，包括数据录入、查询、删除、修改、更新。49学生通讯录管理系统用链表方式来实现学生通讯录管理系统。（1）通过定义一个包含学生通讯录（主要包括：学号、姓名、系别、专业、籍贯、家庭住址、联系电话等）的结构体类型，实现增加学生通讯录的内容、删除某个学生通讯录、输出全部学生通讯录内容、根据用户需求查找某个或某些学生的通讯录内容（如：按系别、专业、学号、姓名等内容进行查找）。（2）能够实现以上给定的各项功能，具有方便简洁的操作界面，具有一定的容错性。50超长正整数的乘法设计一个算法来完成两个超长正整数的乘法。算法提示：首先要设计一种数据结构来表示一个超长的正整数，然后才能够设计算法。51个人电话号码查询系统问题描述：实现简单的个人电话号码查询系统，根据用户输入的信息（如姓名，身份证号，电话号码、邮件地址等）进行快速查询。基本要求： (1) 插入：实现将用户的信息插入到系统中；(2) 删除：删除某个用户的信息；(3) 修改：修改某个用户的信息；(4) 查询：根据姓名、身份证号等查询用户信息（包括简单条件查询，组合条件查询、模糊查询等）；(5) 排序：对于用户信息进行排序，提高查询速度；(6) 输出：输出用户信息。提示：(1) 在内存中，设计数据结构存储电话号码的信息；在外存中，利用文件的形式来保存电话号码信息，系统运行时，将电话号码信息从文件调入内存来进行插入、查找等操作。(2) 如果数据的插入删除频繁，可以考虑采取二叉排序树组织电话号码信息（也可采用较复杂的平衡二叉树），可以提高查找和维护的时间性能。(3) 选择不同的排序和查找算法，尽可能提高查找和维护性能。52数字文本压缩问题描述：利用哈夫曼编码，实现数字文本的压缩和解压缩。基本要求：对于给定的数字文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：(1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。(2)能够对于文件的压缩比例进行统计。53订票系统基本要求：(1)录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）(2)查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；(3)可以输入起飞抵达城市，查询飞机航班情况；(4)订票：（订票情况可以存在一个数据文件中，结构自己设定），可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号；(5)修改航班信息：当航班信息改变可以修改航班数据文件。54学籍管理系统问题描述：建立学籍管理系统，实现对于学生信息的添加和维护管理。基本要求：完成学籍登记表中的下面功能（登记表中包括学号、姓名、性别、出生日期、政治面貌、联系方式、家庭住址等信息）。 插入：将某学生的基本信息插入到登记表中； 删除：将满足条件的基本信息删除； 修改：对基本信息的数据项进行修改； 查询：查找满足条件的学生； 输出：将登记表中的全部（或满足条件）基本信息输出。提高要求： 可以添加课程信息（如开课学期、上课时间、上课地点等信息），学生选课信息，实现学生的选课功能； 增加学生成绩信息，可以对学生的成绩进行插入、删除、修改等操作； 实现查找某学生的选课记录，课程成绩等； 利用二叉排序树、平衡树、排序算法等数据结构知识提高排序和查找速度。提示： 学生登记表一般建立后，比较少更改，因此，可以采用顺序表方式建立； 学生选课、成绩等信息，一般更改比较频繁，则可以采取链表建立； 可以将学生的信息存储到文件中；系统运行时，将信息从文件调入到内存中运行。55数字游戏的设计（1）一个四位数，各位上的数字不重复,从1到9。（2）按以下提示猜出这个四位数。（3）每次猜测输入的数据给出类似的提示*A*B。（4）其中A前的*代表你本次猜对了多少个数字。（5）其中B前的*代表你本次猜对的数字并且位置正确的个数。56稀疏矩阵的压缩与还原一个矩阵含有非零元素比较少，而零元素相对较多，这样的矩阵称为稀疏矩阵，对稀疏矩阵的存储我们不用完全用二维数组来存储，可以用一个三元组，即任意一个稀疏矩阵可以用一个只有三列的二维数组来存放， 要求把给定的稀疏矩阵用为三元组表示；同时把三元组转换为稀疏矩阵形式。57文章编辑输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符。要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：(1) 分行输出用户输入的各行字符；(2) 分4行输出全部字母数、数字个数、空格个数、文章总字数(3) 输出删除某一字符串后的文章；58拓扑排序建立有向无环图，并输出拓扑的序列。59随机探测再散列哈希表实现随机探测再散列哈希表的创建与查找60公园的导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。分步实施：(1) 初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数；(2) 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；(3) 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。61商店存货管理系统建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。分步实施：（1）初步完成总体设计，建好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；（3）进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。62运动会分数统计输入，统计，排序，查询，信息存储。63二叉树遍历算法的实现四种算法都是前序、中序、后序三种算法要求递归和非递归实现，层遍历用非递归实现。64链表的综合算法设计设有一职工文件，其结构为：职工号(no)、姓名(name)、部门号(depno)、工资数(salary)、职工号指针(pno)、部门号指针(pdepno)、工资数指针(psalary),设计一程序，从一文件中读取记录到单链表中，并完成如下功能：(1) 输入：添加一个职工记录；(2) 输出：输出全部职工记录；(3) 按no排序：通过pno指针将职工记录按no从小到大链接起来；(4) 按no输出：沿pno链输出全部职工记录；(5) 按depno排序：通过pdepno指针将职工记录按depno从小到大链接起来；(6) 按depno输出：沿pdepno链输出全部职工记录；(7) 按salary排序：通过psalary指针将职工记录按salary从小到大链接起来；(8) 按salary输出：沿psalary链输出全部职工记录；(9) 全清：删除职工文件中的全部记录；(10) 存贮退出：将单链表中的全部结点存贮到职工文件中，然后退出程序运行。65基于哈希表的身份证查询系统的设计与实现设计一个哈希表，实现个人身份证号码查询系统基本要求：（1） 设每个记录有下列数据项：身份证号码，电话号码、用户名、用户住址；（2） 从键盘输入各记录，分别以身份证号码和用户名为关键字建立哈希表； a) 设计不同的哈希函数，比较冲突率；b) 在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。（3） 查找并显示给定电话号码/用户名的记录。66关键路径问题基本要求：（1）对一个描述工程的AOE网，建立其存储结构；（注：数据的输入可以是键盘输入或文件输入两种方式）（2）判断该AOE网是否能够顺利进行。（3）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。（注：结果的输出可以是屏幕输出和文件输出两种方式）67邮路问题问题描述：一个邮递员从邮局选好邮件去投递，然后回到邮局。当然他必须经过他所管辖的每条街至少一次。请为他设计一条投递路线，使其所行的路程尽可能地短。基本要求：（1）设计邮递员的辖区，并将其抽象成图结构进行表示，建立其存储结构。 (注：数据输入可以是键盘输入和文件输入两种方式)（2）按照输入邮局所在位置，为邮递员设计一条最佳投递路线，要能考虑到辖区一般情况。（3）界面要求：有合理的提示和人机交互。68n元多项式乘法要求：(1) 界面友好，函数功能要划分好(2) 总体设计应画一流程图(3) 程序要加必要的注释(4) 要提供程序测试方案(5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。69文件目录管理系统问题描述：文件是管理用户信息和应用程序的一种工具。每个文件有唯一的文件名，可以通过文件名访问文件，同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。基本要求：函数功能要划分好，程序要有必要的注释。用户通过界面菜单选择以下操作： （1） 生成文件，选择路径和文件名，实现对文件的生成。（2） 删除文件，对指定文件进行删除操作。（3） 修改文件，对指定文件进行内容修改或者文件名修改。（4） 输出该目录结构。70简单算术表达式运算给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。(1)能够正确处理加减乘除这四种运算；(2)能够正确处理括号运算；实现提示： 首先将算术表达式转化成逆波兰式，然后针对逆波兰式进行运算。71机器人布线布线区域分成的方格阵列。要求确定连接方格s到方格d的最短布线方案。布线的时候，电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记（X），其他线路不允许穿过被封锁的方格。(1)用文件保存布线区域，用1、0分别表示某个格子是否有障碍；S,D表示起点和终点；(2)给出最短的布线路径长度； (3)用文件保存布线路径，用*表示布线的方格。72字符串距离开发计算两个字符串间的编辑距离，LCS距离和N-gram距离的函数。（1）编辑距离字符串a和b的编辑距离ED(i,j)表示把字符串a转换成b所需要的最少操作次数，这些操作可以是：插入一个字符，删除一个字符，替换一个字符。显然，ED(i,j)越小，a，b越相似。ED(i,j)可按下列公式计算：（2）LCS相似度字符串a和b的LCS(Longest Common Subsequence)相似度是a和b间的最大相同子串的长度。显然LCS(i,j)越大，a，b越相似。a，b的LCS相似度定义如下：（3）N-gram相似度设Ngram(a) 是字符串a中长度为N的子串的集合。两个字符串a,b的N-gram相似度NG(a,b)定义如下：NG(a,b)越大，字符串a，b越相似。73字符串操作编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。(1)在不使用相关的标准库函数的情况下，完成本任务；(2)实现两个字符串拼接的函数strcat(str1, str2)；(3)实现字符串拷贝的函数strcpy(str1,str2)；(4)实现字符串查找的函数strcstr(str1,str2)；(5)实现字符串长度计算的函数strlen(str1)；(6)实现字符串查找字符的函数strcchar(str1,c)；(7)实现字符串替换的函数strcreplacestr(str1,str2,str3)；(8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)；74集合操作用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。(1)用单链表存放集合中的元素，链表中的元素按大小存放；(2)实现集合加入一个元素删除一个元素的元素操作；(3)实现集合的交、并、差集合操作。75二次探测再散列哈希表实现二次探测再散列哈希表的创建与查找。76跳马在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。（1）输入：每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。（2）输出：对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。（3）输入样例： 1 1 2 1 输出样例：3输入样例： 1 5 5 1 输出样例：477俄罗斯方块龙哥小时候最爱的游戏就是俄罗斯方块了,当年他可是个高手,每次游戏他都会选择最快的速度,以至于根本来不及将方块转向而仅仅能够进行左右移动.为了能够坚持更久,必须尽可能地使落下来方块与底下已有方块上表面完全贴合.在熟悉掌握程序设计后龙哥想要用程序来模拟小时候玩俄罗斯方块的过程,下面请你来帮龙哥参谋一下吧:-)（1）输入包括两个部分：1、落下来方块的矩阵(第一行两个小于5的整数a、b由空格隔开,从下一行开始是一个a行b列的矩阵,1表示方块,0表示空)2、底下已有方块的矩阵(第一行两个小于10的整数c、d由空格隔开,从下一行开始是一个c行d列的矩阵,1表示方块,0表示空.输入底下已有方块矩阵时需确保不存在朝下的表面)（2）输出：根据落下来方块和底下已有方块的形状,若落下来方块的下表面与底下已有方块的上表面可能完全贴合则输出一行“YES”否则输出一行“NO”Sample Input2 31110103 80010000010100011111101113 21110102 81100111011011111Sample OutputYESNO78棋盘问题（OJ1255)在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。输入：每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n = 8 , k = n 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。输出：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C231）。输入样例：2 1#.#4 4.#.#.#.#.输出样例：2179邻接表普利姆算法的实现要求：根据需要建立图的邻接表存储结构；构造最小生成树，模拟演示生成过程。80树转换为二叉树树和二叉树是两种不同的数据结构，树实现起来比较麻烦，二叉树实现起来比较容易，因此可以通过把树转换为二叉树进行处理，处理完后在从二叉树还原为树。树和二叉树的定义及转换请参考（清华版数据结构（c），西安交大版数据结构(c)）要求：a:实现树与二叉树的相互转换;b:树的前序、后序的递归遍历;c:包含树的创建。81本班同学通讯录设计要求：小巧实用，具有添加，查询和删除功能。姓、名、英文名、QQ号、电子邮箱、籍贯、电话号码组成，姓名可以由字符和数字混合编码。电话号码可由字符和数字组成。实现功能为：系统以菜单方式工作、信息录入功能、信息浏览功能。输入个人关键字信息（电话/籍贯/QQ号/邮箱等，）能实现查询功能、信息修改功能、系统退出功能。82学生成绩管理系统。要求：自制两个学生成绩文件，采用文本格式，要求：实现对两个文件数据进行合并，生成新文件1抽取出3科成绩中有补考的学生并保存到一个新文件2中合并后的文件1中的数据按总分降序排序实现输入关键字信息的查询功能。实用结构体，链或数组实现上述要求。83关键路径问题要求：（1）对一个描述工程的AOE网，应判断其是否能够顺利进行。 （2）若该工程能顺利进行，输出完成整项工程至少需要多长时间，以及每个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。84线性探测再散列哈希表实现线性探测再散列哈希表的创建与查找。85班级成绩管理系统对一个有N个学生的班级，每个学生有M门课程。该系统实现对班级成绩的录入、显示、修改、排序、保存等操作的管理。功能要求：（1）本系统采用一个结构体数组，每个数据的结构应当包括：学号、姓名、M门课程名称。（2）本系统显示这样的菜单：请选择系统功能项：a、成绩录入b、成绩显示c、成绩保存d、成绩排序e、成绩修改（要求先输入密码）f、成绩统计86机房机位预定系统20台机器，编号1到20，从早八点到晚八点。两小时一个时间段，每次可预定一个时间段。功能要求：（1）系统以菜单方式工作（2）查询，根据输入时间，输出机位信息。（3）机位预定，根据输入的时间查询是否有空机位，若有则预约，若无则提供最近的时间段，另：若用户在非空时间上机，则将用户信息列入等待列表。（4）退出预定，根据输入的时间，机器号撤销该事件的预定！（5）查询是否有等待信息，若有则提供最优解决方案（等待时间尽量短），若无则显示提示信息。87万年历查询程序。功能要求：（1）提供菜单方式选择（2）输入年份、月份、日期，计算得到的是这一天据今天有多少天，星期几；（3）输入公历的年月日，输出农历年月日。（4）输入农历节气，输出当年农历的年月日及公历年月日。可以假定只涉及年份是1940年到2040年。88汉诺塔移动输入盘子数（2个以上有效），移动速度，开始演示汉诺塔移动的步骤，要求：盘子，A，B，C柱需要自己绘制，初始时盘子在A柱上通过B柱最终移动到C柱上，显示出盘子在几个柱之间的移动过程。89运动会比赛计分系统要求：初始化输入：N-参赛学校总数，M-男子竞赛项目数，W-女子竞赛项目数各项目名次取法有如下几种：取前5名：第一名得分7分，第二名得分5，第三名得分3，第四名得分2，第五名得分1；取前3名：第一名得分5，第二名得分3，第三名得分2；功能要求：（1）系统以菜单方式工作（2）由程序提醒用户填写比赛结果，输入各项目获奖运动员信息。（3）所有信息记录完毕后，用户可以查询各个学校的比赛成绩（4）查看参赛学校信息和比赛项目信息等。90Skip List的实现及分析Skip List作为有序链表结构的一种扩展，如下图所示，其中a是普通的单链表；而b是在次基础上加上第二层（level 2）的额外指针，这些额外的指针指向间隔为2的下一个结点，skip list因此得名；类似的c是加上level 3后的skip list；d是加上level 4后的skip list。基本结构示意图Skip List上查找的基本思想是先从最高的Level层上查找，找到key所在的范围后，再从较低的层次继续重复查找操作，直到Level 1。插入操作的示意图Skip List上的删除操作只需直接删除元素即可（包括指针的修整）。构造并实现Skip List的ADT，同时实现双向Skip List的ADT及循环Skip List的ADT。 基本要求 ADT中应包括初始化、查找、插入、删除等基本操作。 分析各基本操作的时间复杂性。 针对一个实例实现Skip List的动态演示(图形演示)。91B-Trees的实现及分析B-Trees是一类满足特殊条件的M路查找树。首先说明M路查找树，M路查找树是二元查找树的一般化，其结构如下图所示的3路查找树：M路查找树中的任一结点至多存放M-1个数据，并至多拥有M棵子树；每个结点中的数据按升序排列V1 V2 . Vk (k = M-1)，每个数据Vi都存在一棵左子树和一棵右子树，如果左子树不空的话，该子树中所有结点的值都小于Vi,如果右子树不空的话，该子树中所有结点的值都大于Vi。3-路查找树的结构示意图B-Trees是满足如下两个条件的M路查找树： 所有叶结点的高度相同。 除根之外的所有结点都至少是半满的，即该结点包含M/2或更多的值。下图是一个B-树的实例。3-路B-树的结构示意图 基本要求 实现在B-树上的查找，并分析其时间复杂性。 实现B-树的ADT，包括其上的基本操作：结点的加入和删除。 要求B-树结构中的M=3或5，实现其中的一种即可。 实现基本操作的演示。92AVL Tree的实现及分析AVL(Adelson-Velskii and Landis)树是一株平衡的二元查找树。一株平衡的二元树就是指对其每一个结点，其左子树和右子树的高度之差不超过1。下图就是一个AVL树的实例。编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作：结点的加入和删除。BST和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。基本要求 编写AVL树判别程序，并判别一个二元查找树是否为AVL树。二元查找树用其先序遍历结果表示，如：5，2，1，3，7，8。 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为AVL树的操作。93汽车租借公司的管理(1) 问题描述设计数据结构及算法完成某个汽车租借公司日常工作的组织与管理。该管理系统的基本管理对象为汽车，每台汽车用一个license number进行唯一标识。每个汽车存在三种可能状态：可以租借（available for rent）已借（rented）修理中（in repair）其中在available队列中汽车应该依据汽车行驶过的路程进行排序，行驶路程最少的汽车排在最前面。在rented队列中的汽车应依据其预期返回时间进行排序，排在最前的应是预期最早返回的汽车。(2) 课程设计目的应用线性数据结构存储信息，并能够应用上面的基本操作实现事务管理。(3) 基本要求 用三个链表组织三种状态的汽车。 能够实现租借的日常事务：引入新车，租借，收费，修理等。 租借收费应根据汽车行驶的路程及借去的时间综合计算得出，路程收费标准如下： 1. 低于100Km收费20.00元 2. 100Km以外的路程枚Km收费0.15元 汽车根据行驶的路程定期进行维护。 还需实现辅助操作：汽车查询，打印全部信息，计算并打印收入、成本及收益。 管理系统应有完整地界面（最好是图形化界面）。(4) 实现提示主要集中在链表的基本操作上。94长整数的加减计算(1) 问题描述设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减等基本代数运算。(2) 课程设计目的能够应用线性数据结构解决实际问题。(3) 基本要求 长整数长度在一百位以上。 实现两长整数在同余代数下的加、减操作。即实现算法来求解a+b mod n, a-b mod n。 输入输出均在文件中。 分析算法的时空复杂性。(4) 实现提示需将长整数的加法转化为多个一般整数加法的组合。95迷宫的生成与路由(1) 问题描述设计算法生成一个NM(N行M列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。(2) 课程设计目的理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。(3) 基本要求 N和M是用户可配置的，缺省值为50和50。 迷宫的入口和出口分别在第0行和第N-1行上，随机选择。 生成的迷宫要求是连通的。 实现图形化界面(可用VC+，也可用C语言的图形库)。 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。(4) 实现提示多考虑栈上的运算。96应用堆实现一个优先队列(1) 问题描述优先队列priority queue是一种可以用于很多场合的数据结构，该结构支持如下几本操作：Insert (S, x) 将元素x插入集合SMinimum (S) 返回S中最小的关键字Extract Min (S) 删除S中的最小关键字可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的一部分。此处由于要用堆实现队列，所以堆结构的存储表示要求用数组。(2) 课程设计目的堆结构的应用，优先队列的构造。(3) 基本要求 给出优先队列的ADT描述，包括队列的逻辑结构及其上基本操作。 以堆结构为辅助结构实现优先队列的存储表示并实现其上的基本操作。 应用优先队列的ADT实现根据学生成绩对学生信息进行排序输出。 学生信息存放在文本文件中（格式自定，内容自行输入）。(4) 实现提示出队、入队需考虑优先性。97教学计划编制问题(1) 问题描述针对西北农林科技大学信息学院本科课程，依据其相互依赖关系制定课程安排计划，并要求各学期课程数目大致相同且搭配适当。(2) 课程设计目的掌握图上的基本算法，以及集合的划分。(3) 基本要求 求解上图的拓扑排序结果。 上述课程在4学期上完，要求每学期上课的门数大致一样。 每学期的课程应尽量搭配适当，即在每学期内同一系列的课程不要太多。(4) 实现提示在拓扑排序基础上作适当修改。98集合的等价划分(1) 问题描述构造集合结构的抽象数据型，并在此基础上进行集合的等价划分。(2) 课程设计目的掌握集合的表示方法，并设计等价划分算法。(3) 基本要求 选择合理的结构完成集合的表示(要求以ADT的形式给出)。 在进行等价划分前，等价关系需用户输入(从文件输入，格式自定)。 需要验证用户输入的关系是否为等