数据结构综合实验任务书-总

数据结构综合实验任务书

本次课程设计安排在第19周，教师提供了26道选题，按照题目的难易程序度分为一类、二类及三类，一类选题9个，难度稍高，二类选题5个，难度中等，三类选题12个，难度较低。根据自身情况选题，必须保证自己完成。自选题必须事先由教师看过并同意才可以做。选题原则上一人一组形式进行。

课程设计按照软件工程的步骤进行，先写出需求分析，再进行概要设计和详细。基本要求是给出题中所涉及的数据的逻辑结构、存储结构、算法核心设计流程、输入输出、源程序、测试数据及结果，并在总结部分给出设计及实现过程中出现的问题及解决思路，探讨算法的改进方法。系统实现在Visual C++控制台环境下实现，要求有简单界面的设计，课程设计最后以设计报告及软件形式提交，设计报告按照指导书的要求编写。

课程设计从学习态度、程序运行及答辩情况、文档写作情况分项打分，学习态度包括考勤及投入情况，程序运行考查编码的独立完成情况、程序的执行情况及工作量大小，文档的写作包括需求分析文档的写作，概要设计和详细设计情况以及数据结构的定义情况等等。

课程设计第一天，必须写出需求分析和概要设计。

课程设计任务书

一类题（9个）： NO. 1

１、题目：工程求解 ２、设计内容及要求： 内容：一个工程上的关键活动直接影响着整个工程的进展情况，要求实现关键路径上问

题的求解。 要求：

（1） 画出AOE网，以边表示子工程，顶点表示子工程的开始和结束，边上权值表示子工

程完成需要的时间，整个工程一个开始点，一个结束点。在计算机上以邻接表存储该AOE网。

（2） 输出工期和影响工程进展的关键活动。

编程实现基本要求。

NO. 2

１、题目：哈夫曼编码/译码器的设计与实现 ２、设计内容及要求： 内容：信息在通讯线路中是以编码形式进行传输的，在接收端采取一种译码的机制将信

息“译”出来。 要求：

（1） 对下表所示字符及频度，建立哈夫曼树； （2） 输出每个字符的编码；

（3） 利用哈夫曼树，对输入的报文进行编码，并将结果显示出来； （4） 利用哈夫曼树，对输入的译文进行译码。

NO. 3

１、题目：教学计划编制问题 ２、设计内容及要求： 内容：大学的每个专业都要制定教学计划，课程在开设时间的安排上必须满足先修关系，

每门课程恰好开设一个学期，每门课都有对应学分，每个学期的学分总上限是一致的。按照下表所示课程的先修关系，给图中的课程按7学期排课。 要求：

（1） 在纸上表示出课程之间优先关系的有向图，并用邻接表存储图； （2） 给出课程的线性序列；

（3） 设定每个学期的总学分上限，试排定一种课表。

NO. 4

１、题目：煤气管道铺设 ２、设计内容及要求：

内容：若在n个城市之间铺设煤气管道，只需要架设n-1条线路即可。如何以最低的经

济代价铺设煤气管道。 要求：

(1)在纸上模拟设计n个城市的网络平面图，城市数不少于10个，相通的城市数不少于2(n-1)，顶点表示各城市，边表示城市间的距离。在计算机中表示该图； (2)编写算法，求解最小代价煤气管道网络； (3)输出该煤气管道网络中各边及其权值。 选择一种数据结构并编程实现基本要求。

NO. 5

１、题目：通信网络建设 ２、设计内容及要求：

内容：若在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经

济代价建设这个通信网。 要求：

(1)在纸上模拟设计n个城市的网络平面图，城市数不少于10个，相通的城市数不少于2(n-1)，顶点表示各城市，边表示城市间的距离。在计算机中表示该图； (2)编写算法，求解最小代价通信网络； (3)输出该通信网络中各边及其权值。 选择一种数据结构并编程实现基本要求。

NO. 6

１、题目：校园导游咨询1 ２、设计内容及要求：

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

(1)模拟设计学校的平面图，景点不少于10个，顶点表示校园内各景点，有关景点的信息包括名称、代号、简介等信息，边表示路径，存放路径长度。在计算机中表示该图； (2)为来访客人提供图中任意景点相关信息的查询；

(3)为来访客人提供从某个起点到达任意景点的最短路径查询。 选择一种数据结构模拟此过程，编程实现基本要求。

１、题目：航班订票系统 ２、设计内容及要求：

内容： 航班客运订票业务活动包括：查询航线、客票预订和办理退票。试设计一个航

班订票系统，实现订票业务。 要求：

（1）录入，录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） （2）查询，查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；

（3）订票，可以订票，如果该航班有票，则输出座位号，如已经无票，则登记排队等候；已订票客户资料有姓名，证件号，订票数量及航班情况，订单要有编号，客户信息存储在链表中，并按姓名有序排列；未订上票客户信息放在队列中。 （4）退票：根据客户提供的情况（日期、航天班），办理退票手续，退票后查询该航班是否有人排队等候，按先登记先服务原则给等候者补票。 编写算法，并编程实现基本要求。

NO. 8

１、题目：算术表达式求值 ２、设计内容及要求：

内容：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。选取教科书

表3.1中给出的算符优先关系的一部分，实现限定范围的算术四则混合运算表达式的求值

要求：选择一种数据结构模拟此过程，编写通用算法，采用C语言编程实现设计题目

NO.9

１、题目：停车场管理 ２、设计内容及要求：

内容：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出，汽

车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车才可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车按它停留的时间长短交费。试为停车场编制按以上要求进行管理的模拟程序。 要求：

(1) 以栈模拟停车场，以队列模拟停车场外便道，按照从终端读入的输入数据序列进行

模拟管理。栈以顺序结构实现，队列以链表结构实现。

（2） 给出数据的逻辑结构、存储结构、 基本算法（使用程序流程图）、输入输出、源

程序、测试数据和结果、算法的时间复杂度；

（3） 探讨算法的改进方法；

在Visual C++控制台环境下实现软件，实现基本要求。

二类题：（5个）

１、题目：哈希表的设计与实现（1） ２、设计内容及要求：

内容：假设人名为汉语拼音，针对班级的“人名”设计一个哈希表，待输入人名为30

个，取平均查找长度不超过2。 要求：

（1） 采取除留余数法构造哈希表；

（2） 采用链地址法处理冲突，输出哈希表结果； （3） 考查平均查找长度。

编写算法，并编程实现基本要求。

NO.11

１、题目：哈希表的设计与实现（2） ２、设计内容及要求：

内容：假设人名为汉语拼音，针对班级的“人名”设计一个哈希表，待输入人名为20

个，取平均查找长度不超过2。 要求：

（4） 采取除留余数法构造哈希表；

（5） 采用线性探测再散列方法解决冲突，输出哈希表结果； （6） 考查平均查找长度。

编写算法，并编程实现基本要求。

NO. 12

１、题目：校园导游咨询2 ２、设计内容及要求：

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

(1)模拟设计学校的平面图，景点不少于10个，顶点表示校园内各景点，有关景点的信息包括名称、代号、简介等信息，边表示路径，存放路径长度。在计算机中表示该图； (2)为来访客人提供图中任意景点相关信息的查询；

(3)为来访客人提供从某个起点到达任意景点的路径查询。 选择一种数据结构模拟此过程，编程实现基本要求。

NO. 13

１、题目：工程管理 ２、设计内容及要求： 内容：一个工程上的关键活动直接影响着整个工程的进展情况，要求实现关键路径上问

题的求解。 要求：

（3） 画出AOE网，以边表示子工程，顶点表示子工程的开始和结束，边上权值表示子工

程完成需要的时间，整个工程一个开始点，一个结束点。在计算机上以邻接矩阵存储该AOE网。

（4） 能够查询任一子工程的最早开始时间和最迟开始时间；

编程实现基本要求。

NO. 14

１、题目：教学计划编制问题 ２、设计内容及要求： 内容：大学的每个专业都要制定教学计划，课程在开设时间的安排上必须满足先修关系，

每门课程恰好开设一个学期，每门课都有对应学分，每个学期的学分总上限是一致的。按照下表所示课程的先修关系，给图中的课程按7学期排课。 要求：

（4） 在纸上表示出课程之间优先关系的有向图，用矩阵存储图； （5） 可以查询任一门课程的先修课程； （6） 可以查询任一门课程的后继课程。

三类题：（12个） NO. 15

１、题目：简单的安全审计系统

２、设计内容及要求：

内容：安全审计系统通过日志收集用户使用信息，并且利用预设的告警规则向管理员发出告警。

要求：

日志文件中每条记录的格式如下，假设为用户名、用户命令和命令注释： 登录时间 用户名 用户命令 命令注释 20100615 user1 ls *.txt 列出所有的txt文件 20100615 user2 rmdir test 删除test目录 20100615 user1 more readme.txt 打印readme.txt文件内容 20100615 user1 cp a1.doc a2.doc 复制文件a1.doc为a2.doc 20100616 user2 delete *.doc 删除所有的doc文件

(1) 构造日志文件，并在内存中用动态链表存放每个用户的信息； (2) 查询输出某个用户使用的所有命令；

