第一章数据结构(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. 快速排序算法：分