文档详情

数据结构考核知识点.doc

发布:2018-03-05约1.85千字共3页下载文档
文本预览下载声明
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章 排序 掌握排序方法分类、算法时间复杂度(平均/最好/最坏)、辅助空间、“稳定”与否。  掌握直接插入排序、希尔排序的过程。 掌握直接选择排序、堆排序算法(重点掌握初始堆的形成过程以及筛选调整过程)的过程。 掌握冒泡排序、快速排序的过程。 掌握归并排序的过程。 基数排序 掌握算法实现程序:直接插入排序、直接选择排序、冒泡排序、快速排序
显示全部
相似文档