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

《《数据结构》课程教学大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构》课程教学大纲.docx（6页珍藏版）》请在第一文库网上搜索。

1、数据结构课程教学大纲（DataStructure）学时数：72其中：实验学时：10课外学时：0学分数：4.5适用专业：网络工程一、课程的性质、目的和任务数据结构是计算机、网络工程专业的必修学科基础课程，主要介绍：线性表、栈、队列、数组、串、树、二叉树、图等基本数据结构及其应用；排序及查找的原理与方法；数据的存储结构。通过本课程的学习使学生掌握基本数据结构的概念、特征、存贮结构及算法和算法分析的手段。熟悉基本结构在计算机学科的应用，训练学习使用高级语言编写合理算法的能力。二、课程教学的基本要求（一）了解典型数据结构的逻辑关系，存贮结构，操作及算法的关系。（二）熟练掌握各种基本数据结构的概念、特点

2、、存贮方式、算法及分析评估。（H）掌握基本算法分析方法。（四）熟悉查找及排序的典型算法。（五）针对实际问题，选择合理的数据结构及实现相应的操作。三、课程的教学内容、重点和难点第一章概论（2学时）一、基本内容：（一）数据、数据元类、数据类型、数据结构。（二）算法与数据结构的关系。（H）算法的描述，评价标准及评估。第一节：基本概念和术语第二节：抽象数据类型第三节：算法分析第四节：性能分析与度量二、基本要求：（一）熟悉数据结构基本概念（二）了解数据结构要解决的问题重点：数据结构的三个要点。难点：区分数据结构，数据类型，数据元素的差别。第二章线性表（8学时）一、基本内容：（一）线性表的定义及抽象操作。

3、（二）线性表的两种存贮结构及算法。（H）链表的应用举例。第一节:第二节:第三节:第四节:线性表线性表的顺序表示与实现线性表的链式表示与实现链表一元多项式的表示与实现二、基本要求：（一）掌握线性表的基本概念（二）掌握线性表的各种算法重点：线性表的基本操作。难点：线性表的抽象操作，链表应用。第三章栈和队列（8学时）一、基本内容：（一）队列、栈的定义及抽象操作。（二）队列、栈的顺序存贮结构及相关算法。（三）队列、栈的链式存贮结构及相关算法。（四）多队列、栈的顺序存贮。（五）栈的应用举例、栈与递归过程的关系。第一节：栈第二节：队列第三节：栈与队列的实现第四节：栈与队列的应用举例二、基本要求：（）掌握队

4、列、栈的基本概念（二）掌握队列、栈的各种算法（三）熟悉队列、栈的各种应用重点：队列、栈的各种算法。难点：循环队列的概念与操作。第四章数组、广义表（4学时）一、基本内容：（一）数组的定义及操作。（二）数组的顺序存贮及规律。（三）矩阵的压缩存贮。（四）广义表简介。第一节：数组的定义第二节：数组的顺序表示和实现第三节：矩阵的压缩存储第四节：广义表简介二、基本要求：（一）掌握数组的基本概念（二）掌握矩阵的压缩存贮的各种算法重点：矩阵的各种压缩存贮。难点：十字链表的结构与操作。第五章串（4学时）一、基本内容：（一）串的基本概念和抽象操作。（二）串的存贮方式介绍。（三）串的操作的实现。第一节：串类型的定义

5、第二节：串的表示和实现第三节：串的模式匹配算法二、基本要求：（-）掌握串的基本概念（二）掌握串的各种算法（三）熟悉求子串的序号算法的实现原理重点：串的存贮方式比较。难点：子串定位算法实现。第六章树和二叉树（10学时）一、基本内容：（一）树的定义及抽象操作。（二）二叉树的性质及存贮方式（顺序、链式）。（三）二叉树的遍历：前序、中序、后序、线索二叉树。（四）树的存贮结构：双亲表示法、孩子表示法、孩子兄弟表示法等。（五）树、森林、二叉树的转换、树的遍历。（六）HUffman树及其应用。第一节：树的定义和基本术语第二节：二叉树第三节：二叉树的存储结构第四节：遍历二叉树第五节：线索化二叉树第六节：树与森

