报名导航
报名导航
NOIP数据结构分析和编程模块

本课程适用于:
1、编程竞赛或信息奥赛
2、自主招生计算机编程特长生
3、本大纲最新更新时间:2018.10.15

<<返回课程体系 15年青岛双硕郑重承诺:1、零起点补课无额外收费2、没学会,可免费再学一次; 学费:9700元

【NOIP数据结构分析和编程模块】课程大纲

(一)绪论
绪论 1.主要内容:
(1)介绍什么是数据结构;
(2)基本概念和术语: 数据、数据元素、数据对象,以及数据结构的定义、逻辑结构、物理结构(理解)数据类型、抽象数据类型;
(3)抽象数据类型的表示与实现;
(4)算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。
2.基本要求
(1)了解学习数据结构的重要性;
(2)掌握数据结构的定义及相关概念和术语;
(3)了解抽象数据类型的定义、表示与实现方法;
(4)理解算法的概念、特点并掌握度量其效率的基本方法。
3.信息奥赛典型选择题或分析题解释
(二)线性表
线性表 1.主要内容:
(1)线性表的抽象数据类型定义和相关概念:数据项、记录、文件等;
(2)线性表顺序存储表示和基本操作的实现;
(3)线性表的链式存储表示和基本操作的实现;
(4)稀疏多项式的抽象数据类型定义、表示和加法的实现。
2.基本要求
(1)掌握线性表的定义和特点;
(2)熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法;
(3)熟练掌握单链表、循环链表、双向链表三种链表的表示,以及单链表的查找、插入、删除、创建等实现算法。
3.信息奥赛典型选择题或分析题解释
(三)栈和队列
栈和队列 1.主要内容:
(1)栈和队列的结构特性和抽象数据类型定义;
(2)栈和队列的顺序存储表示和实现;
(3)栈和队列的链式存储表示和实现;
(4)栈和队列在程序设计中的应用。
2.基本要求
(1)掌握栈和队列两种抽象数据类型的特点;
(2)掌握栈的两种存储表示和实现,特别注意栈满栈空的条件;
(3)掌握队列的两种存储表示和实现,特别注意队满队空的条件;
(4)了解递归算法与栈的关系。
3.信息奥赛典型选择题或分析题解释
(四)串
1.主要内容:
(1)串的抽象数据类型定义;
(2)串的表示和实现: 定长顺序存储结构和堆分配存储结构;
(3)串的各种基本操作的实现及其应用;
(4)串的模式匹配操作。
2.基本要求
(1)熟悉串的一些基本操作的定义,并能利用基本操作实现串的其它操作;
(2)掌握串的定长顺序存储结构以及基本操作的实现;
(3)掌握串的堆分配存储结构以及基本操作的实现;
(4)掌握串的简单模式匹配算法,理解KMP算法。
3.信息奥赛典型选择题或分析题解释
(五)数组和广义表
数组和广义表 1.主要内容:
(1)数组的抽象数据类型定义及其顺序表示和实现;
(2)特殊矩阵和稀疏矩阵的压缩存储;
(3)广义表的抽象数据类型定义和存储结构。
2.基本要求
(1)了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法;
(2)掌握对特殊矩阵进行压缩存储时的下标变换公式;
(3)熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法;了解十字链表等存储结构;
(4)掌握广义表的结构特点、取表头表尾操作,及其存储表示方法。
3.信息奥赛典型选择题或分析题解释
(六)树和二叉树
树和二叉树 1.主要内容:
(1)树的抽象数据类型定义和基本术语;
(2)二叉树的抽象数据类型定义、性质和存储结构;
(3)二叉树的遍历;
(4)线索二叉树的定义、遍历及线索化二叉树;
(5)树的存储结构、树和森林的遍历以及与二叉树的转换;
(6)Huffman树及其应用。
2.基本要求
(1)掌握树型结构的特点和基本术语;
(2)熟练掌握二叉树的性质,了解相应的证明方法;
(3)了解二叉树的顺序存储结构和链式存储结构,熟练掌握二叉链表存储结构;
(4)熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法,能灵活运用遍历算法实现二叉树的其他操作;
(5)熟练掌握二叉树的线索化过程,以及在中序线索二叉树上找结点的前驱与后继的方法;
(6)熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法;
(7)了解Huffman树的特性,掌握建立Huffman树和Huffman编码的方法。
3.信息奥赛典型选择题或分析题解释
(七)图
1.主要内容:
(1)图的定义和术语;
(2)图的四种存储结构:数组表示法(邻接矩阵)、邻接表、十字链表和邻接多重表;
(3)图的两种遍历策略:深度优先遍历和广度优先遍历;
(4)图的连通性和最小生成树;
(5)有向无环图及其应用:拓扑排序和关键路径;
(6)最短路径问题。
2.基本要求
(1)熟悉图的定义和术语;
(2)了解图的存储结构,熟练掌握数组表示法(邻接矩阵)和邻接表存储表示;
(3)熟练掌握图的深度优先遍历和广度优先遍历算法;
(4)掌握无向连通带权图的最小生成树求解算法;
(5)了解有向无环图、AOV网、AOE网及其在实际中的应用,熟悉拓扑排序算法和关键路径算法;
(6)熟悉两种最短路径问题求解算法。
3.信息奥赛典型选择题或分析题解释
(八)查找
查找 1.主要内容:
(1)查找的基本概念和相关术语;
(2)静态查找表:顺序查找、折半查找和索引顺序表查找;
(3)动态查找表:二叉排序树的查找、插入和删除;
(4)哈希表。
2.基本要求
(1)了解查找的作用,熟悉相关术语;
(2)熟练掌握顺序查找、折半查找和索引顺序表查找;
(3)熟练掌握二叉排序树的特性、构造和查找方法;
(4)熟练掌握哈希表的构造方法,特别是哈希函数和处理冲突方法的选取;
(5)通过分析等概率下的平均查找长度来衡量各种查找方法的效率。
3.信息奥赛典型选择题或分析题解释
(九)近5年,NIOP试题相关部分讲解
近5年,NIOP试题相关部分讲解 1、模拟考试
2、讲解提高
3、实时补充
4、强化训练
收缩
  • QQ咨询

  • 0532-80935385
  • 0532-82773360
  • 【微信咨询】
  • qdit169_com
微信号
  • 【QQ咨询】
  • QQ:571521935
QQ