当前位置：文档之家 › 数据结构课程设计参考题目

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

  • 格式：doc
  • 大小：45.00 KB
  • 文档页数：9

1. 运动会分数统计

【问题描述】

参加运动会的n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。

【基本要求】

可以输入各个项目的前三名或前五名的成绩；

能统计各学校总分，

可以按学校编号或名称、学校总分、男女团体总分排序输出；

可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。

数据存入文件并能随时查询

规定：

输入数据形式和范围：可以输入学校的名称，运动项目的名称

输出形式：有中文提示，各学校分数为整型。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

测试数据：

【测试数据】

要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。

例如，对于n=4，m=3，w =2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。

【实现提示】

可以假设n≤20，m≤30，w≤20，姓名长度不超过 20 个字符。每个项目结束时，将其 编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入运动员姓名、校名(和成 绩)。

2. 马踏棋盘

【问题描述】

设计一个国际象棋的马踏遍棋盘的演示程序。

【基本要求】

将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

3. 迷宫问题

【问题描述】

迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。

【基本要求】

1) 设计数据结构存储迷宫；

0

1 2 3 4 5 6

7 8 9

0 1 1

1 1 1 1 1 1 1 1

1 1 0 1 1 1 0 1 1 1 1

2 1 1 0 1 0 1 1 1 1 1

3 1 0 1 0 0 0 0 0 1 1

4 1 0 1 1 1 0 1 1 1 1

5 1 1 0 0 1 1 0 0 0 1

6 1 0 1 1 0 0 1 1 0 1

7 1 1 1 1 1 1 1 1 1 1 入口(1, 1)

出口(6, 8)

图2 迷宫示意图，其中1代表有障碍，0代表无障碍

前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下 2) 设计存储结构保存从入口到出口的通路；

3) 设计算法完成迷宫问题的求解；

【实现提示】

可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。

4. 航空客运订票系统

【问题描述】

航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。

【基本要求】

(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1，2或3)以及等候替补的客户名单(包括姓名、所需票量)；

(2)系统能实现的操作和功能如下：

①录入：可以录入航班情况，全部数据可以只放在内存中，最好存储在文件中；

②查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；

③承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；

④承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。

【测试数据】

自定。

【实现提示】

两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。

5. 哈夫曼编码

【问题描述】

