复习掌握范围.doc

2012数据结构复习掌握范围 第一章、绪论 填空题，选择题： 知道数据、数据元素、数据项的定义； 知道四类逻辑结构；两类物理结构； 知道逻辑结构的二元组形式化定义方式； 知道算法的几个特点； 会对常见简单算法评估算法复杂度。如给出矩阵的某种操作（加、转置、乘法），能够写出其时间复杂度。 第二章、线性表 选择题、填空题： 知道顺序表中逻辑位置相邻的元素，物理位置关系如何； 知道顺序表在插入元素过程中，如何处理表空间不够； 知道链表结点的组成，链表和数组在各种操作（随机读取、删除、插入）下的区别； 知道双向链表设置前驱指针域的目的； 第三章、栈和队列 选择题、填空题： 知道入栈出栈规则，入队出队规则，能够对给出的输入序列识别出不可能的出栈或出队顺序。 知道前缀、中缀、后缀运算表达式的定义，能够相互转换。 知道采用循环队列的目的、物理数据结构； 知道书中提到模拟银行多个窗口排队的方式； 能够给出栈和队列为空的判断表达式； 数据操作题： 能够从空栈（队列）开始，按照给定入栈（队）和出栈（队）操作顺序，画出栈（队）的内容和栈顶（队首）和栈底（队尾）指针 第四章、串 选择题，填空题： 知道存储密度的概念，能够比较出顺序串和链串存储密度的大小； 能够求字符串长度，知道C语言转义字符的表达方式； 能够区分子串和子序列； 知道字符串比较大小的规则； 知道空串的定义，及其长度； 数据操作题： 能够计算KMP匹配算法中的next数组； 第五章、数组和广义表 选择题，填空题： 知道一般稀疏矩阵的紧缩存储方式有哪几种； 能够估算常见特殊类型（三角阵，对称阵）的稀疏矩阵，采用紧缩存储需要的空间； 知道行稀疏矩阵的链表存储方式的特点； 数据操作题： 能够对稀疏矩阵在三元组存储方式和二维数组直接存储方式直接相互转换； 第六章、树和二叉树 选择题，填空题： 知道满二叉树和完全二叉树的包含情况； 知道线索化二叉树的所能达到的效果； 知道树和二叉树有一一对应关系； 知道树的深度优先遍历，相当于如何访问树的结点； 能够对以下问题枚举并计数：给定树的结点数量，问有多少种不同的树； 能够对给定的二叉树的中序遍历和先序（或后序）遍历，还原出二叉树，然后求出后序（或先序）遍历顺序， 数据操作题： 掌握哈夫曼二叉树的构造过程，能够填其构造表； 第七章、图 选择题、填空题： 图论中已讲的有关图的基本概念不考； 知道图的几种存储方式，能够区分出不是图存储方式的其它数据结构； 知道广度优先有哪些信誉好的足球投注网站和队列的关系，知道深度优先有哪些信誉好的足球投注网站和栈的关系； 数据操作题： 能够对给定图按照Prim算法或者Kruskal算法求出最小生成树； 能够准确画出给定图的邻接矩阵； 对带权有向网络，能够给出图的一种拓扑排序；能够填表完成单源最短路径算法、能够求出关键路径； 第八章、动态存储管理 选择题、填空题： 知道空闲块的概念； 知道可利用空间表一般采用何种数据结构； 知道三种拟合方式在分配策及其对剩余空闲大小分布的影响；能够根据具体的内存申请块大小分布的特点，选择一种恰当的拟合方式； 知道回收空闲块时，满足什么条件的空闲块将被合并； 重点考察伙伴系统，能够根据某一块的位置和大小，得出它的伙伴的位置。能够根据申请的块的大小，估算出被选中空闲块分裂出的块数量和大小。 第九章、查找 选择题、填空题： 知道动态查找表的概念，能够区分出不是动态查找表的其它数据结构； 知道哈希表中，冲突的定义； 数据操作题： 能够按照给定的哈希函数、表空间大小、冲突解决办法，画出一组记录依次存入哈希表之后的状态；并能够准确求出平均查找长度； 第十章、排序 选择题、填空题： 知道“稳定的排序方法”的概念，能够分析出任何一种排序方法是否稳定的，或者能够强记住每种方法是否是稳定的； 知道每种排序方法排序的复杂度； 知道折半插入排序对直接插入排序在那一步上不同，效果如何； 知道排序算法的时间复杂度由哪两部分组成； 知道堆的概念，堆属于哪种二叉树？知道排序建堆和插入元素的复杂度； 知道基数排序的算法特点； 数据操作题： 能够对给定序列进行：希尔排序、快速排序、简单选择排序，注意题目要求做到哪一步！ 分值分布： 选择题20分； 填空题20分； 数据操作题40分；8个题； 程序填空题：10分，2个函数5个空； 编程题：10分 程序填空题完全采用教科书中的程序风格，有完整注释；考核以下算法中的两个算法： 有序链表合并； 有序顺序表合并； 普通求子串出现的位置；使用教科书中的SString数据类型； 使用递归完成图的深度优先遍历； 使用队列完成图的广度优先遍历； 折半插入排序； 希尔排序； 折半查找；