数据结构
《数据结构》
教学⼤纲
哈尔滨师范⼤学信息科学系
《数据结构》
⼀、课程设置的有关说明1．课程性质：是必修课、选修课
是信息与计算科学专业的必修的核⼼课程。是学习计算机和本专业后续课程的基础，也是今后⼯作中必备的和最常⽤的知识。2．课程定义：(简要描述、该课程在学习中的地位、作⽤及发展状况)
它主要内容是讨论现实世界中数据(既事物的抽象描述)的各种逻辑结构,以及进⾏各种⾮数值运算的算法。⽬的是使学⽣掌握数据组织、存储和处理的常⽤⽅法，为以后进⾏软件开发和学习后续专业课打下基础。3．设置本课程的⽬的和基本要求：
本课程是为继续学学习计算机软件和进⾏软件开发打下坚实的基础。为此，本课程在选材和内容组织等⽅⾯⼒求做到：科学性、新颖性和实⽤性相结合，⼒图在阐明基本原理和⽅法的同时，也能反映某些最新研究成果，使学⽣牢固地掌握本学科的基本知识。4．教学内容简介
数据的逻辑结构分为线性结构、树（层次）结构和图形结构、链接结构、索引结构和散列结构中的⼀种或多种的组合。对数据进⾏的⾮数值运算主要包括插⼊、删除、查找、和输出等。需要特别指出：数据的存储结构既适⽤于内存，也适⽤于外存，不仅要学会对内存数据操作的算法，⽽且要学会对外存数据（⽂件）操作的算法，这样才能解决实际软件开发的问题，达到学以致⽤的⽬的。
⼆、具体教学内容
第⼀章绪论(4学时)
教学⽬的和教学基本要求：
要求了解什么是数据结构，及其相关的术语。了解学习本课程所必须的C++知识。
掌握如何进⾏算法评价，包括正确性、健壮性、可读性、简单性、时间复杂性和空间复杂性等。
内容提要：
第⼀节常⽤术语
基本教学内容：对数据结构中⼀些常⽤的名词和术语给以确定的含义。包括数据、数据元素、数据记录、关键字、关键项、数据处理、数据结构、线性结构、树形结构、图形
结构、数据类型、抽象数据类型、数据对象和算法。重点是关键字、线性结构、树形结构和图形结构，难点是数据结构的⼏种形式。
第⼆节 算法描述
基本教学内容：介绍描述算法的各种⽅法，重点是⽤程序描述。 第三节 算法评价
数据结构教案(总32页)
-CAL-FENGHAI.-(YICAI)-Company One1
-CAL-本页仅作为文档封面，使用请直接删除
2015 至2016 学年第二学期
数 据 结 构 课程
教
案
课程编码： 1261D03
总学时／周学时： 80 / 5
开课时间： 2016年2 月 24日第 1 周至第 16
周
授课年级、专业、班级： 15级网工程2班
使用教材 严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.
系别/教研室： 信息工程学院 / 物联网工程
授课教师： 刘波 教学目标：
《数据结构》是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。
通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。
教学要求:
本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。
学生通过学习该课程后主要应掌握以下内容：
1．了解数据结构及有关的基本概念；
数据结构考试题库含答案
数据结构习题集含答案目录目录1选择题2第一章绪论2第二章线性表4第三章栈和队列5第四章串6第五章数组和广义表7第六章树和二叉树7第七章图9第八章查找11第九章排序12简答题15第一章绪论15第二章线性表20第三章栈和队列22第四章串24第五章数组和广义表24第六章树和二叉树26第七章图31第八章查找33第九章排序34编程题36第一章绪论36第二章线性表36第三章栈和队列46第四章串46第五章数组和广义表46第六章树和二叉树46第七章图46第八章查找46第九章排序51选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（A）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.某数据结构是指（A）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A）。
A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B）。
第一章 绪论之五兆芳芳创作
1、 数据结构是计较机中存储、组织数据的方法.精心选择的数据结构可以带来最优效率的算法.
2、 程序设计=算法 +数据结构
3、 解决问题办法的效率：
跟数据的组织方法有关
跟空间的利用效率有关
跟算法的巧妙程度有关
4、 数据：所有能输入到计较机中,且被计较机处理的符号的荟萃，是计较机操纵对象的总称；
是计较机处理的信息的某种特定的符号暗示形式.
5、 数据元素：数据中的一个“个别”,数据结构中讨论的根本单位.相当于“记实”,在计较机程序中通常作为一个整体考虑和处理.
6、 数据项: 相当于记实的“域”, 是数据的不成联系的最小单位,如学号.数据元素是数据项的荟萃.
7、 数据对象：性质相同的数据元素的荟萃.
例如: 所有运动员的记实荟萃
8、 数据结构：是相互间存在某种关系的数据元素荟萃.
9、 数据结构是带结构的数据元素的荟萃.
10、 不合的关系组成不合的结构.
11、 次序关系： {|i=1,2,3,4,5,6}
12、 对每种数据结构，主要讨论如下两方面的问题：
1）数据的逻辑结构，数据结构的根本操纵；
2）数据的存储结构，数据结构根本操纵的实现；
13、 数据的逻辑结构：
数据之间的结构关系，是具体关系的抽象.
数据结构的根本操纵：
指对数据结构的加工处理.
14、数据的存储结构 (物理结构)：
数据结构在计较机内存中的暗示.
数据结构根本操纵的实现：
根本操纵在计较机上的实现（办法).
15、 数据结构的有关概念
16、数据元素的4类的根本结构：
○1荟萃；
○2线性结构：结构中数据元素之间存在一对一的关系；
○3树形结构：结构中数据元素之间存在一对多的关系；
○4图状结构或网状结构：结构中数据元素之间存在多对多的关系.
17、 C语言的优点：C语言可以直接操纵内存.
18、 每个节点都由两部分组成：数据域和指针域.
19、 链接存储结构特点： 比顺序存储结构的存储密度小
