数据结构课程设计参考题目.doc

《数据结构课程设计参考题目.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计参考题目.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1. 运动会分数统计【问题描述】参加运动会的n个学校编号为1n。比赛分成m个男子项目和w个女子项目，项目编号分别为1m和m+1m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。【基本要求】可以输入各个项目的前三名或前五名的成绩；能统计各学校总分，可以按学校编号或名称、学校总分、男女团体总分排序输出；可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。数据存入文件并能随时查询 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文

2、提示，各学校分数为整型。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。测试数据：【测试数据】要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。例如，对于n=4，m=3，w =2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。【实现提示】可以假设n20，m30，w20，姓名长度不超过 20 个字符。每个项目结束时，将其 编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入运动员姓名、校名(和成 绩)

3、。2. 马踏棋盘【问题描述】 设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】将马随机放在国际象棋的88棋盘Board88的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个88的方阵，输出之。3. 迷宫问题【问题描述】迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边

4、矩形表示迷宫，1代表有障碍，0代表无障碍。012345678901111111111入口(1, 1)出口(6, 8) 图2 迷宫示意图，其中1代表有障碍，0代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下11011101111211010111113101000001141011101111511001100016101100110171111111111【基本要求】1) 设计数据结构存储迷宫；2) 设计存储结构保存从入口到出口的通路；3) 设计算法完成迷宫问题的求解；【实现提示】可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按

5、某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。4. 航空客运订票系统【问题描述】航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名

6、单(包括姓名、订票量、舱位等级1，2或3)以及等候替补的客户名单(包括姓名、所需票量)；(2)系统能实现的操作和功能如下：录入：可以录入航班情况，全部数据可以只放在内存中，最好存储在文件中；查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一

7、的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。【测试数据】自定。【实现提示】两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。5. 哈夫曼编码【问题描述】设某编码系统共有n个字符，

8、使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。【基本要求】(1) 设计数据结构；(2) 设计编码算法；(3) 分析时间复杂度和空间复杂度。【实现提示】利用Huffman编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。weight lchild rchild parent 图 哈夫曼树的结点结构 构造哈夫曼树的伪代

9、码如下：1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；2. 数组huffTree的前n个元素的权值置给定权值wn；3. 进行n-1次合并3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2； 3.2 将二叉树i1、i2合并为一棵新的二叉树k；在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。6. 校园导游咨询【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1) 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代

10、号、简介等信息;以边表示路径,存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。【测试数据】自定。【实现提示】一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网。顶点和边均 含有相关信息。7. 全国交通咨询模拟【问题描述】出于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。【基本要求】(1) 提供对城

11、市信息进行编辑 ( 如 : 添加或删除 ) 的功能。(2) 城市之间有两种交通工具、火车和飞机。提供对列车时刻表和飞机航班进行编辑( 增设或删除 ) 的功能。(3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具。(4) 旅途中耗费的总时间应该包括中转站的等候时间。(5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达 , 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】自定。【实现提示】(1) 对全国城市交通图和列车时刻表及飞机航班表的编辑 , 应

12、该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括:起始站的出发时间、终点站的到达时间 和票价 ; 列车时刻表则需根据交通图给出各个路段的详细信息；例如：基于教科书7.6节。图 7.33 的交通图 , 对从北京到上海的火车 , 需给出北京至天津、天津至徐州及徐州至上海 各段的出发时间、到达时间及票价等信息。(2 )以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，还应包 括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。8. 图书管理系统【问题描述】设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编号、单价、作者、

13、存在状态、借书人姓名、性别、学号等。【基本要求】1、新进图书基本信息的输入，图书基本信息保存在数据文件中。2、图书基本信息的查询。3、对撤消图书信息的删除。4、为借书人办理注册。5、办理借书手续（非注册会员不能借书）。6、办理还书手续。7、统计图书库存、已借出图书数量。9. 通讯录管理【问题描述】编写一个简单的通讯录管理程序。通讯录记录有姓名、地址、电话号码、电子邮箱等4项。【基本要求】1）添加：增加一个人的记录到通讯录中；2）显示：在屏幕上显示所以通讯录中的人员信息，应能分屏显示；3）存储：将通讯录信息保存在一个文件中；4）装入：即将文件中的信息读入程序；5）查询：可根据姓名查找某人的相关信

14、息，若找到显示其姓名、地址、电话号码、电子邮箱；6）修改：可修改一个人的除姓名之外的其他信息；【测试数据】程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。10 单项选择题标准化考试系统【问题描述】设计一单项选择题标准化考试系统，实现考试的标准化管理。【基本要求】1）用文件保存试题库。（每个试题包括题干、4个备选答案、标准答案）2）试题录入：可随时增加试题到试题库中3）试题抽取：每次从试题库中可以随机抽出N道题（N由键盘输入）4）答题：用户可实现输入自己的答案5）自动判卷：系统可根据用户答案与标准答案的对比实现判卷并给出成绩。11. 电话号码查询系统【问题描述】人们在日常生活

15、中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。【基本要求】(1)使用文件保存电话号码信息；(2)设计数据结构存储电话号码信息；(3) 提供查询功能：根据姓名实现快速查询；(4) 提供其他维护功能：例如插入、删除、修改等；(5) 按电话号码进行排序。【测试数据】使用实际的电话号码，并不小于20个。【实现提示】由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，

16、要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据： const int max=20; struct TeleNumber string name; /姓名 string phoneNumber; /固定电话号码 string mobileNumber; /移动电话号码 string email; /电子邮箱 Telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉排序树是

17、否平衡，如何使之达到平衡。12. 销售管理系统【问题描述】某公司有四个销售员（编号：1-4），负责销售五种产品（编号：1-5）。每个销售员都将当天出售的每种产品各写一张便条交上来。每张便条包含内容：销售员的代号、产品的代号、这种产品的当天的销售额每位销售员每天可能上缴0-5张便条。假设，收集到了上个月的所有便条，编写一个处理系统，读取上个月的销售情况（自己设定），进行如下处理。【基本要求】1）计算上个月每个人每种产品的销售额。2）按销售额对销售员进行排序，输出排序结果（销售员代号）3）统计每种产品的总销售额，对这些产品按从高到底的顺序，输出排序结果（需输出产品的代号和销售额）4）每张便条的信息存储在数据文件中。