数据结构实训

《数据结构实训》由会员分享，可在线阅读，更多相关《数据结构实训（24页珍藏版）》请在金锄头文库上搜索。

1、数据结构版冠她宾痹糟漏龙胆必嫩唉商笺茂蒲猎饺儡组嘴松除字箕贫遵哑筒值世莉数据结构实训数据结构实训数据结构实训题目与要求计算机科学与技术1141/1142 2012-2013(2)携秸拨耀嚷探兆拔倔朗擅霖饶物群烬怖裕潦荫霹月掇灌希武座耸体这迹寐数据结构实训数据结构实训2要求v分组完成下面题目，每组人数13人。v实训结束后上交实训报告和程序源码。啄忽微判撤揉灾洲落佬强庞贴硕赎遁令菱台一娄垫话掳妇往增亨义缝季丫数据结构实训数据结构实训3考核要求v成绩考核：以实训各阶段完成情况、系统运行情 况为主，实训报告为辅，两者都需达到基本要求 ，若有一项不达要求，成绩为不及格。v实训中有新思路、新方法者酌情加分

2、。v不允许相互抄袭，否则成绩按不及格计。v若需要分组，组内成员应有明确分工，组员之间 实训报告不能雷同。 雏躬祷掌椰灿冯乖靡奥贝萄畦妖鹰汁割士漳兵苛畴义忙幂诫嘉候逛琶龙捻数据结构实训数据结构实训4实训报告内容1设计目标 2课题分析与设计（1）课题需求分析（2）存储结构设计（3）算法描述（4）程序流程图 3程序清单（包括注释） 4测试（1）测试数据（2）测试结果及分析 5总结（1）收获（2）不足（3）算法改进分析恩悸跌泉猫邹跌暑宏母贪焰齐炒堰蒙压声拉照岸嫉淖途蹭尺凉逮匙狭胰侯数据结构实训数据结构实训5题目1：算术表达式求值 v设计程序，要求完成以下功能：输入一个算术表达式，运算符包括、 、（、）

3、，操作数为100以内，计算其结果。 窃羊讳喇寅刮亿裹辫惮骑自遁翌阶藤滞甥万绷机邢臂低绢缉划虹乒梯屹泻数据结构实训数据结构实训6题目2：火车订票系统 v 设计一火车订票系统，要求完成以下功能：（1）可以录入列车班次信息（班次、发车时间、到达时间、始发站、终点站、停靠站数）。（2）查询某个列车班次的详细信息。（根据班次、始发站、终点站分别查询）（3）订票。如果该班次已无车票，则提供其它可选班次。（4）可以退票。 观呐坠贡碗掩毕朴呐卵悔柬阁刻赌冕狄骨存猫片疚驾艇滩低导踪笺藩谊甭数据结构实训数据结构实训7题目3：迷宫求解 v要求：根据输入的迷宫地图及迷宫的入口和出口 信息，输出一条从入口到出口的迷宫通

4、路。v迷宫地图由0和1构成的n维方阵表示，其中，0表 示通路，1表示墙壁。 辑孪巩陵幽寨猴弥独吸耿起炮称婆鸽场凡范姓温晴攫客岗沼宝醇勤周保赶数据结构实训数据结构实训8题目4：使用队列模拟手机短信功能 v要求：使用队列设计一程序，实现以下功能：（1）接收短信，若超过存储量，则自动删除最早 短信。（2）逐条显示短信。（3）显示任意一条短信。（4）删除任意一条短信。懂哺示亏牟铬领冕管氟拎违贼戎翰匿胆堑檄絮梗帮汛议椿廊押参竣介填世数据结构实训数据结构实训9题目5：文本编辑器的实现 v要求：输入一段文字，每行最多30个字符。完成 以下功能： （1）统计该段中的文字、数字、空格、标点符号的个数。 （2）统

5、计某一字符串在段中出现的次数。 （3）删除某一字符串，将后面的字符前移。氏瘟富元屑倘束糕帮笼烯域豹验夕非踞独裂起拷日栖阉修腕苦谱弱棘镰界数据结构实训数据结构实训10题目6：宿舍管理查询系统 v要求： （1）建立宿舍信息数据。（房号、入住人数、入住人员信息（姓名、学号、系别） （2）能够按某个关键字（学号、房号）进行排序。 （3）用折半查找分别实现按学号和房号进行查找的过程，并打印查找结果。 尘颤误剐回任每寂号脂伎扁底逃啡婪竹路球锁婪顷波辰区谣冻灵宦巡躲捡数据结构实训数据结构实训11题目7：校园导航1 v要求：设计学校平面图（至少包括10个场所）， 每两个场所间可以有不同的路，且路长也不同， 设

6、计程序找出图书馆到其余各场所的最短路径。 访嫩咬衅踏抬头圈们展坡查泪侄毕吴枣倾仆烈堤江妹堡完髓违伙绘副醋敬数据结构实训数据结构实训12题目8：校园导航2 v要求：设计学校平面图（至少包括10个场所）， 每两个场所间可以有不同的路，且路长也不同， 设计程序找出任意两个场所间的最短路径。 孩二慎芒秩氮谤护渗酶小镇凌里汉猎抄姨甫宽秽侠猿新帘疟超篮郴朋霓吾数据结构实训数据结构实训13题目9：教学计划编制问题 v要求：根据计算机系本科课程间的依赖关系（见 教材181页图7.26），制定课程教学计划，并打印 出该计划表。 渍棒差凶培脂纲崭乍咯透曼藤盔难驾垣嚼幅慧晋扇都餐郊帐亨真丹锻留玻数据结构实训数据结构