设某编码系统共有n个字符，使用频率分别为{w1, w2, …, wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。

【基本要求】

(1) 设计数据结构；

(2) 设计编码算法；

(3) 分析时间复杂度和空间复杂度。

【实现提示】

利用Huffman编码树求得最佳的编码方案。

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。

weight

lchild rchild parent

图 哈夫曼树的结点结构 构造哈夫曼树的伪代码如下：

1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；

2. 数组huffTree的前n个元素的权值置给定权值w[n]；

3. 进行n-1次合并

3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；

3.2 将二叉树i1、i2合并为一棵新的二叉树k；

在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。

6. 校园导游咨询

【问题描述】

设计一个校园导游程序，为来访的客人提供各种信息查询服务。

【基本要求】

(1) 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。

(2)为来访客人提供图中任意景点相关信息的查询。

(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。

【测试数据】

自定。

【实现提示】

一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网。顶点和边均 含有相关信息。

7. 全国交通咨询模拟

【问题描述】

出于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。

【基本要求】

(1) 提供对城市信息进行编辑 ( 如 : 添加或删除 ) 的功能。

(2) 城市之间有两种交通工具、火车和飞机。提供对列车时刻表和飞机航班进行编辑( 增设或删除 ) 的功能。

(3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具。

(4) 旅途中耗费的总时间应该包括中转站的等候时间。

(5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达 , 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

【测试数据】

自定。

【实现提示】

(1) 对全国城市交通图和列车时刻表及飞机航班表的编辑 , 应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括:起始站的出发时间、终点站的到达时间 和票价 ; 列车时刻表则需根据交通图给出各个路段的详细信息；例如：基于教科书7.6节。

图 7.33 的交通图 , 对从北京到上海的火车 , 需给出北京至天津、天津至徐州及徐州至上海 各段的出发时间、到达时间及票价等信息。

(2 )以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，还应包 括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。

8. 图书管理系统

【问题描述】

设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编号、单价、作者、存在状态、借书人姓名、性别、学号等。

【基本要求】

1、新进图书基本信息的输入，图书基本信息保存在数据文件中。

2、图书基本信息的查询。

3、对撤消图书信息的删除。

4、为借书人办理注册。

5、办理借书手续（非注册会员不能借书）。

6、办理还书手续。

7、统计图书库存、已借出图书数量。

9. 通讯录管理

【问题描述】

编写一个简单的通讯录管理程序。通讯录记录有姓名、地址、电话号码、电子邮箱等4项。

【基本要求】

1）添加：增加一个人的记录到通讯录中；

2）显示：在屏幕上显示所以通讯录中的人员信息，应能分屏显示；

3）存储：将通讯录信息保存在一个文件中；

4）装入：即将文件中的信息读入程序；

5）查询：可根据姓名查找某人的相关信息，若找到显示其姓名、地址、电话号码、电子邮箱；

6）修改：可修改一个人的除姓名之外的其他信息；

【测试数据】

程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。

10． 单项选择题标准化考试系统

【问题描述】

合集下载

数据结构课程设计可选题目

数据结构课程设计可选题目

数据结构课程设计可选题目

一、课程设计的目的

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

二、数据结构课程设计可选题目

1. 运动会分数统计（限1 人完成）

任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）

功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校；5) 数据存入文件并能随时查询；6) 规定：①输入数据形式和范围：可以输入学校的名称，运动项目的名称；②输出形式：有中文提示，各学校分数为整形；③界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。④存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上）请在最后的上交资料中指明你用到的存储结构；⑤测试数据：要求使用a.全部合法数据；b.整体非法数据；c.局部非法数据进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。

2. 飞机订票系统

任务：通过此系统可以实现如下功能：⑴录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）⑵查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；⑶可以输入起飞抵达城市，查询飞机航班情况；⑷订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；⑸退票： 可退票，退票后修改相关数据文件；⑹客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。⑺修改航班信息：当航班信息改变可以修改航班数据文件。

数据结构课程设计-学生成绩管理系统

数据结构课程设计-学生成绩管理系统

广东学院

《数据结构课程设计》

题 目： 学生成绩管理系统

学 号：

姓 名：

年 级： 计算机科学与技术6班

学 院： 智能制造学院

专 业：

指导教师：

目录

一、问题描述与基本要求 ................................... 3

1.1问题描述 .......................................... 3

1.2基本要求 .......................................... 3

二、数据结构的设计 ....................................... 3

2.1数据结构的选择 ..................................... 3

2.2单链表的定义....................................... 3

2.3重要函数的定义及说明 ............................... 4

三、软件模块结构图 ....................... 错误!未定义书签。

3.1大体模块关系图 .................................... 13

3.2各模块具体分析 ..................... 错误!未定义书签。

四、程序流程图 .......................................... 15

五、源程序 .............................................. 17

《数据结构》课程设计题目1+2

《数据结构》课程设计题目1+2

《数据结构》课程设计题目1+2

2011级《数据结构》课程设计

【实验目的】：使学生全面深入理解数据结构知识，掌握应用技巧，提高应用与分析能力，并培养学生综合运用所学理论知识求解问题的能力和协作精神。

【实验原理】：针对相对复杂问题，综合数据结构、算法和相关数学知识，给出解决问题的方案，应用相关的数据结构和算法知识设计并编写代码，给出测试数据和测试方案，完成上机测试和运行结果分析。

【实验要求】：

1.第一、二题一人独立完成，第三题以小组为单位协作完成（每组3-4人）；

2.前三周内须完成第一题,第四和第五周内须完成第二题，后四周完成第三题；

3.检查程序前须提交设计报告（按提交报告的先后顺序检查程序）；

4.第一、二题每人提交一份设计报告, 第三题每个小组提交一份报告，该报告由组内每人

提交的一份设计报告装订而成，报告内必须明确描述每个人的分工；

5.检查第三题时小组成员都要参与讲解（每人侧重讲自己完成部分）；

6.每次上机必须出席，如不能到需事先提交辅导员签字的假条；

【实验题目】

题目一: 基本查找算法比较

1)对以下3种基本的查找算法的性能进行比较：顺序查找，二叉查找树，哈希。算法

包含两步：第一步：从文件中读取数据建查找表；第二步从文件中读取查找关键字 静态查找。

2)待查找记录的个数不小于n ( n<=1000000)，关键字key互不相同，取值范围0-109；

查询操作的次数为m(m=100000)，每次查询的关键字随机生成，取值范围0-109.

3)比较的指标为关键字的比较次数（包含建立查找表和查找操作）、内存空间和实际

运行时间。至少用5组不同的数据作比较，至少包含完全正序(n=10000)、完全逆

序(n=10000)及随机(n=10000、100000，1000000)情况。

4)为提高比较的可信度，待查找数据和查询关键字数据的生成及排序等预处理要设计

成一个独立功能，并将结果数据保留在data.in文件中，格式如下：第1行，用空

数据结构课程设计题目

数据结构课程设计题目

数据结构课程设计（2010年）

一、设计目的

1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。

2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4、训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。

二、设计内容与任务（2、3两题任选一题）

1、 利用栈，将十进制数转换成八进制的数

例：十进制转换成八进制：(66)10=(102)8

66/8=8 余 2

8/8=1 余 0

1/8=0 余 1

结果为余数的逆序:102

2、 到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事：

（1） 病人到达诊室时，将病例交给护士，排到等候队列中候诊。

（2） 护士从等候队列中取出下一个患者的病例，该患者进入诊室就诊。

在排队时按照“先到先服务”的原则。设计一个算法模拟病人等候就诊的过程。其中“病人到达”用命令A表示，“护士让下一位患者就诊”用命令N表示，“不再接受病人排队”就用命令Q表示。

3、 某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上船有如下规定：同类车先到先上船，客车先于货车上渡船，且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，就以货车代替，若无货车等待则允许客车都上船。设计一个算法模拟渡口管理。

4、 以7个权值：7，5，1，4，8，10，20为例，构造Huffman树。

5、 在二叉树中查找值为X的结点，试设计打印值为X的结点的所有祖先的算法，假设值为X的结点不多于1个。

6、学生成绩管理： 给出n 个学生的考试成绩表，每条信息由姓名与分数组成，试设计一个算法(1)按分数高低次序打印出每个学生在考试中获得的名次，分数相同的为同一名次；(2)按名次列出每个学生的姓名和分数。其中，学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。用冒泡排序或快速排序算法实现该问题，最后要对结果做简单分析。