数据结构考试资料——10信管
数据：描述客观事物的数字、字符、图像、语音等可以用符号表示，能输入到计算机内并被计算机处理的信息的总称。
数据元素：数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。
数据结构：是指同一类数据元素及个数据元素之间存在的关系，数据只有存储在计算机中才能被计算机处理，因此数据结构主要研究在计算机上数据的组织、存储以及基于数据的运算，我们称为数据的逻辑结构、数据的存储结构、数据运算。
数据的逻辑结构：是指对是要处理的数据经过抽象，提取一定特征后，从逻辑上进行描述并形成数据模型。它可以用数据元素的集合和数据元素之间若干关系进行表示。分为线性结构和非线性结构（集合、树形结构、图形结构）
数据的存储结构（物理结构）：逻辑结构和数据元素在计算机内存储方式或方法称为数据的存
储结构。数据的存储结构常见有顺序存储和链式存储。
数据类型：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称.
算法：对给定的待求解问题的一种处理方法或一个求解过程步骤的表述，是有限的指令系列。（一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列）
五个特征：有穷性，确定性，可行性，输入，输出。
时间复杂度：算法所有被执行的语句中，处于最深层循环内的语句被执行的次数。往往与问题的规模n有关，记作为T（n）
c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
顺序查：O（n） 二分查（折半查）：O（log2n） 分块查：log2(n/2+1)+s/2)
空间复杂度：执行算法所需要的辅助空间的大小定义为空间复杂度，也成为空间代价。
线性表：线性表是n(≥0)个数据元素的有限序列，记作（a1, a2, …, an）ai是表中数据元素，n是表长度。
线性表的顺序存储：是用一组地址连续的存储单元依次存储现行表的数据元素。顺序表就是现行表的顺序存储的实现。
顺序表：将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构。特点：逻辑上相邻的数据元素，其物理存储位置也是相邻的。
单链表：用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。每个结点只有一个链域的链表称为单链表。
循环链表：循环链表是单链表的变形。最后一个结点的 link 指针不为 NULL，而是指向了表的前端，使整个链表形成一个循环结构。
双向链表：双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。
静态链表：为数组中每一个元素附加一个链接指针，就形成静态链表结构。每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。
栈：限制为仅仅能在表的一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。特点：后进先出。
递归：若一个对象部分地包含它自己，或用它自己给自己定义,  则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
队列：队列是只允许在一端删除，在另一端插入的线性表。允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。
循环队列：队列存放数组被当作首尾相接的表处理。
串(字符串二叉树定义)：是由零个或多个字符构成的有限序列。
子串：串中任意个连续字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。
数组：是n(n>1)个相同类型的数组元素a1,a2,…an构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。
一维数组：数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标和值组成。
多维数组：多维数组是一维数组的推广。特点是每一个数据元素可以有多个直接前驱和多个直接后继。
特殊矩阵：特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
树：是由n(n>=0)个结点组成的有限集合。
分支结点：度不为0的结点即为分支结点，亦称为非终端结点。
叶结点：度为0的结点即为叶结点，亦称为终端结点。
结点的度：每个结点足有的子树数或者说后继结点数被定义为该节点的度。
树的度：所有结点的度的最大值为树的度。
二叉树的定义：二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。特点：每层上的结点数都是最大结点数。
完全二叉树 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。特点：所有的叶节点都出现在第k层或k-1层。对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次为i或i+1。
二叉树的顺序存储：所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。
哈夫曼树：最优二叉树，也称哈夫曼树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
图：图是由非空的顶点集合和一个描述顶点之间关系——边（或者弧）的集合组成，其形式化定义为： G＝（V，E）
无向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的
连线没有方向，则称该图为无向图。
有向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。
无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。
有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。
度：顶点的度（degree）是指依附于某顶点v的边数。
权：与边有关的数据信息称为权。网：带权的图称为网。
连通：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。
生成树:对于连通的无向图或者强连通的有向图，从任一定点出发，一次遍历能够访问到图中
所有的定点。遍历时经过的边加上所有的定点构成了图的一个连通子图，称为图的一棵生成树。
最小生成树：对于带权的连通图，其生成树也是带权的，把生成树各边的权值总和最小的生成树称为最小生成树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。