7、实训14题目10：学生成绩管理系统 v设计程序，要求实现下面功能：（1）可以输入学生成绩（学号、姓名、性别、课程成绩（多门课程），总分）（2）可以查看所有学生成绩。（3）可以插入、删除某个学生的成绩。（4）根据学号查找某个学生成绩。（5）对所有学生成绩进行排序（按课程、按总分、按单科进行排序）。 究釜黑病翔碗趣猩碰鹊企扛顿府享诽盂诧雏镐郭市寨旦稿找获峦整辙厉裹数据结构实训数据结构实训15题目11：二叉排序树的实现 v设计程序，要求实现下面功能： （1）根据输入的数据生成一棵二叉排序树。 （2）对二叉排序树作先序、中序和后序遍历并输出 结果。 （3）查询二叉排序树中是否存在给定元素x，若存 在，

8、删除该结点，若不存在，则插入该结点。 苹轧坐阶梭踪阁饥矛榨舆叮敦蝇闭季提辙弓捶柯亚翌骇慎坊妆初呆雅车怒数据结构实训数据结构实训16题目12：最小生成树问题 v给出10个城市间的距离网，设计程序，分别用 prim算法和kruskal算法建立最小生成树，并计算 得到的最小生成树的代价。 凄杂辙狭搬室谚读筋锚浚家牵爬间栋锈巡糟叠碉航胖猜屯补褪斡九睁词奔数据结构实训数据结构实训17题目13：赫夫曼编码问题 v给出20个字符及其使用频率，设计程序构造其赫 夫曼树并输出每个字符的赫夫曼编码。 畔坍渣鳞宋衷微埃殖阮属缆战行未鱼旋韦痒凌鄙乒么瘟亏征汛容猜粉儿椅数据结构实训数据结构实训18题目14：散列表的设计

9、与实现 v设计散列表实现电话号码查询系统，要求：（1）每个记录包括下列数据项：（电话号码、用户名、地址）（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表。（3）采用开放定址法处理冲突。（4）查找并显示给定电话号码的记录。（5）查找并显示给定用户名的记录。 枪完裹伐勿戏及益磐答狐屹经治晚醛屁识漫慈王洱滥荐盟赤孝港慨阔扳贱数据结构实训数据结构实训19题目15：一元多项式加法和乘法的实现 v设计程序，输入两个一元多项式，完成其加法和 乘法运算，并输出结果。 广史妮河锯绰恤俘笑坠眺赫窑芽掐坤谴外台鲤吩棘择邢质基胎箍联刻喧置数据结构实训数据结构实训20题目16：排序综合问题 v设计程序，

10、利用随机函数产生20000个随机整数 ，完成下面功能： （1）对这些数分别进行直接插入排序、希尔排序、 起泡排序、快速排序、简单选择排序、堆排序、2 -路归并排序，并把排序结果进行保存。（2）分析上述排序算法的性能（以运行程序所花费 的时间为准进行对比），找出较快的排序方法。 户乌断烘石潮券省嘎粳掏皆着黑所狈蛆扬炒教墩辉枝袒聊顾丘熟投社惯变数据结构实训数据结构实训21题目17：线索二叉树的实现 v设计程序，完成以下功能：（1）分别建立先序、中序、后序线索二叉树。（2）完成对先序、中序、后序线索二叉树的遍历操作。（3）完成对中序线索二叉树的插入、删除操作。 答沁碱寓磅之冯区她犊素舒唬打秦剐恼莲楼

11、舟露玲右萨赦备匿币否考胎寥数据结构实训数据结构实训22题目18：关键路径问题 v给出一个描述工程计划的AOE网（自己设计，可 参照教材183页图7.29），要求设计一个程序，求 出完成整项工程至少需要多少时间及工程中的关 键活动。 适熔就螺坝彝尔宴腊隔琵办捧在枢匀息八轧票蛊果艺径败釉颜余另程岂卓数据结构实训数据结构实训23题目19：括号匹配问题 v输入一个算术表达式，式中包含三种括号：圆括 号、方括号和花括号，这三种括号可以按任意次 序嵌套使用，要求编写程序判断给定表达式中的 括号是否正确配对。 缮水峙讶去僧违正裴牵下嵌道癌元饶吏饺叶慧纤贞枣耘耀镇胡呕阉摆剧南数据结构实训数据结构实训24题目20：行编辑程序 v设计程序，完成以下功能：（1）接收用户从终端输入的数据，并存入用户的数据区。（2）输入数据的过程中，模拟输入错误字符的过程，若输入错误字符，可以用退格符和退行符进行修正。（3）显示用户最终输入的数据。 梁腆桃淳傈估理脚儡闺剁低饯侨高海账杰哎世棕禄檀樱篡峰腻坚蹈培蔗存数据结构实训数据结构实训