《2022年数据结构考试要 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考试要 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章：数据结构包含：逻辑结构，数据的存储结构，对数据进行的操作。数据元素：相对独立的基本单位，即可简单也可复杂，简单的数据元素只有一个数据项，数据项是数据的不可分割的最小单位。数据对象：性质相同的数据元素的集合。数据结构：相互存在一种或者多种特定关系的数据元素的集合（集合，线性结构，树结构，图结构）。顺序存储结构：数据元素按照逻辑顺序依次存放在存储器的一段连续存储单元中。链式存储结构：存储在存储空间的任意位置上，包含一个数据域和至少一个指针域，要访问，必须从第一个元素开始查找。数据类型：一组值加一组操作。第二章：线性表：有限多个性质相同的数据元素构成的一个序列，数据元素的个数就是长度。线性表
2、的顺序存储结构：用一组地址连续的存储单元能随机存取的结构。 链式存储结构：具有链式存储结构的线性表称为链表，是用一组地址任意的存储单元来存线性表中的数据元素。每个数据元素存储结构包括数据元素信息域和地址域，存放一个数据元素的存储结构称为结点，每个结点只定义一个指针域，存放的是当前结点的直接后记结点的地址（直接后继结点），线性表的最后一个结点指针域存放空（0，NULL）标志结束。不支持随机存取，访问必须从第一个结点开始，一次访问。双向链表：每个结点设置两个方向的指针（直接前驱和直接后继）。第三章：栈：堆栈的简称，限定在表尾进行插入和删除的线性表。特点是后进先出。当栈定指针指向栈底时，为空栈。队列
3、：限定只能在一端进行插入和在另一端进行删除的线性表，进行插入的是队尾，删除的是队头。特点是先进先出。队列的链式结构：用一个链表依次存放从队头到队尾的所有的数据元素。存放队头地址（队头指针）队尾地址（队尾指针），空链队列：有头结点，空队列条件是头结点存放0，无头结点为队头指针指向空。队列的顺序存储结构： 用一组地址连续的存储空间依次存放从队头到队尾的所有数据元素，再用队头指针和队尾指针记录队头和队尾的位置。队头指针指向队头元素前一个数组元素的位置，队尾始终指向队尾，当队尾和队头指向同一位置，空队列。入队和出队，队尾指针都会向数组元素下标的增加方向移动，当队尾指针超出数组上界面无法进行操作（假溢出
4、），解决方法是使用具有顺存储存结构的循环队列：将存放队列元素的数组首尾连接，形成一个环形结构。第四章：数组的存储结构：一般为顺序存储结构，依次将数组元素存放在一段连续的存储区域中。通常有两种存放方式：1.以行序为主， 2.列序为主。矩阵的压缩存储：对值相同的元素可以自分配一个存储空间，0 不分配。对称的压缩存储：对于每一个位置对称的矩阵元素只分配一个存储单元。稀疏矩阵：若一个矩阵存在大量的0，就称为稀疏矩阵。稀疏矩阵的三元组表示若以顺序储存结构表示由非零元三元组构成的表，则得到稀疏矩阵的一种压缩储存方式，三元组表。稀疏矩阵的十字链表表示：链式表，每一个结点除了表示存储非零元素的三元组以外，还设
5、置两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元素结点。第五章：串：空串的长度为0，空格串的字符为空格。串的顺序存储结构（串的主要存储结构）：将字符串的所有字符依次存放在一段连续的存储单元中。非紧缩存储（访问方便）：以存储单元为单位依次存放所有字符。紧缩存储（节省空间）：根据机器字的长度尽可能的将多个字符存放在一个字中。静态数组： 0 表示串终结。动态数组：用new 和 delete 动态分配空间和释放空间。串的链式存储结构：用一个线性表来一次存储串值。第六章：广义表：在线性表中，每个数据元素都是结构上不能分割的原子元素，如果放宽这个限制，允许表中的数据元素既可以是数据元素
6、又可以是原子元素， 也可以是一个表， 这种数据结构就是广义表。子表： 某个元素本身是表。 广义表的长度： 最外层元素的个数。空表： 没有元素。 广义表的表尾：将第一个元素除去之后剩下全部元素构成的表，广义表的表尾一定是广义表。层：（a,(b,(c,e)）a 和(b,(c,e)第一层， b 和(c,e)第二层。广义表的深度：广义表的最大层数，其值与广义表书写形势中括号的最大嵌套层数相同。第七章：树 : 树是由 n（n=0）个结点组成的有限集，若n=0，则为空树， n0,则树满足：有且仅有一个根节点；其他的结点划分为m 个互不相交的有限集，每个有限集本身是一棵树，称为根的子树。基本术语：结点：存放
7、数据元素的逻辑单元。分支：节点之间的二元关系。结点的度：结点拥有的子树棵数。叶子的结点：度为0 的结点。分支的结点：度不为0 的结点。树的度：树内各结点度的最大值。结点的层次：根为第一层，对其他任何结点，若其父亲是k 层结点，它就是K+1层。树的深度 (高度 )：树中结点的最大层次。有序数：任意一个结点的各棵子树从左到右是有序的，其次序不能任意颠倒。森林：m 棵互不相交树的集合。二叉树的定义：一种度小于或等于2 的有序树。特点是树的每一个结点最多有两棵子树，且子树有左右之分，不能任意颠倒。满二叉树：一棵二叉树所有的结点都有非空的左子树和右子树，且所有的叶子结点都位于二叉树的最下面一层。完全二叉
8、树：只有最下面两层结点的度可以小于2，且最下面一层的结点都集中在该层最左边的位置上。二叉树的性质：1.第 i 层上最多有2 的 i-1 次方个结点。 2.深度为k的二叉树最多有2 的 k 次方减 1 个结点。 3.若叶子结点数为n,度为 2 的节点数为 m,则 n=m+1.具有 n 个结点的完全二叉树的深度为log 以 2 为底， n 的对数再加上1.二叉树的顺序存储结构：将一棵完全二叉树的全部结点按层次从上到下，每层从左到右， 依次存放在一组地址连续的存储单元中。对于一般的二叉树，可以增加一些不存在的虚节点变成二叉树。链式存储结构：二叉树一般采用链式存储方式存放，每一个树结点对应一个链结点，
9、每个链结点除了存放数据元素以外，还要根据需要定义若干指针，分别存放当前结点的左孩子，右孩子，双亲结点地址。定义lchild 和 rchild 指针指向当前结点的左右孩子，称为二叉链表，再定义一个parent,称为三叉链表。二叉树的遍历：按照某种搜索方式，访问二叉树中的每个结点，且每个结点只访问一次。访问还可以修改结点额的值，输出结点的内容。遍历方式：先序，中序，后序。先序遍历二叉树：若二叉树为空，则空操作；否则访问根结点，先序遍历根结点的左子树，先序变了根结点的右子树。中序遍历二叉树：若, 中序遍历根节点的左子树，访问根结点，中序遍历根节点的右子树。后序遍历二叉树：若 , 后序遍历根结点的左子
10、树，后序遍历根结点的右子树，访问根结点。树的存储结构：孩子兄弟表示法：每个树结点构成了链表中的一个链结点，每个链结点设置了三个域，一个是数据域，还有两个指针域，分别表示当前结点第一个孩子的地址和下一个兄弟的地址。任何一棵树，可以找到一棵唯一的二叉树，他们的存储结构完全相同。树，森林与二叉树的转换：任何一棵二叉树可以找到一棵唯一对应的二叉树，他们的存储结构完全相同， 只是解释不同。 树的根结点对应着二叉树的根结点，树上某结点的第一个孩子对应二叉树的上是相同的结点的左孩子，树上的某结点的下一个兄弟结点在对应二叉树上是用同结点的右孩子。任何一棵与树对应的二叉树，其根结点的右子树必然是空树。哈夫曼树：
11、路径长度：从一个结点向下到达某子孙结点的分支，成称为这两个结点之间的路径，分支的数目称为路径长度。结点的权：赋予给结点的一个数值。结点的带权路径长度：从树根到该结点的路径长度与结点权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。现在有N 个数值，将他们作为n 结点的权，以这n个结点为叶子结点构造一个二叉树，其中带权路径长度最短的那颗二叉树为哈夫曼树（最优二叉树）。要使二叉树的带权路径长度达到最小，权值大的叶子结点尽量离根近些。第八章： 图是由若干个顶点和若干条边构成的数据结构。顶点是实际对象的抽象，边是对象之间的关系的抽象。有向图：若图中带表一条边的偶对是有序的，则图中的边具有
12、方向性，可以将其称为又向边（弧），常将顶点x 到顶点 y 的弧表示为 ，其中顶点x 称为弧尾， y 为弧头。完全图：任名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 意两个边之间都有边存在，n 个顶点，一共有n(n-1)/2 条边。有向完全图：对于任意两个顶点，既有x 到 y 的弧，又有y 到 x 的图。 n 个顶点，一共有n(n-1)条边。度：与顶点相关联的边的数目或者弧的数目称为度，对于有向图，氛围出度和入度，入度与出度之和
13、就是这个顶点的度。网：图中的边或者弧带有数值，称为权，边或弧上带权的图称为网。路径上弧的度数称为路径长度。连通和强连通：图中任意两个顶点之间是连通的，是连通图。无向图的极大连通子图称为原图的连通分量。对于连通图，只有一个连通分量。在有向图中，任意两个顶点之间存在相互连连通的路径就为强连通图。对于强连通图就只有一个强连通分量。图的存储结构：图是一种网状结构，图中的顶点之间不存在先后顺序关系，任何一个顶点都可以看成是第一个顶点。数组表示法： 用两个数组来存放图，用一个一维数组存放图的所有顶点，用一个二维数组存放图中的全部边或者弧，存放图中边或弧的二维数组称为邻接矩阵。邻接矩阵的特征：无向图的邻接矩
14、阵是对称矩阵，有向图的是非对称矩阵。无向图，其邻接矩阵第i 行（列）非零元素的个数正好是第i 个顶点的度。对于有向图，其邻接矩阵第i 行非零元素的个数正好是第i 顶点的出度，而第i 列非零元素的个数正好是第i 个顶点的入度。邻接表：图的一种链式存储结构。 邻接表中的结点由图的边（弧）和顶点构成。 十字链表： 用于储存有向图。 十字链表的结点由图的弧和顶点组成。对于由弧构成的结点。需要定于5 个域，由顶点构成的结点只需要定义3 个域。多重邻接点：只用于无向图的一种链式存储结构。图的遍历：从图中的任意指定顶点出发，按照某种访问原则依次访问图中的所有顶点，且每个顶点只访问一次。为了避免重复访问，需要
15、对访问过的顶点做标记，方法是“访问标记数组”的辅助数组。深度优先遍历：从图中某个指定的顶点v 开始，优先访问v，然后依次从v 的尚未访问的邻接点出发深度优先遍历，直到所有的顶点都被访问到。广度优先遍历：先访问 V,再依次访问v 的各个尚未被访问的邻接点，然后从这些邻接点出发，按照相同的原则访问它们的尚未被访问的邻接点。要使用一个队列来存放被访问过的顶点，依次访问它未被访问的邻接点，知道队列变为空为止。第九章：查找（检索，搜索）：指在数据元素集合中寻找满足某些指定条件的数据元素。经常进行的查找操作：1.查询特定的数据元素是否存在2.查找结构中某个特定数据元素的一个或者多个属性。3.删除查找到的数
16、据元素。4.插入不存在的数据元素。查找一般是根据数据元素的关键字进行查找，关键字分为主关键字和次关键字。主关键字可以唯一标识一个数据元素，次关键字可以标识一组数据元素，所有的数据元素都具有相同的次关键字。根据查找时是否所有的元素都存在内存，分为内查找和外查找；是否增删元素， 分为静态查找和动态查找；是否进行关键字比较分为比较式查找和非比较式查找。按照查找结构中数据元素之间的关系，可以讲查找结构分为：1.线性索引结构2.树形结构 3.散列结构。使用查找指定元素需要进行关键字比较的次数的数学期望作为衡量算法效率高低的标准，并将它称为平均查找长度。线性表的查找： 顺序存储结构， 数据元素无序， 按照
17、顺序搜索方式进行查找；而数据元素按照关键字有序，就进行高效的折半查找等；对于链式存储结构，只能进行顺序查找。顺序查找：最简单的方法，从一端开始，依据元素的待查字和关键字进行比较，相等则成功，未找到就失败。顺序查找既可用于顺序表，又可以用于链表。顺序表查找可从前往后或者从后往前。链表只能从前往后。折半查找：线性表是顺序存储结构，数据元素按关键字有序。思想：先知道有序表中点位置的元素，用待查值K与之比较，若k 大于中点元素，则下一步是有序表的后半部分按类似的方法进行查找，反之亦然。折半查找查找成功时进行的关键字比较次数最多是log 以 2 为底 n 的对数再加上1.线性索引结构：为了加快索引速度，
18、为数据元素集建立一个或多个引索。一个引索由若干个索引构成。索引分为稠密索引（每一个数据元素在索引中都有一个索引项）和稀疏索引（每一组数据元素在索引中都有一个索引项）。索引项组织成线性表，称为线性索引或者索引表，该索引项一般按关键字有序。线性稠密索引：数据集中的每个元素在索引中有一个索引项，若稠密索引组建成一个按关键字有序的线性表，就称为线性稠密索引。分块索引：减少索引项的数目，若数据集具有分块有序的特征，以数据元素为单位为建立分块索引。分块有序是指，虽然整个数据元素师无序的，但可以将它划分为若干个大小不等的数据块；虽然数据块中的数据元素任然是无序的，但第二个数据块中的所有数据元素的关键字均大于
19、（小于）第一个数据块正的最大（最小的）关键字，以此类推。查找的过程：1.再索引表中查找，确定待查关键字所在数据块2.在数据块中查找关键字。二叉排序树：属于树形索引结构。在树形索引结构中，树的每一个结点都是一个索引项。又称为二叉查找树或者是空树或者是包含关键字。特点是1.左子树不空，则左子树上所有的关键字均小于它的根结点的关键字2.右子树不空，则 , 大于, 。3.它的左右子树也是二叉排序树。平衡二叉树（AVL 树） ：或者是一棵空树，或者具有以下性质：一、根结点的左右子树的高度只差绝对值不超过1.二、根结点的左右子树都是平衡二叉树。B 树：是一种平衡的多路查找树，常用于文件索引。 B 树的特征： 1.树中的每个结点最多有m 棵子树 2.若根不是叶子结点，则最少有两棵子树3.除根结点以外，其他非终端结点至少有m/2 棵子树。关键字的个数比叶子结点少1. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -