第一章数据结构(16学时，包含8学时上机) 一、教学内容及要求（按节或知识点分配学时，要求反映知识的深度、广度，对知识 点的掌握程度（了解、理解、掌握、灵活运用），技能训练、能力培养的要求等) 1重点掌握内容 ●有关数据结构(DS)的基本概念(0.5学时) 数据元素、数据结构、C语言的数据类型、抽象数据类型 ●线性DS的常用存储结构(4.5学时) )线性表，包括：i.线性表的顺序存储和链式存储结构：ⅱ，顺序存储下的插入和删除算 法：ⅱ.线性链表（重点掌握），其中涵盖单链表的插入、删除和生成算法以及双向链表， 双向循环链表以及相应的算法： b)栈，包括：1.顺序栈（重点掌握)，顺序栈的入栈、2.出栈算法：ⅱ.链栈，涵盖链栈 的入栈算法以及链栈的出栈算法： c)队列，包括：.队列的顺序存储，涵盖入队算法、出队算法和循环队列入队、出队算 法（重点掌握）：ⅱ队列的链式存储，涵盖链队列入队算法、链队列出队算法： d)栈和队列的应用 ©)数组和串，包括：i.数组的顺序存储结构、iⅱ.二维数组的压缩存储、i.特殊矩阵的 存储实现 ●非线性DS的常见存储结构(4学时) a)树（重点掌握)，包括：i二叉树的概念、iⅱ.二叉树的存储结构、ii.二叉树的遍历 b)图，包括：i.图的基本概念：ⅱ.图的存储结构：邻接矩阵和邻接表：ⅱ.图的遍历： 深度优先遍历和广度优先遍历： ●查找、排序算法(6学时) a)查找算法，包括：i顺序查找：监视哨的作用：iⅱ.二分查找：二分查找的适用场合（适 用于哪种存储实现)：ⅱ.分块查找：w.树表查找：二叉排序树：v.哈希查找：重点掌握 哈希思想：关键字到地址的映射 b)排序算法，包括：i.排序的基本概念：排序码、稳定性、内部排序和外部排序：ⅱ.简 单排序算法：涵盖简单插入排序：把未排序部分第一个元素与有序部分元素依次比较，并 插入到适当位置：简单选择排序：每次选取无序部分最小的元素，跟无序部分第一个元素 交换：冒泡排序：两两比较，每次将最大的元素交换到最右端：ⅱ.快速排序算法：分
第一章 数据结构（16 学时，包含 8 学时上机） 一、教学内容及要求（按节或知识点分配学时，要求反映知识的深度、广度，对知识 点的掌握程度（了解、理解、掌握、灵活运用），技能训练、能力培养的要求等） 1 重点掌握内容 有关数据结构（DS）的基本概念（0.5 学时） 数据元素、数据结构、C 语言的数据类型、抽象数据类型 线性 DS 的常用存储结构（4.5 学时） a) 线性表，包括：i. 线性表的顺序存储和链式存储结构；ii. 顺序存储下的插入和删除算 法；iii. 线性链表（重点掌握），其中涵盖单链表的插入、删除和生成算法以及双向链表， 双向循环链表以及相应的算法； b) 栈，包括：i. 顺序栈（重点掌握），顺序栈的入栈、2. 出栈算法；ii. 链栈，涵盖链栈 的入栈算法以及链栈的出栈算法； c) 队列，包括：i. 队列的顺序存储，涵盖入队算法、出队算法和循环队列入队、出队算 法（重点掌握）；ii. 队列的链式存储，涵盖链队列入队算法、链队列出队算法； d) 栈和队列的应用 e) 数组和串，包括：i. 数组的顺序存储结构、ii. 二维数组的压缩存储、iii. 特殊矩阵的 存储实现 非线性 DS 的常见存储结构（4 学时） a) 树（重点掌握），包括：i. 二叉树的概念、ii. 二叉树的存储结构、iii. 二叉树的遍历 b) 图，包括：i. 图的基本概念；ii. 图的存储结构：邻接矩阵和邻接表；iii. 图的遍历： 深度优先遍历和广度优先遍历； 查找、排序算法（6 学时） a) 查找算法，包括：i. 顺序查找：监视哨的作用；ii. 二分查找：二分查找的适用场合（适 用于哪种存储实现）；iii. 分块查找；iv. 树表查找：二叉排序树；v. 哈希查找：重点掌握 哈希思想：关键字到地址的映射 b) 排序算法，包括：i. 排序的基本概念：排序码、稳定性、内部排序和外部排序；ii. 简 单排序算法：涵盖简单插入排序：把未排序部分第一个元素与有序部分元素依次比较，并 插入到适当位置；简单选择排序：每次选取无序部分最小的元素，跟无序部分第一个元素 交换； 冒泡排序：两两比较，每次将最大的元素交换到最右端；iii. 快速排序算法：分
区交换的思想，基准元素的选择，快速排序的稳定性：ⅳ.归并排序算法：二路归并排序 2理解内容 ●顺序存储和链式存储的优缺点对比及应用场合(0.5学时) 3了解内容 ● 链栈(0.3学时) ●链队列(0.2学时) 二、教学重点、难点及解决办法（分别列出教学重点、难点，包括教学方式、教 学手段的选择及教学过程中应注意的问题：哪些内容要深化，那些内容要拓宽等等) 1.顺序存储和链式存储 该知识点属于本章的核心技术，也是重点和难点内容。顺序存储和链式存储各有优缺点， 也有各自适用的应用场合。许多类型的数据逻辑结构都可以采用这两种物理存储来实现，如 何选择是难点。另外一方面，数据的物理存储同其操作算法存在着密切的关系，这种关系也 有必要强调。 解决办法：该知识点可以通过线性表的两种存储模式：顺序表和链表来展开。介绍完线 性表的逻辑特征后，让学生就线性表如何在计算机当中实现物理存储展开讨论，引导他们得 出两种物理存储方式后，讨论两种方案各自的优缺点，指出顺序存储可以节约存储空间，实 现随机访问，但插入删除操作耗时：链式存储需要付出指针的开销，而且只能实现顺序访问， 但插入删除操作方便高效。最后，通过两个实例程序的分析来印证上述结论，有可能的情况 下，组织学生讨论两种实现算法的CPU和存储开销。本知识点的教学还要同上机实验结合 起来进行。 2.双向链表插入算法指针修改顺序 该知识点属于本章重点和难点内容。链式存储相对于顺序存储而言对内存要求低，不需 要系统确保连续存储空间，逻辑上顺序的元素在屋里上可以不连续，而是通过指针表达元素 之间的逻辑关系：链式存储的插入和删除操作也简单高效，只需要修改指针域，而不会引起 元素移动。本部分知识的重点是单链表的结点结构描述以及单链表的插入删除操作算法。由 于涉及到指针，因此指针域的修改是难点，尤其对于双向链表，由于指针数量多，其修改顺 序是一个难点，错误的修改顺序会导致链表的断链。 解决办法：相对于单向链表，双向链表访问直接前趋和直接后继都很方便，但是在插入 和删除操作时，需要修改更多的指针，并且指针的修改顺序有严格要求，否则会引起链表的 断链。本知识点可通过案例教学的模式展开，先给出教材的案例，让学生讨论插入操作时指
区交换的思想，基准元素的选择，快速排序的稳定性；iv. 归并排序算法：二路归并排序 2 理解内容 顺序存储和链式存储的优缺点对比及应用场合（0.5 学时） 3 了解内容 链栈（0.3 学时） 链队列（0.2 学时） 二、教学重点、难点及解决办法（分别列出教学重点、难点，包括教学方式、教 学手段的选择及教学过程中应注意的问题；哪些内容要深化，那些内容要拓宽等等） 1. 顺序存储和链式存储 该知识点属于本章的核心技术，也是重点和难点内容。顺序存储和链式存储各有优缺点， 也有各自适用的应用场合。许多类型的数据逻辑结构都可以采用这两种物理存储来实现，如 何选择是难点。另外一方面，数据的物理存储同其操作算法存在着密切的关系，这种关系也 有必要强调。 解决办法：该知识点可以通过线性表的两种存储模式：顺序表和链表来展开。介绍完线 性表的逻辑特征后，让学生就线性表如何在计算机当中实现物理存储展开讨论，引导他们得 出两种物理存储方式后，讨论两种方案各自的优缺点，指出顺序存储可以节约存储空间，实 现随机访问，但插入删除操作耗时；链式存储需要付出指针的开销，而且只能实现顺序访问， 但插入删除操作方便高效。最后，通过两个实例程序的分析来印证上述结论，有可能的情况 下，组织学生讨论两种实现算法的 CPU 和存储开销。本知识点的教学还要同上机实验结合 起来进行。 2. 双向链表插入算法指针修改顺序 该知识点属于本章重点和难点内容。链式存储相对于顺序存储而言对内存要求低，不需 要系统确保连续存储空间，逻辑上顺序的元素在屋里上可以不连续，而是通过指针表达元素 之间的逻辑关系；链式存储的插入和删除操作也简单高效，只需要修改指针域，而不会引起 元素移动。本部分知识的重点是单链表的结点结构描述以及单链表的插入删除操作算法。由 于涉及到指针，因此指针域的修改是难点，尤其对于双向链表，由于指针数量多，其修改顺 序是一个难点，错误的修改顺序会导致链表的断链。 解决办法：相对于单向链表，双向链表访问直接前趋和直接后继都很方便，但是在插入 和删除操作时，需要修改更多的指针，并且指针的修改顺序有严格要求，否则会引起链表的 断链。本知识点可通过案例教学的模式展开，先给出教材的案例，让学生讨论插入操作时指