《数据结构》试验大纲

试验大纲

(一)实验课程简介

“数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

(二)实验教学目的和基本要求

不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。   为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。

(三)实验项目名称与学时分配

序号 实验名称 学时 类型 实验要求
100100701 约瑟夫环问题 2 基础性 必做
100100702 长整数运算 2 设计性 选做
100100703 停车场管理 3 基础性 必做
100100704 文学研究助手 2 基础性 选做
100100705 简单行编辑程序 3 设计性 必做
100100706 树基本操作 2 综合性 必做
100100707 二叉树基本操作 2 综合性 必做
100100708 图遍历的演示 2 基础性 选做
100100709 图的基本操作 4 设计性 必做
100100710 哈希表设计 3 设计性 选做
100100711 常用排序算法的对比分析 4 综合性 必做

(四)实验方式及基本要求

上机操作,Windows XP及以上版本,VC系统或Turbo c2.0环境。

(五)考核方式及成绩评定

采用上机情况、程序质量、实习报告相结合的形式,满分为100分。

  • 1.上机情况(30%):包括出勤情况、调试表现、是否上网、玩游戏。
  • 2. 程序质量(50%)
  • 3. 实习报告(20%)

(六)教学参考书目

  • (1)数据结构. 黄扬铭编著. 科学出版社出版,2001
  • (2) Data Structures with C++. William Ford et al. Prentice Hall Inc, 1996
  • (3) Data Structures & Program Design in C. Robert Kruse et al. 2nd Ed. Prentice Hall, 1997
  • (4) 数据结构(第二版). 黄刘生 唐策善编著. 中国科学技术大学出版社,2000
  • (5) 数据结构. 刘大有编著. 高等教育出版社,2002
  • (6) 数据结构(面向对象语言描述). 朱振元等编著. 清华大学出版社,2004
  • (7) 数据结构(C语言版)实践教程. 胡元义等编著. 西安电子科技大学出版社,2008

(七)实验内容安排

【实习一】 线性表

1.实验目的:本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。 2.实验内容:约瑟夫环;长整数运算。

【实习二】 栈、队列与递归算法设计

1.实验目的:仅仅认识到栈和队列是两种特殊的线性表是远远不够的,本次实习的目的在于使读者深入了解栈和队列的特征,以便在实际问题背景下灵活运用它们;同时还将巩固这两种结构的构造方法,接触较复杂问题的递归算法设计。 2.实验内容:停车场管理。

【实习三】 串及其应用

1.实验目的:本次实习的目的是熟悉串类型的实现方法和文本模式匹配方法,熟悉一般文字处理软件的设计方法,较复杂问题的分解求精方法,在第二次实习的基础上,进一步强化这样一个观念:程序是数据结构结合定义在其上的操作,此外还希望起到训练合作能力和熟悉文件操作的目的。本次实习的难度较大。 2.实验内容:文学研究助手;简单行编辑程序。

【实习四】 树、图及其应用

1.实验目的:树和图是两种应用极为广泛的数据结构,也是这门课程的重点。它们的特点在于非线性。广义表本质上是树结构;稀疏矩阵的十字链表存储结构也是图的一种存储结构,故也把它们归在这次实习中。本章实习继续突出了数据结构加操作的程序设计观点,但根据这两种结构的非线性特点,将操作进一步集中在遍历操作上,因为遍历操作是其他众多操作的基础。遍历逻辑的(或符号形式的)结构,访问动作可是任何操作。本次实习还希望达到熟悉各种存储结构的特征,以及如何应用树和图结构解决具体问题(即原理与应用的结合)等目的。 2.实验内容:图遍历的演示

【实习五】 查找和排序

  • .实验目的:本次实习旨在集中对几个专门的问题作较为深入的探讨和理解,也不强调对某些特定的编程技术的训练。
  • .实验内容:哈希表设计;内部排序算法比较。