6、林第七节：赫夫曼树二、基本要求：（一）掌握树、二叉树的基本概念（二）掌握二叉树存储结构及各种算法（三）熟悉树的存储结构及相关操作的实现重点：二叉树的概念与操作。难点：二叉树的遍历算法与HUffinan树。第七章图（10学时）一、基本内容：（一）图的定义及基本操作。（二）图的存贮结构：（邻接矩陈，邻接表存贮方法，十字链表法）。（H）图的遍历：深度优先搜索与广度优先搜索算法。（四）连通分量，生成树，最小生成树。（五）拓扑排序，关链路径。（六）最短路径。第一节：图的定义和术语第二节：图的存储结构第三节：图的遍历与连通性第四节：最小生成树第五节：活动网络第六节：最短路径二、基本要求：（一）掌握图的基本

7、概念（二）掌握图遍历的DFS和BFS算法（三）熟悉图的实现与应用重点：图的DFS与BFS算法，拓扑排序。难点：最小生成树，拓扑排序。第八章内部排序（10学时）一、基本内容：（-）概述。（二）插入排序：直接插入排序，希尔排序。（三）选择排序：直接选择排序，堆排序。（四）交换排序：冒泡排序，快速排序。（五）归并排序：（六）排序各种方法比较。第一节：概述第二节：插入排序（直接插入、折半插入、表插入排序、希尔排序）第三节：交换排序（起泡排序、快速排序）第四节：选择排序（简单选择排序、树形选择排序、堆排序）第五节：归并排序二、基本要求：（一）掌握排序的基本概念（二）掌握排序的各种算法（三）熟悉排序算法的

8、比较与应用。重点：插入排序、交换排序。难点：堆排序、快速排序。第九章查找（8学时）一、基本内容：（一）概述。（二）顺序查找算法：顺序查找、折半查找、分块查找。（三）树表的查找、二叉排序树，平衡二叉树。（四）哈希（HaSh）表：概念，构造方法，冲突与冲突处理方法。第一节：静态查找表第二节：动态查找树表第三节：哈希表二、基本要求：（一）掌握查找的基本概念（二）掌握查找的各种算法（三）熟悉HASH表的实现与应用重点：顺序查找算法难点：二叉排序树，哈希（HaSh）表第十章外部排序（4学时）一、基本内容：（一）概述（外存贮器的特点，外部排序的特点）（二）K路归并排序。（三）初始归并的产生。（四）最佳归并

9、树。第一节：概述第二节：归并排序第三节：最佳归并树二、基本要求：（一）掌握外部排序的基本概念（二）掌握外部排序的各种算法（三）熟悉归并算法的实现。重点：K路归并排序难点：最佳归并树第十一章文件（2学时）一、基本内容：（一）基本概念。（二）文件组织：顺序文件，索引顺序文件、哈希文件、链接文件、倒排文件。第一节：概述第二节：文件组织二、基本要求：（一）掌握文件的基本概念（二）掌握文件的组织结构重点：文件基本概念，顺序文件。难点：哈希文件。四、课程各教学环节要求本课程教学环节除讲课外，还有实验课等，实验课是培养工科学生实验技能的主要手段，是本课程的实践环节，通过实验训练使学生能达到如下要求：（一）实

10、验要求：I、实现队列、栈的各种算法及操作。2、用Huffman树进行加密抽样与解密算法。3、实现深度优先搜索与广度优先搜索算法。4、实现典型的排序算法。5、实现典型的查找算法。（-）考试环节要求：I、本课程的命题考试将根据本大纲所规定的内容和目标来确定考试范围和考核要求。考试命题会覆盖各章，并适当突出重点章节，体现本课程的内容重点。2、本课程在试题中对不同能力层次要求的分数比例一般为：基础题占20%,简答与计算题占60%-70%,综合运用与编成题占10%-20%3、本课程采取期末考试与平时作业考查相结合的方法，期末考试成绩占70%,平时作业成绩（含实验）占30%。期末考试闭卷笔试，根据教学大纲

11、命题，考试时间为120分钟,卷面分值100分。五、学时分配章号主要内容各教学环节学时分配作业量（题）备注讲授实验讨论习题课外其它小计概论222二线性表883三栈与队列6284四数组与广义表442五串443六树与二叉树82108七图82108八内部排序82106九查找6284十外部排序442十一文件222期中测验、期末复习、机动22合计62107244、课程与其它课程的联系本课程一般应在学完语言、离散数学之后开课。而本课程又是后续的编译原理、操作系统原理、数据库系统原理等专业课程的前置课程。七、教材及教学参考书（一）教材严蔚敏.数据结构（C语言）.北京：清华大学出版社，2008年。（二）教学参考书1E11isHorowitz（朱仲涛译）.数据结构基础（C语言版）（第2版）.北京：清华大学出版社，2009年。2唐策善等.数据结构用C语言描述.北京：高等教学出版社，2007年。