(3) 假设rmdir命令、cp命令为敏感命令，分别输出使用过这两个命令的所有用户； (4)查找某个时间段登录的所有用户。 编写算法并编码实现基本要求。

NO. 16

１、题目：简单的网络计费系统 ２、设计内容及要求：

内容：网络服务器对每个登录的用户都要记载下他登录的信息，并且放在日志文件中，以便计算他使用网络的时间。 要求：

假设日志文件中每条记录的格式如下，假设以秒计上线时间和离线时间：

用户名 上线时间 离线时间 user1 10051 10622 user2 20001 20200 user3 30111 30333 user1 45000 45789

(1)构造日志文件，并在内存中用动态链表存放每个登录的信息； (2)查询输出某个用户上网情况（什么时间上线，什么时间离线）； (3)计算每个用户使用网络的总时间。 选择一种数据结构并编程实现基本要求。

NO. 17

１、题目：选择类排序算法实现和比较 ２、设计内容及要求：

内容：实现简单选择排序、堆排序算法，并比较两种算法的比较次数和移动次数。 要求：

（1） 输入不少于10个元素的无序、正序、降序三组序列；

（2） 排序算法进行排序，输出每组元素序列每种算法的比较次数和移动次数。

（3） 对结果进行简单的分析。

编写算法，编码实现基本要求，并经过比较给出结论，

NO. 18

１、题目：交换类排序算法实现和比较 ２、设计内容及要求：

内容：实现起泡排序、快速排序算法，并比较两种算法的比较次数和移动次数。 要求：

（4） 输入不少于10个元素的无序、正序、降序三组序列；

（5） 排序算法进行排序，输出每组元素序列每种算法的比较次数和移动次数。 （6） 对结果进行简单的分析。

编写算法，编码实现基本要求，并经过比较给出结论，

NO. 19

１、题目：归并类排序算法实现和比较 ２、设计内容及要求：

内容：实现两路归并排序和三路归并排序算法，并比较各种算法的比较次数和移动次数。 要求：

（7） 输入不少于10个元素的无序、正序、降序三组序列；

（8） 排序算法进行排序，输出每组元素序列每种算法的比较次数和移动次数。 （9） 对结果进行简单的分析。

编写算法，编码实现基本要求，并经过比较给出结论，

NO. 20

１、题目：插入类排序算法实现和比较 ２、设计内容及要求：

内容：实现直接插入排序、希尔排序算法、，并比较两种算法的比较次数和移动次数。 要求：

（10） 输入不少于10个元素的无序、正序、降序三组序列；

（11） 用排序算法进行排序，输出每组元素序列每种算法的比较次数和移动次数。 （12） 对结果进行简单的分析。

编写算法，编码实现基本要求，并经过比较给出结论，

NO. 21

１、题目：设计一个一元稀疏多项式的简单计算器 ２、设计内容及要求：

内容：一元稀疏多项式的相加减 要求：

（1） 输入多项式，用带头结点的单链表存放该多项式；

（2） 输出多项式，输出形式为：n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分

别是第i项的系数和指数，按指数降序排列；

（3） 实现多项式的相加； （4） 实现多项式的相减。 编写算法，编程实现基本要求。

NO. 22

１、题目：词汇统计器 ２、设计内容及要求：

内容：统计任意的文本文件中指定的一组词汇出现的次数及位置。文本文件中存放的可以为英文文章。

NO. 23

１、题目：广度优先搜索（邻接矩阵存放） ２、设计内容及要求：

内容：图中结点数不少于10个，每个结点用一个编号表示，通过输入图的全部边输入一个图，以用户给定的点为起始点，对图进行广度优先搜索，输出结点的访问序列和相应的边集。

NO. 24

１、题目：广度优先搜索（邻接表存放） ２、设计内容及要求：

内容：图中结点数不少于10个，每个结点用一个编号表示，通过输入图的全部边输入一个图，以用户给定的点为起始点，对图进行广度优先搜索，输出结点的访问序列和相应的边集。

NO. 25

１、题目：深度优先搜索（邻接矩阵存放） ２、设计内容及要求：

内容：图中结点数不少于10个，每个结点用一个编号表示，通过输入图的全部边输入一个图，以用户给定的点为起始点，对图进行深度优先搜索，输出结点的访问序列和相应的边集。

NO. 26

１、题目：深度优先搜索（邻接表存放） ２、设计内容及要求：

内容：图中结点数不少于10个，每个结点用一个编号表示，通过输入图的全部边输入一个图，以用户给定的点为起始点，对图进行深度优先搜索，输出结点的访问序列和相应的边集。

本文来源：https://www.bwwdw.com/article/xure.html