《数据结构》课程教学大纲

数据结构课程教学大纲

（DataStructure）

学时数：72

其中：实验学时：10

课外学时：0

学分数：4.5

适用专业：网络工程

一'课程的性质、目的和任务

数据结构是计算机、网络工程专业的必修学科基础课程，主要介绍：线性表、栈、队列、

数组、串、树、二叉树、图等基本数据结构及其应用；排序及查找的原理与方法；数据的存

储结构。通过本课程的学习使学生掌握基本数据结构的概念、特征、存贮结构及算法和算法

分析的手段。熟悉基本结构在计算机学科的应用，，训练学习使用高级语言编写合理算法的

能力。

二、课程教学的基本要求

（-）了解典型数据结构的逻辑关系，存贮结构，操作及算法的关系。

（二）熟练掌握各种基本数据结构的概念、特点、存贮方式、算法及分析评估。

（三）掌握基本算法分析方法。

（四）熟悉查找及排序的典型算法。

（五）针对实际问题，选择合理的数据结构及实现相应的操作。

三'课程的教学内容、重点和难点

第一章概论（2学时）

一、基本内容：

（-）数据、数据元类、数据类型、数据结构。

（-）算法与数据结构的关系。

（三）算法的描述，评价标准及评估。

第一节：基本概念和术语

第二节：抽象数据类型

第三节：算法分析

第四节：性能分析与度量

二、基本要求：

（-）熟悉数据结构基本概念

（二）了解数据结构要解决的问题

重点：数据结构的三个要点。

难点：区分数据结构，数据类型，数据元素的差别。

第二章线性表（8学时）

一、基本内容：

（-）线性表的定义及抽象操作。

(-)线性表的两种存贮结构及算法。

(三)链表的应用举例。

第一节线性表

第二节线性表的顺序表示与实现

第三节线性表的链式表示与实现链表

第四节一元多项式的表示与实现

二、基本要求：

(-)掌握线性表的基本概念

(-)掌握线性表的各种算法

重点：线性表的基本操作。

难点：线性表的抽象操作，链表应用。

第三章栈和队列(8学时)

一、基本内容：

(-)队列、栈的定义及抽象操作。

(-)队列、栈的顺序存贮结构及相关算法。

(三)队列、栈的链式存贮结构及相关算法。

(四)多队列、栈的顺序存贮。

(五)栈的应用举例、栈与递归过程的关系。

第一节：栈

第二节：队列

第三节：栈与队列的实现

第四节：栈与队列的应用举例

二、基本要求：

(-)掌握队列、栈的基本概念

(-)掌握队列、栈的各种算法

(三)熟悉队列、栈的各种应用

重点：队列、栈的各种算法。

难点：循环队列的概念与操作。

第四章数组、广义表(4学时)

一、基本内容：

(-)数组的定义及操作。

(-)数组的顺序存贮及规律。

(三)矩阵的压缩存贮。

(四)广义表简介。

第一节：数组的定义

第二节：数组的顺序表示和实现

第三节：矩阵的压缩存储

第四节：广义表简介

二、基本要求：

(-)掌握数组的基本概念

(二)掌握矩阵的压缩存贮的各种算法

重点：矩阵的各种压缩存贮。

难点：十字链表的结构与操作。

第五章串（4学时）

一、基本内容：

（-）串的基本概念和抽象操作。

（-）串的存贮方式介绍。

（三）串的操作的实现。

第一节：串类型的定义

第二节：串的表示和实现

第三节：串的模式匹配算法

二、基本要求：

（-）掌握串的基本概念

（二）掌握串的各种算法

（三）熟悉求子串的序号算法的实现原理

重点：串的存贮方式比较。

难点：子串定位算法实现。

第六章树和二叉树（10学时）

一、基本内容：

（-）树的定义及抽象操作。

（-）二叉树的性质及存贮方式（顺序、链式）。

（三）二叉树的遍历：前序、中序、后序、线索二叉树。

（四）树的存贮结构：双亲表示法、孩子表示法、孩子兄弟表示法等。

（五）树、森林、二叉树的转换、树的遍历。

（六）Huffman树及其应用。

第一节：树的定义和基本术语

第二节：二叉树

第三节：二叉树的存储结构

第四节：遍历二叉树

第五节：线索化二叉树

第六节：树与森林

第七节：赫夫曼树

二、基本要求：

（-）掌握树、二叉树的基本概念

（-）掌握二叉树存储结构及各种算法

