(new)《数据结构与算法》上机实验要求.pdf

《数据结构与算法》课程实验内容与要求 一、 课程简介 本课程着重讲述 ①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应 的基本算法。②各种查找算法 ③典型内部排序算法。 二、 实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际 问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水 准的应用程序的能力。 三、 实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、 考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、 实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照附件中实验报告模版书写。实验报告中应 包括如下内容：  实验内容按任课教师下达的实验任务填写（具体实验题目和要求）；  实验过程与实验结果应包括如下主要内容：  数据结构定义  算法设计思路简介  算法描述：可以用自然语言、伪代码或流程图等方式  算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办 法等  算法时间复杂度分析  源程序清单与实验结果或其它说明可打印，并装订在实验报告之后。  实验报告雷同者，本次实验成绩为 0 分或雷同实验报告平分得分 五、 实验的软硬件环境 硬件环境：P Ⅱ以上微型计算机 软件环境：Windows98/2000, VC++6.0 或 turbo C 六、 实验内容安排 实验一 线性表应用 实验时间：2017年 3 月9日 1-2 节（地点：7-219），3月10日5-6节（地点：7-215） 实验目的： 理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、 删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际 问题背景下的灵活运用线性表来解决问题，实现相应算法。 每位同学可从下面题目中选择至少2题实现：其中第一题为必做题 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2 ）要求: （1）采用单链表存储结构一元稀疏多项式 （2 ）输入并建立多项式 （3 ）输出多项式 （4 ）实现多项式加、减运算 3 ）分析算法时间复杂度 2. 约瑟夫环问题 1）问题描述：有编号为 1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数 密码。开始给定一个正整数 m ，从第一个人按顺时针方向自 1 开始报数，报到 m 者出列，不再参加 报数，这时将出列者的密码作为 m ，从出列者顺时针方向的下一人开始重新自 1 开始报数。如此下 去，直到所有人都出列。试设计算法，输出出列者的序列。 2 ）要求: 采用顺序和链式两种存储结构实现 3 ）分析算法时间复杂度 3 ．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表