数据结构课程设计题目(2023春季25题)

1/1数据结构课程设计题目(2023春季25题)数据结构课程设计题目

题目1：设计链表结构的相关函数库，以便在程序设计中调用。要求：（1）实现链表的各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

题目2：设计挨次表结构的相关函数库，以便在程序设计中调用。要求：（1）实现挨次表的各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

题目3：设计程序以实现任意两个高次多项式的加法和减法运算。要求：（1）所设计的数据结构应尽可能节约存储空间；（2）程序的运行时间尽可能少。

题目4：设计一个模拟计算机器程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。要求：运算前应先检查有关运算条件，并对错误产生报警。

题目5：设计二叉链表结构的相关函数库，以便在程序设计中调用。要求：（1）实现二叉树的各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

题目6：设计树结构的相关函数库，以便在程序设计中调用。要求：（1）包括树的存储结构及各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

题目7：设计程序以实现构造哈夫曼树的哈夫曼算法。要求：求解所构造的哈夫曼树的带全路径长度。

题目8：设计图结构的相关函数，以便在程序设计中调用。要求：（1）实现图的存储结构及各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

题目9：设计程序完成如下功能：对给定的图和起点，产生其全部的深度优先遍历序列。

题目10：设计程序完成如下功能：对给定的网和起点，实现求解最小生成树的Prim算法。

题目11：设计程序完成如下功能：对给定的网和起点，实现求解最小生成树的Kruskal算法。

题目12：设计程序完成如下功能：对给定的网和起点，用Prim算法的基本思想求解其全部的最小生成树。

题目13：设计程序完成如下功能：对给定的网和起点，用Kruskal算法的基本思想求解其全部的最小生成树。

题目14：选择合适的结构表示图，在此基础上实现拓扑排序算法。要求：对所设计的图结

构，供应必要的基本功能。

题目15：设计程序完成如下功能：对给定的AOV网，产生全部的拓扑序列。

题目16：选择合适的结构表示图，在此基础上实现求解最短路径的Dijkstra算法。要求：对所设计的图结构，供应必要的基本功能。

题目17：设计并实现一简洁通讯录管理系统。要求：实现通讯录的建立、通讯者的删除、查询、删除，以及通讯录的保存。

题目18：设计并实现一个交通询问系统，能让旅客询问从任一个城市顶点到另一个城市顶点之间的最短路径问题。要求：能够输出旅客所走的路线和所走路径（或所需花费或所需时间等）

题目19：设计并实现一个航班信息查询和检索系统。要求：对飞机航班信息进行排序和查找，可根据航班号、起点站、到达站、起飞时间和到达时间等信息进行查询。航班信息表的

其中航班号一项的格式为：前两个大写字母表示航空公司的名称，后4位为航班编号，例如：CA1544，CA表示航空公司的名称，1544为航班编号。（限选3-4人）

题目20：图书管理信息系统的设计与实现。图书管理一般包括：图书采编、图书编目、图书查询及图书流通（借、还书）等，请编程实现上述功能。详细设计要求：

（1）设计图书管理的存储结构，输入若干种书的记录。

（2）实现关于书号、书名、及出版社的图书查询；

（3）实现图书的借还子系统，包括建立读者文件、借还书文件、读者管理及图书借还等相关处理。

题目21．求解迷宫问题：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。设计要求如下：

(1)以链栈作为存储结构，编写一个求解迷宫的非递归程序，并将求得的通路以三元组（i,j,d）的形式输出，其中：i,j指示迷宫中的一个坐标，d表示走到下一坐标的方向；(2)编写递归形式的算法，求得迷宫中全部可能的通路；(3)以方阵形式输出迷宫及其通路。（选做）

[测试数据]

左上角（1，1）为入口，右下角（9，8）为出口。

[实现提示]

计算机解迷宫通常用的是“穷举求解”方法，即从入口动身，顺着某一个方向进行探究，若能走通，则连续往前进；否则沿着原路退回，换一个方向连续探究，直至出口位置，求得一条通路。假如全部可能的通路都探究到而未能到达出口，则所设定的迷宫没有通路。

可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理便利起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可商定有东、南、西、北四个方向可通。

题目22．哈夫曼编/译码器问题：利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。设计要求如下：

一个完整的系统应具有以下功能：

(1)I:初始化(Initialization)。从终端读入字符集大小n，及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。

(2)C:编码(Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。

[实现提示]

可以依据题目要求把程序划成3个模块，设计成菜单方式，每次执行一个模块后返回菜单。除了初始化过程外，在每次执行时都经过一次读取磁盘文件数据。这是为了假如在程序执行后始终没有进行初始化(I)过程，为了能使后面的操作顺当进行，可以通过读取旧的数据来进行工作。比如：假如程序的工作需要的字符集和权值数据是固定的，只要在安装程序时进行一次初始(I)化操作就可以了。再在次运行程序时，不管进行那项操作都可以把需要的数据读入到内存。

题目23．教学方案编制问题：高校的每个专业都要制定教学方案。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设课程都是确定的，而且课程在开设时间的支配必需满意先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学方案编制程序。设计要求如下：

(1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。

(2)允许用户指定下列两种编排策略之一：一是使同学在各学期中的学习负担尽量匀称；二是使课程尽可能地集中在前几个学期中。

(3)若依据给定的条件问题无解，则报告适当的信息；否则将教学方案输出到用户指定的文件中。方案的表格格式自行设计。

[测试数据]

学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分挨次为2，3，4，3，2，3，4，4，7，5，2，3。先修课程关系自己设定。

[实现提示]

可设学期总数不超过12，课程总数不超过100。假如输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程号与课程号之间的对应关系

题目24.运动会分数统计问题：参与运动会有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).可以按学校编号查询学校某个项目的状况；可以按项目编号查询取得前三或前五名的学校。

题目25.校内导游程序：用无向网表示