数据结构考核知识点.doc
文本预览下载声明
BuildDate:2011-12-01
第1章 概论
逻辑结构和存储结构。
时间复杂度(大O表示法)、空间复杂度。
第2章 线性表
线性表的存储结构:顺序表、单链表、循环链表、双向链表。各自的优缺点;如何选择相应的表结构
掌握顺序表上的操作:插入、删除、查找、初始化。算法实现、性能分析。
掌握单链表上实现的建表、查找、插入和删除(逆转、合并)等基本算法,时间复杂度分析。
掌握双链表的定义,及其插入、删除、查找等算法实现。
应用顺序表、链表解决实际问题。
程序实现:链表的基本操作(查找、插入、删除)、其他操作(逆转、合并等等)。双链表的插入、删除。
第3章 栈和队列
栈和队列的概念、特点、存储结构。
掌握顺序栈和链栈上实现的进栈、退栈、栈空等算法实现。
掌握顺序循环队列和链队列上实现的入队、出队等算法实现。利用 头指针front和尾指针rear计算对列中元素个数,队列空的判断,队列初始化、进队列、出队列算法实现(三种情况的循环队列:设头尾指针、只设头指针和计数器、只设尾指针和计数器)
应用栈、队列解决实际问题
程序实现:栈、队列的程序实现。
第4章 串和数组
串的定义、概念、存储结构。
掌握顺序串的基本运算:赋值运算、复制、求串长度、判断串相等、串连接、求子串、查找子串位置。
简单串匹配(串匹配的概念、模式串、子串的概念)
KMP算法的Next数组(程序不要求)
掌握多维数组的顺序存储结构及地址计算方式。
掌握对称、三角等特殊矩阵的压缩存储、地址计算。
理解稀疏矩阵的三元组表表示方法及有关算法(加、转置)。
程序实现:串定位的BF算法、
第5章 递归和广义表
理解递归的定义。
掌握递归模型的设计,转换成递归函数。
理解广义表的概念、表示方式、存储方式。
了解广义表的常见运算,掌握求长度、深度、表头和表尾。(程序不做要求)
程序实现:简单的递归程序的实现
第6章 树和二叉树
掌握二叉树的定义、性质,了解相应的证明方法。(判断一棵树是否为二叉树、计算某一层的最大(小)结点数、计算某棵二叉树的总的结点数、根据高度计算某完全二叉树的最多节点总数等。)
掌握二叉树的两种存储方法、特点及适用范围。
顺序存储(根据树形给出顺序存储结构、或者给出顺序存储结构画出该二叉树)
二叉链存储结构(创建二叉树、求二叉树高度、求二叉树结点个数、求二叉树叶子结点个数等算法实现)
掌握二叉树的基本运算、三种遍历算法。
掌握给定二叉树的三种遍历表示、给定两种遍历构造出二叉树。
掌握树和森林与二叉树之间的转换。
二叉树的线索化和线索二叉树的遍历算法实现。(给出一棵二叉树,要求给出中序线索化二叉树;线索化二叉树的遍历)
哈夫曼树的创建、哈夫曼编码以及WPL计算。
掌握算法实现程序:三种遍历(前序、中序、后序)和中序线索二叉树的遍历算法
第7章 图
了解图的常用术语及含义。
掌握邻接矩阵和邻接表这两种存储结构的特点及适用范围。
给出一个图,能够给出邻接矩阵、邻接表;能给出DFS、BFS序列。
能够利用图的两种遍历设计算法解决简单的应用问题。
掌握求最小生成树 Prim和Kruskal算法的基本思想和过程。
掌握单源最短路径的Dijkstra算法的基本思想和过程。
掌握AOV网、拓扑排序的基本思想和过程。
掌握AOE网、有向图关键路径查找过程。
掌握算法实现程序:DFS深度优先搜索和BFS广度优先搜索
第8章 查找
ASL平均查找长度计算、时间复杂度、空间复杂度。
掌握顺序查找、二分查找的过程和查找效率分析。
理解二分查找对存储结构及关键字的要求。
理解分块查找的过程。
掌握二叉排序树的插入、删除、建树和查找过程及时间性能。
理解AVL树、平衡因子的概念。
AVL 树调整方法,建立、查找的过程。
掌握散列表、散列函数、散列地址和装填因子等有关概念。了解几种常用的散列函数构造方法。
掌握采用线性探测法和拉链法解决冲突时,散列表的建表方法、查找过程以及ASL的计算。(成功、不成功两种情况)
掌握算法实现程序:顺序查找、二分查找
第9章 排序
掌握排序方法分类、算法时间复杂度(平均/最好/最坏)、辅助空间、“稳定”与否。
掌握直接插入排序、希尔排序的过程。
掌握直接选择排序、堆排序算法(重点掌握初始堆的形成过程以及筛选调整过程)的过程。
掌握冒泡排序、快速排序的过程。
掌握归并排序的过程。
基数排序
掌握算法实现程序:直接插入排序、直接选择排序、冒泡排序、快速排序
显示全部