1、数据结课程设计数据结构课程设计任务书 学期：09-10-2 班级：软件08一、设计目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研
2、读数据结构课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题说明：课程设计题目主要分为两大类：一是基础类题，主要是验证性题，少数是简单的综合性题，侧重考查学生对数据结构课程中重要数据结构和算法的理解与掌握程度，相对较简单；本类题目选题要求：要求个人所选题目必须独立完成，不得合作；原则上不得参考别人的程序，若个人能力有限
3、必须参考，参考成分不得超过30%，其中参考部分自己必须能消化吸收，否则无效；为培养学生分析问题、解决问题的实际动手能力和团队协作能力，鼓励有能力的学生尽可能选作难度较高的题目或第二类题目，故仅选作第一类题目中一星和二星题目的学生，无论完成多少题目，原则上最高分不超出75分；仅选作第一类题目中三星和四星题目的学生，无论完成多少题目，原则上最高分不超出90分；选择其他第一类题目中组合类题目的学生无论完成多少题目，原则上最高分不超出80分；二是提高类题，主要是设计性题，侧重考查学生综合能力，包括营火利用所学知识（主要是数据结构和算法等相关知识）去分析问题、解决问题的实际动手能力以及团队协作精神和协调
4、能力；题目相对较难，多数题目无现成算法，考验学生的创新能力和综合素质。本类题目选题要求：每个题目的可以有三名同学组成一个三人小组共同协作完成（可以自由组队），三人分工负责程序编写、测试以及实验报告撰写工作。程序员、测试员、文档员的工作难度不同，其工作的分数分配也应不同，我们采用50:30:20的分配制度，原则上每人至少（必须）在三个题目中将三种角色分别成功体验一遍，才能及格分，每个队至少出色地完成6题（每位队员至少做2题）有可能得到满分100，建议每队做6题以上。一.基础类题目 选题说明：一个*的题代表15分，两个*的代表30分，三个*的题代表50分，四个*的题代表80分。根据实际选做题目的分
5、值和数量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，保障及格，力争多做。1、散列表的设计与实现（*）任务：设计散列表实现电话号码查找系统。要求： （1) 设每个记录有下列数据项：用户名、电话号码、地址； （2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； （3) 采用一定的方法解决冲突； （4) 查找并显示给定电话号码的记录； 选作内容： （1) 系统功能的完善； （2) 设计不同的散列函数，比较冲突率； （3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。2、 迷宫求解（*）任务：可以输入一个任意大小的迷宫数
6、据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；3、 文章编辑（*）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符
7、号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；4、 猴子选大王（*）任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：（注：分别顺序存储结构和链式存储实现）输入数据：输入m,n。 m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 5、线索二叉树（*）任务：1建立中序线索二叉树，并
8、且中序遍历； 2. 求中序线索二叉树上已知结点中序的前驱和后继； 6、 基数排序（*）任务：假设有n个待排序记录，记录Ri的关键字为Keyi, Keyi由d位十进制数字组成，即Keyi=Ki1 Ki2 Ki3 Kid ,试分别采用链式存储结构和顺序存储结构实现基数排序。提示：为提高基数排序效率，采用顺序储结构的方式可以仿造稀疏矩阵转置中的交换方法实现。7、 运动会分数统计（*）任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3
9、、2；哪些项目取前五名或前三名由学生自己设定。（m=20,n、提高题目： 【试题一】小李是计算机学院的教学秘书，每学期都要对每个班级的学生成绩分析统计，其中一项重要工作就是把学生的百分制成绩转换为五分制。在长期的工作中，他发现，采用传统的转换方法，效率较低，耗费他大量的时间和精力，所以他想改变他的工作方法，以提高工作效率。细心的他发现，一个班级中学生成绩分布有一定的规律：一般情况下，中等成绩者最多，占总人数的38%，其次是良好的占30%，优秀生占10%，及格生占16%，不及格率占10%。根据这一规律，他设计一个理想的转换方案。为了验证方案的高效性，他进行了多次对比测试，测试结果表明，他所设计的
10、转换方案是正确的，并且是最理想的。【标准输入】 第一行： N M /N为某个班级的人数（1=N=10000）, M表示测试次数（3=M=100） 第二行： X1, X2,Xi,Xn 表示N个学生的成绩,第一次测试第三行： X1, X2,Xi,Xn 表示N个学生的成绩,第二次测试第四行： X1, X2,Xi,Xn 表示N个学生的成绩,第三次测试.【标准输出】 每次测试结果输出一行，成绩转换的工作量。【约束条件】（1）1= N，L，Ai =1000 ( i=1, 2, ., N )（2）时间限制： 1000MS【 样 例 】 标准输入标准输出10 3 54 65 61 75 78 72 81 70
11、 92 85 51 60 71 72 73 82 88 93 83 932322【试题二】据不完全统计，受地震影响，大部分灾区通信陷入瘫痪，数千个基站因断电、传输中断等原因退出服务，目前总公司已紧急部署对受灾地区进行通信抢修。按照应急通信保障预案，必须尽快、付出代价最小，效率更高来全力恢复通信。由于大部分灾区都处于山区，有很多基站之间不能直接建立通信。现已知建立各基站之间直接通信的代价，问如何建立总代价最小的通信网，使得任意两个基站之间都能通信？【标准输入】 第1行： N M (N为基站数 M为能直接建立通信关系数 )接下有M行： I J P （每行有三个数。I J 为基站的编号P为基站I与基
12、站之间直接通信的代价）【标准输出】T （建立通信网的最小代价数）【约束条件】（1） 2 N 100 10 M 1000（2） 0 P 1000 P为正整数（3） 时间限制： 1000MS【 样 例 】标准输入标准输出5 71 2 1601 3 301 4 202 3 2003 4 503 5 805 4 70280【试题三】TOM设计了一件艺术品，该艺术品由N个构件堆叠而成，N个构件从高到低按层编号依次为1，2，,N。艺术品展出后，引起强烈的反响。Tom观察到，人们尤其对作品的高端部分评价甚多。狂热的Tom一激动，对组成该艺术品的N个构件重新组合，比如：把第6层到第12层的构建搬下来，想一想，
13、然后整体放到剩下构件的第7层下面；过一会儿，又把第2层到第9层的构件搬下来，整体放到剩下构件的第1层下面等等。于是，Tom在进行了连续若干次“搬来搬去”后，还是这N个构件又诞生了一件新的艺术品。 编程：请输出新的艺术品最高十层构件的编号。标准输出 第一行： N K 表示构件的总数和“搬来搬去”的总次数 第2K+1行： A B C 表示要搬动的构件（即从第A层到B层）整个放在第c层下面；如果C=0,则要搬动的构件将放到最高层。标准输出 由十行组成，分别为组成新艺术品的第一层到第十层构件的编号。约束条件（1） 10N20000 1K100（2） 1ABN 0CN-(B-A+1)样例标准输入标准输出
14、13 3 6 12 12 9 010 13 8 6789101112234【题目四】 最短的旅程描述在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。 Starhder 就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下
15、，旅游完上述的城市最短需要多少路程。输入第一行包含两个整数，上文中的n和k，以一个空格隔开。（2= n =50000，1 = k =n），下面的n- 1行每行描述一条路，第i + 1行包含3个整数ai，bi，di，相邻两个数用一个空格隔开（1= ai,bi = n，1= di = 1000），ai和bi是用道路直接相连的城市编号，di是这条道路的长度。第n + 1行包含一个整数j，是starhder要旅游的城市数（1= j = n - 1），接下来一行包含j个不同的整数m1，m2，mj，每两个相邻的整数用一个空格隔开，表示starhder想要去的城市。（1= mt=n，mt k）。输出输出只有
16、一行，包含一个整数：starhder旅游的最短路程。样例输入42121422233213样例输出5【题目五】纪念品发放事件描述 新学期到了，校学生会让乐乐负责迎新晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。 输入多组数据，每组数据共n+2行，第1行包括一个整数w(80=w=200)，为每组纪念品价格之和的上限。第2
17、行为一个整数n(1=n=30000)，表示购来的纪念品的总件数。第3n+2行每行包含一个正整数pi(5=pi=w)，表示所对应纪念品的价格。输入数据以0结束。输出每组数据输出一行，包含一个整数，即最少的分组数目。样例输入10099020203050607080900样例输出6【试题六】 Time Limit: 1000MSYou are given two integernumbers X and Y. Write a program to calculate X+Y and X-Y.InputThe first line of the input file contains a single
18、 integer N, the number of test cases. The following N lines each contains two integers-X and Y ( 0 X,Y =10100 ).OutptPrint the value of X+Y, X-Y on a separate line.Sample input and outputInout3555559 11111566670 5444489999999999 610000000005 9999999993800005555 996666000010766665555 -9166654445【试题七】
19、SortAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of the form A
20、B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 = n = 26. The objects to be s
21、orted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A B which will be given in this problem instance. 1 = m = 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character and a second uppercase letter. No letter will be outside the range of the first n letters of the
