《数据结构》-数据结构复习提纲（08级）

数据结构复习提纲第一章绪论11数据结构1什么是数据结构包括哪三方面的内容2什么是数据类型12算法及其描述1算法具有哪5个特性2算法描述有哪些方式13算法分析1能分析小程序段的时间复杂度（如练习题15，16）2时间复杂度TNOFN的含义是什么3各种不同数量级的时间复杂度的增长率比较（P15）第二章线性表21线性表及其逻辑结构1线性表的定义2线性表有哪些基本运算22线性表的顺序存储结构1清楚顺序表的类型定义SQLIST2顺序表的各种基本算法。3算法（例23，例24，练习题22）23线性表的链式存储结构1清楚单链表的类型定义LINKLIST2单链表的各种基本算法3算法（例25，例26，例211，练习题23）4清楚双链表的类型定义DLINKLIST5双链表的算法（其各种基本算法，例27）6循环链表的算法（例29，例210）第三章栈和队列31栈1什么是栈栈的特点是什么栈有哪些基本运算2栈的顺序存储结构SQSTACK,其基本运算的算法。3栈的链式存储结构（不考）4练习题32，例34，例3532队列1什么是队列队列的特点是什么队列有哪些基本运算2队列的顺序存储结构的定义SQQUEUE。3循环顺序队列的判断空队列和满队列的条件各是什么如何求队列长度4循环顺序队列的基本算法。如入队列算法ENQUEUE，出队列算法DEQUEUE，等，习题345队列的链式存储（不考）第四章串41串的基本概念1串的定义。2串有哪10种基本运算42串的存储结构1清楚顺序串的定义SQSTRING2顺序串的基本算法STRASSIGN,STRCPY,STREQUAL，CONCAT，DISPSTR的实现。43串的模式匹配1简单匹配（BF）算法（INDEX）的实现，其匹配过程。2KMP算法的NEXT函数的计算，NEXTVAL函数的计算，匹配过程（不要求算法本身）（看例46）练习题4的433练习题42,例41。第五章数组和广义表51数组1对称矩阵的压缩存储方法，注意地址的变换公式。2上三角矩阵的压缩存储方法、下三角矩阵的压缩存储方法，注意地址的变换公式。3习题5252稀疏矩阵1清楚矩阵的三元组顺序表的类型定义TSMATRIX,TUPNODE2三元组表的算法（二维数组创建三元组表的算法，矩阵转置算法，习题56）3十字链表不考53广义表1广义表的定义2HEAD,TAIL的计算（习题57）3清楚广义表结点类型的定义GLNODE,能画出广义表的链式存储结构4广义表的运算求广义表的长度，求广义表的深度算法第六章递归61什么是递归1了解递归的概念2递归函数的定义及执行结果如N的递归函数，FIBONACCI数列的递归函数，HONOI塔问题的递归函数（如HANOI3,A,B,C的执行所显示的结果）63递归算法的设计1递归算法（如例62，例63，习题61，习题62）第七章树和二叉树71树的基本概念2树的定义、基本术语。3树的4个性质。例724树的先根、后根遍历（能写出遍历结果）5算法例7372二叉树概念和性质1二叉树的定义2二叉树的5个性质。例743画出二叉树与森林（或树）之间的转换（例75例76）73二叉树存储结构1清楚二叉树的链式存储结构BTNODE74二叉树的基本运算及其实现1查找结点，找孩子结点，求高度，输出二叉树的算法75二叉树的遍历1二叉树的先序，中序、后序遍历得到的结果2二叉树的先序，中序、后序遍历的递归算法3二叉树的先序、中序遍历的非递归算法（P169，P171）4层次遍历算法（P174）5算法例78（求叶子结点数，可扩展成求结点总数，度为2的结点数等的算法），例79，例710，习题7876二叉树的构造1给定二叉树的先序、中序遍历序列，构造二叉树（图715的例子）；给定二叉树的后序、中序遍历序列，构造二叉树（图717的例子）；（如习题72），不考算法。77线索二叉树（不考）78哈夫曼树1给定字符的权值，构造哈夫曼树（习题73），写出各个字符的哈夫曼编码，并计算WPL，不考算法。第八章图81图的基本概念1知道图的各种基本术语。82图的存储结构1清楚邻接矩阵的存储方法，知道其类型定义MGRAPH2清楚邻接表的存储方法，知道其类型定义ALGRAPH,VNODE,ARCNODE3能画出邻接矩阵（如图85），邻接表（如图86）4算法例8283图的遍历1深度优先搜索遍历算法DFS（P204）2广度优先搜索遍历算法BFS（P205）3与图遍历有关的算法。如例83，例84，习题81，习题82。84生成树和最小生成树1能按PRIM算法画出最小生成树的过程（如图814）。2能按KRUSKAL算法画出最小生成树的过程（如图815）。85最短路径1写出DIJKSTRA算法求最短路径的过程（如P219例），不考算法本身。2写出FLOYD算法求所有顶点对的最短路径的过程（如P224例，矩阵A和矩阵PATH的变化过程），不考算法本身3实验题82，83，85，86，87，88，8986拓扑排序（不考）第九章查找91查找的基本概念1什么是动态查找表什么是静态查找表2平均查找长度ASL的定义92线性表的查找1顺序查找算法SEQSEARCH及其ASL2二分查找算法BINSEARCH3能画出二分查找的判定树（如图91），计算ASL例91，习题914分块查找不考93树表的查找1二叉排序树的定义2能画出二叉排序树,计算ASL（如习题92）3二叉排序树的算法。如插入算法INSERTBST，查找算法（习题94，P246的SEARCHBST，例94）4二叉排序树的结点删除（画出过程，如图98，不考算法）5能画出平衡二叉树（AVL树）的生成过程,计算ASL（例95，习题93）6能画出平衡二叉树（AVL树）的删除过程（例96）7B树（不考）94哈希表查找1构造哈希表（例99，实验题98（1）（不用编程，只须画出哈希表）,并计算其ASLSUCC（P270）和ASLUNSUCCP271第十章内排序101排序的基本概念102插入排序1直接插入排序算法INSERTSORT2写出直接插入排序过程（例101）3希尔排序过程103交换排序1冒泡排序算法BUBBLESORT2快速排序法的递归算法QUICKSORT3写出排序的过程（例103，例104，实验题104的过程）104选择排序1直接选择排序算法SELECTSORT以及过程（例105）2堆的定义。3能构造大根堆（图1011的AB）4堆排序算法（包括SIFT和HEAPSORT）5堆排序的过程（例106）105归并排序1写出归并排序法的排序过程（例107的图1013）,不考算法106基数排序（不考）107