2023《数据结构与算法》上机实验题目.pdfVIP

《数据结构与算法》课程实验要求与指导

一、课程简介

本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应

的基本算法。②各种查找算法③典型内部排序算法。

二、实验的作用、地位和目的

数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际

问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水

准的应用程序的能力。

三、实验方式与要求

本课程实验采用线上线下、课内课外相结合的方式开展。课内实验学时为24学时，主要分布

在线性表、栈与队列、树、图、查找与排序部分，实验采用线上线下同步方式，可利用课外时间在

线上CourseGrading平台进行。课内实验的准备、设计等也要求学生在课下完成。具体实验方式：

①教师提前1-2周布置具体实验任务，要求学生在课下完成问题分析、算法设计。

②实验时，每位学生使用一台微机，独立调试，完成程序。实验过程中教师进行答疑指导，可

以要求学生回答相关的问题。

③程序调试好后，上传CG平台进行自动评判。

④学生记录程序的输入数据、运行结果及源程序，进行实验分析，在一周内完成实验报告。教

师评阅后就问题进行说明和反馈。

四、考核方式与实验报告要求

实验成绩由指导教师根据学生的实验过程表现、CG平台程序完成情况、实验报告质量、创新

与特色等方面给分等方面给分。

学生在实验后的一周内提交实验报告。实验报告按照附件中实验报告模版书写。实验报告中应

包括如下内容：

实验内容按任课教师下达的实验任务填写（具体实验题目和要求）；

实验过程与实验结果应包括如下主要内容：

数据结构定义

算法设计思路简介

算法描述：可以用自然语言、伪代码或流程图等方式

算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办

法等

算法时间复杂度分析

源程序清单与实验结果或其它说明可打印，并装订在实验报告之后。

实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分

五、实验的软硬件环境

硬件环境：PⅡ以上微型计算机

软件环境：Windows98/2000,VC++6.0或turboC

六、实验内容安排

实验一线性结构应用

实验时间：2023年9月25日5-6节,地点：7-220，9月28日1-2节，地点：7-220，

10月9日5-6节，地点：7-220；线上CourseGrading平台

实验目的：理解线性表、栈和队列的逻辑特点；掌握顺序表、链表存储结构，以及线性表、栈和队

列的基本操作，并能够在实际问题背景下灵活运用线性表、栈或队列特性，综合运用程序设计、算

法分析等知识解决实际问题。

具体实验题目：每位同学从下面题目中至少选择4题实现：其中第1,5题为必做题，2,3,4选一题，

6,7选一题，8,9为选做题，具体实验要求以CG平台发布为准。

1．单链表基本操作练习

1）问题描述：已知单链表L（带头节点）是一个递增有序表，试编写算法，删除表中值大

于min且小于max的节点（若表中有这样的节点），同时释放被删节点的空间。

2）实验要求：min和max是两个给定参数。

3）分析算法时间复杂度

2.约瑟夫环问题

1）问题描述：有编号为1,2…n的n个人按顺时针方向围坐一圈，每人持有一个正整数

密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加

报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下

去，直到所有人都出列。试设计算法，输出出列者的序列。

2）要求:采用顺序和链式两种存储结构实现

3）分析算法时间复杂度

3.一元稀疏多项式简单的计算器

1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器

2）要求:（1）采用单链表存储结构一元稀疏多项式

（2）输入并建立多项式

（3）输出多项式