（三）熟悉树的存储结构及相关操作的实现

重点：二叉树的概念与操作。

难点：二叉树的遍历算法与Huffman树。

第七章图（10学时）

一'基本内容：

（-）图的定义及基本操作。

（二）图的存贮结构：（邻接矩陈，邻接表存贮方法，十字链表法）。

（三）图的遍历：深度优先搜索与广度优先搜索算法。

（四）连通分量，生成树，最小生成树。

（五）拓扑排序，关链路径。

（六）最短路径。

第一节：图的定义和术语

第二节：图的存储结构

第三节：图的遍历与连通性

第四节：最小生成树

第五节：活动网络

第六节：最短路径

二、基本要求：

（-）掌握图的基本概念

（二）掌握图遍历的DFS和BFS算法

（三）熟悉图的实现与应用

重点：图的DFS与BFS算法，拓扑排序。

难点：最小生成树，拓扑排序。

第八章内部排序（10学时）

一、基本内容：

（-）概述。

（二）插入排序：直接插入排序，希尔排序。

（三）选择排序：直接选择排序，堆排序。

（四）交换排序：冒泡排序，快速排序。

（五）归并排序：

（六）排序各种方法比较。

第一节：概述

第二节：插入排序（直接插入、折半插入、表插入排序、希尔排序）

第三节：交换排序（起泡排序、快速排序）

第四节：选择排序（简单选择排序、树形选择排序、堆排序）

第五节：归并排序

二、基本要求：

（-）掌握排序的基本概念

（-）掌握排序的各种算法

（三）熟悉排序算法的比较与应用。

重点：插入排序、交换排序。

难点：堆排序、快速排序。

第九章查找（8学时）

一、基本内容：

（-）概述。

（二）顺序查找算法：顺序查找、折半查找、分块查找。

（H）树表的查找、二叉排序树，平衡二叉树。

（四）哈希（Hash）表：概念，构造方法，冲突与冲突处理方法。

第一节：静态查找表

第二节：动态查找树表

第三节：哈希表

二、基本要求：

（-）掌握查找的基本概念

（-）掌握查找的各种算法

（三）熟悉HASH表的实现与应用

重点：顺序查找算法

难点：二叉排序树，哈希（Hash）表

第十章外部排序（4学时）

一、基本内容：

（一）概述（外存贮器的特点，外部排序的特点）

（二）K—路归并排序。

（三）初始归并的产生。

（四）最佳归并树。

第一节：概述

第二节：归并排序

第三节：最佳归并树

二、基本要求：

（-）掌握外部排序的基本概念

（-）掌握外部排序的各种算法

（三）熟悉归并算法的实现。

重点：K—路归并排序

难点：最佳归并树

第十一章文件（2学时）

一、基本内容：

（-）基本概念。

（-）文件组织：顺序文件，索引顺序文件、哈希文件、链接文件、倒排文件。

第一节：概述

第二节：文件组织

二、基本要求：

（-）掌握文件的基本概念

（二）掌握文件的组织结构

重点：文件基本概念，顺序文件。

难点：哈希文件。

四'课程各教学环节要求

本课程教学环节除讲课外，还有实验课等，实验课是培养工科学生实验技能的主要手

段，是本课程的实践环节，通过实验训练使学生能达到如下要求：

（―）实验要求：

1、实现队列、栈的各种算法及操作。

2、用Huffman树进行加密抽样与解密算法。

3、实现深度优先搜索与广度优先搜索算法.

4、实现典型的排序算法。

5、实现典型的查找算法。

（二）考试环节要求：

1、本课程的命题考试将根据本大纲所规定的内容和目标来确定考试范围和考核要求。

考试命题会覆盖各章，并适当突出重点章节，体现本课程的内容重点。

2、本课程在试题中对不同能力层次要求的分数比例一般为：基础题占20%,简答与计

算题占60%-70%,综合运用与编成题占10%-20%。

3、本课程采取期末考试与平时作业考查相结合的方法，期末考试成绩占70%,平时作

业成绩（含实验）占30%。期末考试闭卷笔试，根据教学大纲命题，考试时间为120分钟,

卷面分值100分。

五、学时分配

各教学环节学时分配

作业量备

早万主要内容讲实讨课其小

习（题）注

授验论题外它计

一概论222

二线性表883

三栈与队列6284

四数组与广义表442

五串443

六树与二叉树82108

七图82108

八内部排序82106

九查找