数据结构期末复习资料.docx

数据结构期末复习资料

第一篇：数据结构期末复习资料《数据结构》课程复习资料第一章：数据结构概述1、掌握数据结构的定义，即数据结构三要素：数据的逻辑结构、存储结构、操作；2、数据结构包括：逻辑结构和存储结构；3、数据之间的关系：表（一对一之间的关系）、树（一对多之间的关系）、图（多对多之间的关系）；4、算法的定义：算法衡量的标准：时间复杂度和空间复杂度；5、算法时间复杂度的求法：给定一段程序，求其时间复杂度；时间复杂度的比较；6、为什么学习“数据结构”？“数据结构”课程主要学了哪些知识？第二章：线性表1、线性表按照存储结构不同分为顺序表、链式表；顺序表的特点：逻辑上相邻的两个元素在物理上也相邻；链式表的特点：逻辑上相邻的两个元素在物理上未必相邻；（“未必”的含义是可相邻也可以不相邻）2、比较线性表顺序存储和链式存储的优缺点。第三章：栈和队列1、栈和队列的特点：栈：后进先出，队列：先进先出2、熟悉栈和队列的基本操作：初始化栈、入栈操作、出栈操作、判断栈是否为空、取栈顶元素等。3、根据实例，能够容易的判断出是栈的应用还是队列的应用？4、重点掌握栈的应用：进制转换算法的思想或程序。第四章：数组1、牢记对称矩阵、三角矩阵、对角矩阵的特点，掌握矩阵中的元素Aij与一维数组SA[K]的对应关系。2、掌握稀疏矩阵的三元组表示法。第五章：串1、掌握上课介绍的9种函数名称及其实现结果；第六章：树1、二叉树的5个性质；2、二叉树前序、中序和后序遍历，根据2种遍历结果求第3种遍历结果。3、完全二叉树、满二叉树、哈弗曼树的定义；4、给定一组叶子权值，求带权路径长度最小的多少？第七章：图1、掌握图的术语：无向完全图、有向完全图、顶点的度等；2、图的深度优先遍历和广度优先遍历；3、图的邻接矩阵存储，给定一个图，求出邻接矩阵；或者给定一个邻接矩阵，构造图；4、图的最小生成树；第八章：查找1、查找的定义：静态查找和动态查找2、折半查找算法的思想；第九章：排序1、掌握排序的分类：插入排序、交换排序、选择排序；2、重点掌握希尔排序、快速排序、简单选择排序；第二篇：数据结构复习资料数据结构复习资料模块一：计算题一.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。二叉树自画！二．试列出如下图中全部可能的拓扑排序序列。123456解：全部可能的拓扑排序序列为：152364、152634、156234、561234、516234、512634、512364三．已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度以及查找因子。解：哈希表及查找各关键字要比较的次数如下所示：ASL=1(4×1+1×2+1×4+2×5)=2.58a=8/9四．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。解：五．设有序列：w={23,24,27,80,28}，试给出哈夫曼树；哈夫曼树如下图所示：六：已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。七．（本题8分）对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。解：用Kruskal算法构造最小生成树的过程如下图所示：八．给出一组关键字29、18、25、47、58、12、51、10，写出归并排序方法进行排序时的变化过程。解：(l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58)九．三、（本题8分）请画出如下图所示的邻接表。解：邻接表如下图所示：***45454∧∧∧∧5∧十．判断以下序列是否是小根堆?如果不是，将它调整为小根堆。（1）{12,70,33,65,24,56,48,92,86,33}（2）{05,23,20,28,40,38,29,61,35,76,47,100}解：（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70}（2）是小根堆。十一．设有如下图所示的AOE网（其中vi（i=l，2，…，6）