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

1、数据结构B课程教学大纲课程编号：20211514总学时数：48（理论32，实验16）总学分数：3课程性质：专业选修课适用专业：地理信息系统、测绘工程一、课程的任务和基本要求：课程任务：“数据结构”是计算机科学中一门综合性的专业基础课。计算机加工处理的对象是数据，而数据在计算机中的存储和表示并不是杂乱无章的，它们具有一定的结构并且有着内在的联系。因此，为了使计算机能够有效的处理数据，不但要求熟练掌握计算机程序语言，还必须掌握数据组织、存储和运算的方法。本课主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和

2、物理结构的基本概念，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，并初步掌握算法的时间分析和空间分析的技术。为学习地理信息系统和数据库等课程奠定基础。以C语言作为算法的描述工具，强化数据结构基本知识和程序设计基本能力的双基训练。基本要求：1、了解数据结构及其分类、数据结构与算法的密切关系。2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。4、掌握数据结构在排序和查找等常用算法中的应用。二、基本内容和要求：第1章 绪论1.1 数据

3、结构研究的对象1.2 基本概念和术语1.3 算法的描述语言1.4 算法和算法分析要求：了解数据结构研究的对象和算法的描述与分析第2章 线性表2.1 理解线性表的逻辑结构及基本操作2.2 掌握线性表的顺序存储结构的特点2.3 掌握顺序表的基本操作算法2.4 掌握线性表的链式存储结构的特点2.5 掌握单链表、静态链表、循环链表双向链表的基本操作算法及其应用要求：掌握线性表的顺序表示和实现及链式表示和实现第3章 栈和队列3.1 掌握栈和队列的特点和区别；3.2 掌握栈和队列的存储表示和实现算法3.3 掌握栈和队列的应用；要求：掌握栈和队列的表示和实现第4章 串4.1 了解字符串数据的逻辑结构特点和基

4、本操作4.2 了解串的存储结构设计和串的应用实例要求：了解串的表示和实现第5章 树和二叉树5.1 掌握树结构的特点及树的术语，了解树的基本操作 5.2 掌握二叉树的概念，了解基本操作5.3 掌握二叉树的性质和两种特殊的二叉树的概念5.4 了解二叉树的存储结构5.5 掌握二叉树的遍历思想及算法，掌握线索二叉树的思想及算法5.6 了解树的存储结构；掌握树、森林和二叉树的转换方法5.7 掌握树和森林的遍历思想5.8 掌握哈夫曼树的概念、构造算法及其应用要求：掌握树和二叉树的概念，二叉树的性质、二叉树的遍历及线索二叉树的方法第6章 图6.1 掌握图结构的特点和有关术语，了解图的基本操作6.2 了解图的

5、存储结构6.3 掌握图的两种遍历思想和算法6.4 理解无向图的连通性，掌握构造最小生成树的两种思想方法和算法6.5 了解有向无环图的概念、拓扑排序的方法及应用6.6 掌握求有向图中的最短路径的两种方法及算法要求：了解土的存储结构，掌握图的遍历、图的拓扑排序、最短路径、关键路径第7章 查找7.1 了解查找的基本概念7.2 掌握静态查找中几种重要的查找方法及算法顺序查找、折半查找、索引查找7.3 掌握动态查找中几种重要的查找方法及算法二叉排序树和平衡二叉树的查找、哈希表查找 7.4 了解各种查找方法的特点要求：掌握各种查找方法及算法第8章 (内部)排序8.1 了解有关排序的基本概念8.2 掌握几种

6、重要的内部排序依据的原则、方法和算法插入排序（直接插入排序、希尔排序）、交换排序（起泡排序、快速排序）、选择排序（简单选择排序、树形排序、堆排序）、归并排序（2-路归并排序）8.3 了解各种排序方法的特点要求：掌握集中重要的内部排序依据的原则、方法和算法三、实践环节和要求：实验1 用顺序结构实现线性表要求：用顺序结构实现线性表的建立、查找、插入、删除实验2 用链式结构实现线性表要求：用链式结构实现线性表的建立、查找、插入、删除实验3 二叉树的应用要求：采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等实验4 二叉树的排序要求：实现二叉排序树上的

7、查找算法实验5 多种排序法的实现要求：实现直接插入、冒泡、直接选择、快速、归并等排序算法四、教学时数分配：教学内容 学时第1章 绪论 2第2章 线性表 12第3章 栈和队列 4第4章 串 2第5章 树和二叉树 8第6章 图 4第7章 查找 8第8章 内部排序 8其中实验5个，共16学时。五、其它项目：六、有关说明：1、教学和考核方式：本课程属考查课，考核方式为开卷。2、习题：数据结构题集（C语言版），每章练习题（每次课后3-4题）。3、能力培养要求：强化数据结构基本知识和程序设计基本能力，熟练应用数据结构的基本算法，对具有一定逻辑关系的数据进行算法设计。综合应用数据结构的原理，培养解决一些应用性问题的能力。4、与其它课程和教学环节的联系：先修课程和教学环节：C语言，数据库原理与应用后续课程和教学环节：毕业论文平行开设课程和教学环节：GIS设计与开发5、教材和主要参考书目：（1）教材：数据结构（C语言版），严蔚敏、吴伟民编，清华大学出版社（2）主要参考书目： 数据结构（C语言版），朱战立、刘天