南京工程学院数据结构复习考纲

第1章 绪论
1.能简单的计算时间复杂度
第2章 线性表
2.掌握（单、双、循环）链表的插入、替换、连接、比较、创建空链表、是否相等操作的大致编程思路。能写代码
3.用链表实现的集合运算

第3章 字符串
4.掌握JAVA中字符串操作的基本方法，StringBuffer的主要成员函数的用法。
5.注意转义字符的用法，例如\”
6.熟练掌握KMP算法，能求解NEXT数组，匹配过程，子串匹配次数和字符比较次数
7.掌握Brute-Force匹配算法 P80-81

第4章 栈、队列和递归
8.栈和队列的存储规则
9.循环队列的存储规则（P107），注意front和rear这两个下标的变化规律，队列空和满的条件。

第5章数组和广义表
10.了解几种特殊矩阵的压缩存储矩阵，能画出它们的数组表示（P130图5-7图5-8）
11.稀疏矩阵的几种压缩存储方法，能够画出它们的几种链表结构，单链表P135，十字链表P141

第6章 二叉树和树
12.二叉树的广义表表示的写法（P164例6.2）
13.二叉树的性质：度为0的叶子结点个数总是比度为2结点多1个。
设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。
14.掌握树的父母孩子兄弟链表的简单实现思路。P172
15.掌握树的横向凹入表示法（P174）要求能看懂，会把它画成普通的树图
16.掌握树的层次遍历（P168图6-18），和队列中的数据变化，注意循环队列的存取规则
17.掌握在二叉树中查询、插入、删除子树（或子结点）的编程思路。能写代码
18.Huffman树和编码的方法（P180图6-34图6-36）。注意Huffman树中没有1度结点
19.遍历二叉树，能写出中根先根后根的遍历序列。
20.掌握用栈访问二叉树的方法。P166
21.根据先根和中根访问序列构造二叉树
22.根据标出空子树的二叉树先根遍历序列构造二叉树（P161）
23.能根据中缀表达式画表达式二叉树，写出前缀后缀表达式
24.计算完全二叉树的节点个数和层次（之间的关系）
25.表达式二叉树（P185）

第7章 图
26.连通图的概念，注意连通图中点和边的数量关系
27.掌握度的概念，有向图中出度和入度的概念，图中度数之和的计算方法
28.深度（P213）和广度（P216）优先遍历，能写出遍历的序列，栈和队列中的变化
29.图或者树中，两点间
30.Next（x,y）用来求x点的邻接点y的下一个临界点。如果没有下一个邻接点，返回值是-1
31.构造图的最小生成树，Prim算法（P219）和Kruskal算法（P222），能写出生成树结构，计算权值和（代价）
32.构造图的单源最短路径（Dijkstra算法P223），能画出某点(请注意是哪一个顶点)往其他所有点的最短路径。写出路径长度。

第8章 查找
33.二分查找法，能写出二分查找的比较数列
34.构造散列表（P249），已知一个数字序列和hash函数，画出链地址法的散列表，计算ASL
35.根据已知的数字序列构造二叉排序树（P253图8-15），计算出ASL

第9章排序
掌握插入排序、冒泡排序、直接选择排序的基本思路。
36.能写出快速排序（P281图9-7），归并排序（P286图9-12）的每趟的序列
37.希尔排序（P277图9-2）能画出每趟排序的图
38.构造最小堆（P284图9-10），能画对应的完全二叉树，把最小堆（完全二叉树）序列写出来。

希望同学们有一定的JAVA编码能力，能够简单分析算法执行效率
特别是第2章和第6章的编程题