数据结构填空题
题源来自《算法与数据结构考研试题精析》、《王道数据结构》
在Liang’s Blog所著的文章上补充考点，仅供参考学习
一、概论
- 数据元素 是数据的基本单位，一个数据元素由若干 数据项 组成。
- 数据对象是 具有相同性质的数据元素 的集合，是数据的一个子集。
- 数据元素之间存在某种关系，这种数据元素相互之间的关系称为 结构
- 数据结构由数据的 逻辑结构 、 存储结构 和 数据的运算 三部分组成。
- 算法的设计取决于 逻辑结构，算法的实现取决于 存储结构。
- 逻辑结构 与数据的存储无关，是 独立于计算机的。
- 在数据结构中，数据的逻辑结构分 线性结构 和 非线性结构 。
- 存储结构，也称为物理结构，主要有 顺序存储 、 链式存储 、 索引存储 和 散列存储 。
- 用 抽象数据类型（ADT）定义一个完整的数据结构，其具备数据对象，数据关系和基本操作集。
- 链式存储的特点是利用 指针 来表示数据元之间的逻辑关系。
- 数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。
- 链式存储时，结点内的存储单元地址 一定连续。
- 对于给定的n个元素，可以构造出的逻辑结构有 集合 、 线性结构 、 树形结构 、 图结构 四种。
- 一个数据结构在计算机中的 表示 称为存储结构。
- 数据的逻辑结构是指 数据的组织形式，即数据元素之间逻辑关系的总体。
- 数据结构是研讨数据的 逻辑结构 和 物理结构 ，以及它们之间的相互关系，并对与这种结构定义相应的 操作 ,设计出相应的 算法 。
- 抽象数据类型的定义仅取决于它的一组 逻辑特性 ，而与 在计算机内部如若表示和实现 无关，即不论其内部结构如何变化，只要它的 数学特性 不变，都不影响其外部使用。
- 算法效率的度量是通过 时间复杂度 和 空间复杂度 来描述的。
- 算法是对 特定问题的求解步骤的一种描述 。
- 算法的五个特性： 有穷性 、 确定性 、 可行性 、 0或多个输入 、 1或多个输出 。
- 算法的时间复杂度 不仅依赖问题的规模n ， 也取决于待输入数据的初始状态 。
- 算法的时间复杂度 考虑在最坏情况下的时间复杂度，估算算法执行时间的一个上界。
- 算法的时间复杂度加法规则： O（max ( f(n) ，g(n) ) 。
- 算法的时间复杂度乘法规则： O（ f(n) * g(n) ) 。
- 算法的渐进时间复杂度口诀： 常对幂指阶 。
- 算法的时间复杂度为O(n^2)，表明 该算法的执行时间与n^2成正比 。
- 算法 原地工作指算法所需的辅助空间为常量O(1) ，而并非不需要辅助空间。
二、线性表
- 线性表是具有 相同数据类型 的n个 数据元素 的 有限序列 。
- 除表头元素外，每一个元素有且仅有一个直接前驱，除表尾元素外，每一个元素有且仅有一个直接后继。
- 线性表的顺序存储称为 顺序表 ，是用一组 地址连续的存储单元 依次存储。顺序表的特点是 表中元素的逻辑顺序与其物理顺序相同 。
- 线性表的顺序存储结构是一种 随机存取 的存储结构 ，用 数组 来描述线性表的顺序存储结构 。
- 顺序表最主要的特点是 随机访问 ， 即通过 首地址和元素序号（按序号查找）可在O(1) 内找到指定的元素 。
- 顺序表的 存储密度高 ，每个结点只存储 数据元素 。
- 顺序表 逻辑上相邻的元素物理上也相邻 ，所以 插入和删除操作需要移动大量的元素 。
- 顺序表 按序号查找为 O(1) ， 按值查找为 O(n) ， 插入操作为 O(n) ， 删除操作为 O(n) 。
- 顺序表所占的存储空间 = 表长 x sizeof( 元素的类型 ) ，元素的类型显然会影响存储空间的大小。 对于同一类型的顺序表，表越长，所占存储空间就越大。
- 顺序存储需要 连续的存储空间 ，动态申请空间时，在原有的 n 个空间追加了 m 个单位 。意味着 申请了 n + m 个连续的存储空间，然后将原来的 n 个元素复制到新申请的 n + m 个连续存储空间来 。
- 顺序存储结构是通过 结点物理上相邻 表示元素之间的关系的；链式存储结构是通过 结点指针 表示元素之间的关系的 ， 因此链式存储 插入和删除操作不需要移动元素，只需修改指针 。 但也因此 失去了可随机存取的优点 。 ——————————————————————————————————————————————————————————————
- 采用 头插法 建立单链表时，读入数据的顺序与生成的链表中的元素顺序是 相反 的 。 每个结点的插入时间为 O(1) ，设单链表长度为 n，则总时间为 O(n) 。
- 采用 尾插法 建立单链表时，读入数据的顺序与生成的链表中的元素顺序是 相同 的 。 每个结点的插入时间为 O(1) ，设单链表长度为 n，则总时间为 O(n) 。
- 单链表 按序号查找为 O(n) ， 按值查找为 O(n) 。
- 单链表插入操作和删除操作主要开销花费在查找 前驱结点，时间为 O(n) ，而插入结点与删除结点的时间为 O(1) ，总的来说总时间为 O(n) 。
- 双链表 可以很方便地找到前驱结点，因此插入和删除操作的时间为 O(1) 。
- 在单链表中设置头结点的作用是 有头结点后，方便运算的实现 ，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。
- 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 单链表 和 双链表 ；而又根据指针的连接方式，链表又可分成 链表 和 静态链表 。
- 链接存储的特点是利用 指针 来表示数据元素之间的逻辑关系。
- 单链表查找某个特定的结点时， 需要从 表头开始遍历 ，依次查找 。
- 循环单链表的最大优点是： 从任一结点出发都可访问到链表中每一个元素 。 ———————————————————————————————————————————————————————————————
- 指针p指向单链表的某个结点，在指针p所指结点之前插入s所指结点。操作序列： s->next=p->next;p->next=s 。
- 判断带头结点的双循环链表L仅有一个元素结点的条件是 L->next->next=L&&L->prior->prior==L&&L->next!=L 。
- 带头结点的循环单链表L为空表的条件是： L->next == L 。
- 带头结点的双循环链表L为空表的条件是： L->next==L&&L->prior=L 。
- 判断带头结点的单循环链表L仅有一个元素结点的条件是 L->next->next=L&& L->next!=L 。 ———————————————————————————————————————————————————————————————
- 静态链表借助 数组 来描述线性表的链式存储结构 ，静态链表也要预先分配 一块连续的内存空间 。
- 静态链表的指针 是下一元素结点的相对地址（数组下标） 。
- 静态链表以 next == -1 作为其结束的标志。 ———————————————————————————————————————————————————————————————
- 难以估计线性表的长度或存储规模时，不宜采用 顺序表 ；链式存储不用事先估计存储规模，但 链表的存储密度低，< 1 。
- 链式存储结构比顺序存储结构更能方便地表示各种逻辑结构 。
- 散列存储 通过散列函数映射到物理空间， 不能 反映数据之间的逻辑关系 。
三、栈和队列
- 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求 栈已存在 。
- 栈是 操作受限 的线性表，其运算遵循的原则 后进先出 。
- 堆栈是一种操作受限的线性表，它只能在线性表的 一端 进行插入和删除操作，对栈的访问是按照 后进先出 的原则进行的。
- 栈顶 ，线性表允许进行插入删除的一端。 栈底 ，固定的，不允许进行插入删除。
- 栈的数学性质：n 个不同的元素进栈，出栈元素不同排列的个数有 （1/(n+1)) * Cn-2n 。
- 栈的基本操作： 初始化栈 、判断栈是否为空 、进栈 、出栈 、读栈 、销毁栈 。
- 进栈操作 ，栈不满时， 栈顶指针先加 1 ，再送值到栈顶元素 。
- 出栈操作 ，栈非空时， 先取栈顶元素值，再将栈顶指针减 1 。
- 顺序栈S的GetTop(s,e)操作是用e返回s的栈顶元素。则操作正确的是 e = S.data[s.top]。
- 顺序栈用data[1..n]存储数据，栈顶指针是top，则值为x的元素入栈的操作是 if(top!=n) data[++top]=x;
- 判断顺序栈是否为空的条件是 s->top == -1 ；判断顺序栈是否为满的条件是 s.top == maxsize -1 ；栈长是 s.top + 1 。
- 共享栈 ：两个栈共享空间时栈满的条件 两栈顶指针相邻 。
- 共享栈 ：当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为 0 ，栈2空时，top[2]为 n+1 ，栈满时为 top[1]+1=top[2] 。
- 共享栈 ：为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的 栈底 分别设在内存空间的两端，这样只有当 两栈顶指针相邻 时才产生溢出。
- 共享栈 ：存取数据的时间复杂度为 O(1) 。
- 链栈 ：多个栈共享存储空间和提高其效率， 且不存在栈满上溢的情况 。
- 链栈 ：多个栈共存时，最好用 链式存储结构 作为存储结构。
- 链栈 ： 最大的优势在于它可以动态地分配存储空间 。
- 栈的应用 ：递归 、进制转换 、迷宫求解 、括号匹配 、存储调用函数，局部变量 。
- 栈在表达式求值的应用 ：先将表达式换成 后缀表达式 然后依次压入栈中，根据栈的特性进行求解。
- 递归模型必须满足两个条件： 递归体 、 递归出口 。
- 递归算法的效率往往低于非递归算法。
- 递归算法转换成非递归算法，通常需要借用到 栈 来实现这种转换。 ———————————————————————————————————————————————————————————————
- 队列只允许在表的一端插入，插入的一端叫 队尾，删除的一端叫 队头。
- 队列的特性是 先进先出 。
- 队列的基本操作 ： 初始化队列 、 判断队列是否为空 、 入队 、 出队 、 读队头元素 。
- 栈和队列是操作受限的线性表，因此不能随便操作，比如， 不可以随便读取栈或队列中间的某个数据 。
- 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。
- 循环队列是队列的一种 顺序 存储结构。
- 循环队列初始时， rear = front = 0 。
- 在循环队列中，队列长度为n，存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是 rear=(rear+1)%n 。
- 在循环队列中，队列长度为n，存储位置从0到n-1编号，以rear指示实际的队尾元素，要求当前循环队列的长度，则为 （ rear – front + n ）% n 。
- 已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是 front==(rear+1)%(n-m+1) 。
- 区分循环队列的满与空，只有两种方法，它们是 牺牲一个存储单元 和 设标记 。
- 链队是一个同时带有 队头指针 和 队尾指针 的单链表 。
- 链队为空的条件 ： Q.front == NuLL && Q.rear == NuLL 。
- 链队特别适合于 数据元素变动比较大的情形，而且不存在队列满且产生溢出 的问题 。
- 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是 new(s) ; s->data=x ; s->next = r->next ; r->next = s ; r = s ;
- 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 O(1) 和 O(n) ；若只设尾指针，则出队和入队的时间复杂度分别是 O(1) 和 O(1) 。
- 最适合做链队的链表要符合以下条件 ： 必须能直接或间接得到队首和队尾指针 。
- 双端队列 ：允许两端都可以进行入队和出队的操作 。
- 双端队列 ： 输出受限，指只有一个输出方向 ； 输入受限，指只有一个输入方向 。
- 双端队列 ：设有一个双端队列，输入序列为 1 ，2 ，3 ，4 ，试求出符合下列条件的输出序列
- 能由 输入（ ru – r ~ 2 ）受限的双端队列得到，但不能由输出受限的双端队列得到的是 ：4 ，1 ，3 ， 2 ( r )
- 能由 输出（ chu – C ~ 3 ）受限的双端队列得到，但不能由输入受限的双端队列得到的是 ：4 ，2 ，1 ， 3（ c ）
- 既不能由输入受限的双端队列得到， 又不能由输出受限的双端队列得到的是 ： 4 , 2 , 3 , 1 ( 死记这个就行，其它靠小心思记忆 )
- 队列的应用 ： 冲缓区 、 页面替换算法 、 层次遍历 – 图的广度优先搜索算法 。
四、树和二叉树
- 树是一种 递归 的数据结构。树作为一种 逻辑结构 ，同时也是一种 层次结构 。
- 树适合表示具有 层次结构 的数据，在 n 个结点的树中有 n-1 条边。
- 树的基本术语
- 祖先：根节点A是余下结点的祖先
- 子孙：余下结点是根节点A的子孙
- 孩子：结点K是结点E的左孩子，结点L是结点E的右孩子
- 双亲：结点E是结点K & L 的双亲
- 兄弟：结点K & L 是兄弟
- 堂兄弟：在同一层的结点互为堂兄弟，比如结点F & G & H 等是堂兄弟
- 结点的度：一个结点的孩子个数是结点的度，比如结点E的度为 2 ，因为它有两个孩子
- 树的度：树中结点的最大度数就是树的度
- 分支结点：度非 0 的结点
- 叶子结点：度为 0 的结点
- 结点的层次：从树根开始定义，根节点为第一层
- 结点的深度：从根节点开始 自顶向下 逐层累加
- 结点的高度：从叶子结点开始 自底向上 逐层累加
- 树的高度（深度）：树中结点的最大层数
- 有序树：结点的各子树从左到右都是有次序的，不能互换，否则为无序树
- 路径长度：两个结点之间的路径所构成的长度
- 森林：森林是 m（ m >= 0 ）棵互不相交的树的集合
- 树的性质：
- 树结点数 = 所有结点的度数 + 1
- 任意一棵树，结点数量为 n ，则边的数量为 n – 1
- 度为
m的树中，第k层上最多有m^(k-1) 个结点 （ k >=1 ) - 高度为
h的m叉树最多有 (m^h-1 ) / ( m – 1 ) 个结点 - 具有
n个结点的m叉树的最小高度为 logm( n ( m-1 ) + 1 ) ——————————————————————————————————————————————————————————————— - 二叉树每个结点最多只有两个孩子，且左右次序不能颠倒。
- 二叉树是 有序树 ，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
- 二叉树有 5 种基本形态： 空二叉树 、 只有根节点 、 只有左子树 、 只有右子树 、 左右子树都有 。
- 几种特殊的二叉树
- 满二叉树：除叶子结点外每个结点的度数均为 2
- 完全二叉树：
- 若 k
- 二叉排序树：左子树 < 根节点 < 右子树关键字的树
- 平衡二叉树：树上任一结点的左子树和右子树的深度之差
- 二叉树的性质：
- n0 = n2 + 1
- 结点总数 n = n0 + n1 + n2
- 非空二叉树上第 k 层上最多有
2^(k-1) 个结点 （ k >=1 ) - 高度为
h的二叉树最多有 (2^h – 1 ) 个结点 - 具有
n个结点的完全二叉树的高度为 log2（ n+1 ） - 完全二叉树结点有以下关系：
- 当 k > 1 时，结点 k 的双亲编号为 k / 2 ，即当 k 为偶数时，它是双亲的左孩子；当 k 为奇数时，其双亲编号为 ( k – 1 ) / 2，它是双亲的右孩子
- 当 2k
- 当 2k + 1
- 结点 k 所在的层次（深度） = log2k + 1
- 在二叉树中，指针p所指结点为叶子结点的条件是 p->lchild==null && p->rchlid=-null 。
- 深度为 H 的完全二叉树最少有 2^(H-1) 个结点；最多有 2^H-1 个结点；H和结点总数N之间的关系是 H=[log2N]+1 。
- 已知完全二又树的第8层（根结点的层次为0）有240个结点，则整个完全二叉树的叶子结点数是 248 。
- 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列 ( √ )
- 二叉树的顺序存储是用一组地址连续的存储单元 自上而下 、 自左而右 存储完全二叉树上的结点元素，存储结构从数组下标 1 开始存储。
- 完全二叉树和满二叉树采用 顺序存储 比较合适。
- 对于一般的二叉树，在最坏的情况下，一个高度为 h 且只有 h 个结点的单支树却需要占据近 2^h – 1 存储单元。
- 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么结点 i 没有右兄弟的条件为 2*i+1 > n 。
- 对于一个具有n个结点的二叉树，当它为一棵 完全 二叉树时具有最小高度，当它为一棵 只有一个叶子结点的二叉树 时，具有最大高度。 ———————————————————————————————————————————————————————————————
- 不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度为 O( n )
- 二叉树的定义是递归的，因此遍历算法也是用到递归，递归遍历中， 递归工作栈的深度 = 树的深度 。
- 三种遍历算法的求序过程：
- 根据图片指示进行排序即可分别得出先序、中序、后序序列
- 层次遍历需要借助一个 队列 。
- 二叉树的 先序序列 和 中序序列 可以唯一确定一棵二叉树。
- 二叉树的 后序序列 和 中序序列 可以唯一确定一棵二叉树。
- 二叉树的 层次序列 和 中序序列 可以唯一确定一棵二叉树。
- 先序遍历森林正好等同于按 先序 遍历对应的二叉树， 后序遍历 森林正好等同于按 中序 遍历对应的二叉树。
- 二又树的先序序列和中序序列相同的条件是 任何结点最多只有右子女的二叉树 。
- 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是 双亲的右子树中最左下的叶子结点 。
- 线索二元树的左线索指向其 前驱 ，右线索指向其 后继 。
- 在线索二叉树中，T所指左子树的充要条件是 T->ltag =0 ，右子树同理 T->Rtag =0 。 ———————————————————————————————————————————————————————————————
- 树在计算机内的表示方式有 双亲链表表示法 ， 孩子链表表示法 ， 孩子兄弟表示法 。
- 双亲表示法可以很快得到每个结点的 双亲结点 。
- 孩子表示法可以很快得到每个结点的 孩子个数 。
- 孩子兄弟表示法可以 实现树转换成二叉树的操作，易于查找结点的孩子 。
- 树转换成二叉树的规则 ： 左孩子右兄弟 ，由于根节点没有兄弟，所以对应的二叉树没有右子树
- 森林转换成二叉树的画法：将每一棵树转换成二叉树，然后接连其右子树串起来
- 树的遍历
- 先根遍历 = 树对应二叉树的先序遍历
- 后根遍历 = 树对应二叉树的中序遍历
- 森林的遍历
- 先序遍历 = 对应二叉树的先序遍历
- 中序遍历 = 对应二叉树的中序遍历 ———————————————————————————————————————————————————————————————
- 二叉排序树 ： 左子树结点值 < 根结点值 < 右结点值 。
- 对二叉排序树进行 中序遍历 ，将得到一个递增的有序序列 。
- 二叉排序树的查找从 根结点 开始，若关键字小于根结点值，则从左子树开始，否则从右子树开始，这很明显是 递归 的过程。
- 二叉排序树的查找效率，主要取决于 树的高度 。若二叉排序树是 平衡二叉树，那么它的平均查找长度为 O( log2n ) 。若二叉排序树是一个只有左（右）孩子的 单支树，则其平均查找长度为 O( n ) 。
- 二叉排序树的查找 并非唯一，相同关键字其插入的顺序不同可能会产生不同的二叉排序树 。
- 平均查找长度 ASL = （ 每层结点个数 * 层数 ） / 总结点数
- 当有序表是静态查找表时，宜用 顺序表 作为其存储结构，而采用 二分查找 实现其查找操作； 若有序表是动态查找表，则应选择 二叉排序树 作为其逻辑结构 ———————————————————————————————————————————————————————————————
- 平衡二叉树结点的平衡因子取值只可能为 1（左高 > 右高），0（左高 = 右高 + 叶子结点 ），-1 （左高 < 右高） 。
- 平衡二叉树的插入需要调整，有 LL( 右单旋转 ) 、RR( 左单旋转 ) 、LR( 先左后右双旋转 ) 、RL( 先右后左双旋转) ，具体调整规律需要依图王道P176页
- 含有 n 个结点的平衡二叉树的最大深度为 O( log2n ) ，因此平衡二叉树的平均查找长度为 O( log2n ) ———————————————————————————————————————————————————————————————
- 哈夫曼树是 所有叶结点的带权路径长度（WPL） 最小的二叉树，又称最优二叉树 。
- 哈夫曼树的构造：王道P180页
- 哈夫曼树的特点：
- 权值越小的结点到根结点的路径长度越大
- 构造过程中共 新建了 N – 1 个结点，因此哈夫曼树的总结点数为 2N – 1
- 每次构造都选择两棵树作为新结点的孩子，因此 哈夫曼树不存在度为 1 的结点
- 利用哈夫曼树可以设计出总长度最短的二进制前缀编码，具体王道P181页
- 哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。( F) 解析： 哈夫曼码的长度不是唯一的 ———————————————————————————————————————————————————————————————
- 中缀式 a+b 3+4（c-d）对应的前缀式为 ++a b3 4-cd ，若a=1，b=2，c=3，d=4 则后缀式 db/cc a-b+ 的运算结果是 18
- 在有 N 个元素的最大堆中，随机访问任意键值的操作可以在 O(logN) 时间完成。(F) 解析： 堆排序最坏情况为 n * log2n
五、图
- 线性表可以是空表，树可以是空树， 图不能是空图，最少也得留一个顶点
- 图的基本概念
- 有向图：有向弧< v，w > 的有限集合，称G为有向图
- 无向图：无向边（ v，w ）或 （ w，v ）的有限集合，称G为无向图
- 简单图：不存在顶点到自身的边 + 不存在重复边
- 多重图：与简单图的定义相对
- 完全图：
- 完全图是任意两个顶点之间存在 边 ；连通图是任意两个顶点之间都有 路径 。
- 对于无向图，e 的取值范围为 0 ~ n ( n-1 ) / 2，有 n ( n-1 ) / 2 条边的无向图称为无向完全图
- 对于有向图，e 的取值范围为 0 ~ n ( n-1 ) ，有 n ( n-1 ) 条弧的有向图称为有向完全图
- 子图：顾名思义
- 连通：无向图中，顶点 v 到顶点 w 有路径存在，则称为 v和w 是连通的
- 连通图：图G中任意两个顶点都是连通，都存在路径，则称为连通图，否则为非连通图
- 一个图有 n 个顶点，如果 e < n – 1，则此图为非连通图
- 连通分量：无向图中的极大连通子图称为连通分量
- 强连通：有向图中，有一对顶点 v 和 w，彼此之间都有路径，则称为强连通
-
强连通图：有向图中，任何一对顶点都是强连通的，则称为强连通图.
- 一个有向图中有 n 个顶点，如果是强连通图，那么最少需要 n 条边 ， 正好形成一个环
- 强连通分量：有向图中的极大强连通子图称为强连通分量
- 顶点的度：在无向图中，顶点 v 的度指顶点 v 边的条数。 无向图的 V 的度 = 2E
- 顶点的入度：有向图中，箭头指向顶点的弧，记作 ID(v)
- 顶点的出度：有向图中，箭头指向其它的弧，记作 OD(v)
- 对于有向图，顶点 v 的度 =ID(v) + OD(v)
- 对于具有 n 个顶点，e 条边的有向图，总 ID = 总OD = e
- 边的权和网：边上带有权值的图称为带权图（网）
- 稠密图：与稀疏图的定义相反
- 稀疏图：边数很少的图，当 e < V log V 时，可以看成稀疏图
- 距离：顶点 u 到顶点 v 的 最短路径称为 u 到 v 的距离
- 有向树：一个顶点入度为 0 ，其余顶点的入度均为 1 的有向图 ———————————————————————————————————————————————————————————————
- 若一个具有 n 个结点、e条边的无向图是一个森林，则该森林中必有 n-e 棵树。
- 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为 1 个。解析：已经确定是n个顶点的无向连通图了，所有只能有1个连通分量，即它本身
- 根据不同图的结构与算法，采用不同的存储方式。但都必须要准确地反映顶点集和边集的信息。
- 在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在 一对一 、 一对多 和 多对多 的联系。
- 如果具有n个顶点的图是一个环，则它有 n 棵生成树。解析：因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，所以共有n种情况
- 若无向图满足 n个顶点n-1条边的无向连通图 ，则该图是树。
- n个顶点的无向图的邻接矩阵至少有 0 个非零元素；n个顶点的有向图是强连通图至少有 n 条边。
- N个顶点的连通图用邻接矩阵表示时，该矩阵至少有 2(N-1) 个非零元素。
- 图的存储：
- 邻接矩阵法：有向、无向、网均适用， 适合稠密图，数组方式存储 （王道P206页）
- 定义：用二维数组存储图中边的信息，1和权值为边，0 和 ∞ 不是边
- 特点：
- 无向图的邻接矩阵是 对称矩阵，对规模较大的邻接矩阵可以采用压缩存储
- 邻接矩阵的 空间复杂度为 O( n^2 ) ，其中 n 为图的顶点数
- 无向图的邻接矩阵第 k 行（列）的非零或非∞个数正好是顶点的度TD( k )
- 有向图的邻接矩阵第 k 行 的非零或非∞个数正好是顶点的 出度 OD( k ) ；第 k 列 的非零或非∞个数正好是顶点的 入度 ID( k )
- 邻接矩阵很容易确定图中任意两个顶点之间是否有边相连，但是要确定有多少条边，则需要花费很长时间
- A^3【m】[n]表示从顶点 m 到顶点 n 长度为 3 的路径一共有 A^3【m】[n] 条
- 邻接表法：有向、无向均适用， 适合稀疏图，顺序+链式方式存储
- 定义：（王道P206页）
- 特点：
- 无向图算双重边，有向图算出边
- 若G为无向图，则需要 O( V + 2E )的存储空间，若G为有向图，则需要 O( V + E )的存储空间
- 用邻接表法存储稀疏图将极大节省空间
- 邻接表中，给定一个顶点，很容易找出其所有邻边，而在邻接矩阵中，则需要O( n )
- 有向图的邻接表，求一个顶点的出度只需计算其邻接表的结点个数
- 图的邻接表不是唯一的，因为链接次序可以是任意的
- 十字链表：有向适用，链式方式存储
- 定义：（王道P208页）
- 特点：
- 十字链表中，容易求出顶点的出度和入度
- 十字链表不是唯一的，但十字链表表示的图是唯一的
- 邻接多重表：无向适用，链式方式存储
- 定义：（王道P208页） ———————————————————————————————————————————————————————————————
- 树是一种特殊的图，树的遍历实际上也可以看作是一种特殊的图的遍历
- 图的遍历算法主要有两种： 广度优先搜索 和 深度优先搜索
- 广度优先搜索 = 二叉树中的层次遍历， Dijkstra单源最短路径算法和Prim最小生成树算法应用了类似的思想
- 图的遍历算法可以用来判断图的连通性
- 在 无向图 中，调用遍历函数(BFS 或 DFS)的次数为 连通分量的个数 。
- 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 队列 以存放被访问的结点以实现遍历。
- 邻接矩阵法的广度优先生成树及深度优先生成树唯一，邻接表法的不唯一。
- 遍历图的过程实质上是 查找顶点的邻接点的过程 ，breath-first search遍历图的时间复杂度 O(n+e) ；depth-first search遍历图的时间复杂度 O(n+e) ，两者不同之处在于 访问顶点的顺序不同 ，反映在数据结构上的差别是 队列和栈 。
- 图的遍历：
- 广度优先搜索
- 定义：广度优先搜索是一种 分层 的查找过程，不是一个 递归 的算法，为了实现逐层访问，需要借助 辅助队列 。
- BFS算法性能：
- 无论是邻接表还是邻接矩阵，n 个顶点均需入队一次，在最坏的情况下， 空间复杂度为 O( V )
- 采用 邻接表 存储时，每个顶点均需搜索一次，故时间复杂度为O( V )，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为 O( E )。算法的总时间复杂度为 O( V+E )
- 采用 邻接矩阵 存储时，查找每个顶点的邻接点所需的时间为O( V )，故算法的总时间复杂度为 O( V^2 )
- BFS算法应用：求解顶点 u 到顶点 v 的 最短路径，为从 u 到 v 的任何路径中 最少的边数。
- 广度优先生成树： 给定图的邻接矩阵存储是唯一的，所以广度优先生成树也是唯一的；由于邻接表的存储不是唯一的，故广度优先生成树也不是唯一的。
- 深度优先搜索
- 定义：相当于树的 先序遍历，可以采用 递归 的形式的算法，需要借助一个 递归工作栈
- DFS算法性能：
- DFS是采用 递归 的形式的算法，需要借助一个 递归工作栈，故其空间复杂度为 O( V )
- 采用 邻接表 存储时，查找所有顶点的邻接点所需时间为 O( E )，访问顶点所需的时间为 O( V )，故总的时间复杂度为 O( V+E )
- 采用 邻接矩阵 存储时，查找每个顶点的邻接点所需的时间为O( V )，故算法的总时间复杂度为 O( V^2 )
- 深度优先生成树：对 连通图 调用DFS才能产生 深度优先生成树，否则产生的将是深度优先生成森林。 ———————————————————————————————————————————————————————————————
- Prim算法求最小生成树的时间复杂度是 O(V^2) ，适用求解 边稠密的图 的最小生成树。
- Kruskal算法求最小生成树的时间复杂度是 O(E*logE) ,所以更适合用于 边稀疏而顶点多的图。
- AOV网中，结点表示 活动 ，边表示 活动间的优先关系 。AOE网中，结点表示 事件 ，边表示 活动 。
- 若AOE网中有几条关键路径，提高一条关键路径上的活动速度，能导致整个工程缩短工期。 ( × )
- 拓扑排序是按AOE网中每个结点事件的最早事件对结点的进行排序。 ( × )
- AOE网工程工期为关键活动上的权之和。( T )
- 在拓扑分类中，拓扑序列的最后一个顶点必定是的顶点 出度为0
- 拓扑排序的时间复杂度为 O( V + E )
- 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；若各个顶点已经排在一个有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
- 在AOV网中，存在环意味着 某项活动以自己为先决条件 ，这是 荒谬 的；对程序的数据流图来说，它表明存在 死循环 。
- 对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。
- 最小生成树不唯一。当带权无向连通图G 的各边权值不等时 或 G只有结点数减1条边时，最小生成树( MST ) 唯一。
- 无向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度均小于3，则图G最少有 11 个顶点 ，最多有 15 个顶点。 解析：无向图16条边，每条边有两个度，16*2=32，所以总度数为32。32 – 3 x 4 – 4 x 3 = 8度；剩余节点度均小于3，则最大为2 则节点是至少的，即8/2=4，则得到3 + 4 + 4 = 11个顶点。前面的3个度和4个度都是已知的，所以总体就是至少的。若剩余节点度小于3，则最小是1，则总体最大是3+4+8=15个顶点
- 已知一个图的邻接矩阵表示，删除所有从第 k 个结点出发的边的方法是 将第k行的元素全部置0
- 在有向图的邻接矩阵上，第 k 行中的非零且非无穷元素个数是第 k 个结点的 出度 。
- 在一个无向图的的邻接表中，若表结点的个数是m，则图中边的条数是 m/2 条。解析：无向图的邻接表每条边被记录2次
- 图的多重邻接表表示法中，表中结点的数目是图中边的边数。 (√)
- Dikstar算法是 按距离源点路径的长度小的次序产生一点到其余各定点最短路径的算法。
- 图的应用：
- 最小生成树
- 定义：无向有权图G 边的权值最小的那棵生成树 ，称为 最小生成树
- 性质：
- 最小生成树不是唯一的 ；
- 当图G中的 各边权值互不相等 时，G的 最小生成树是唯一 的 ；
- 若无向连通图G的 边数比顶点数少 1 ，即G本身是一棵树时，则G的 最小生成树就是它本身 ；
- 最小生成树的 边权值之和总是唯一的 ，而且是 最小的 ；
- 最小生成树的边数为 = 顶点数 – 1
- 构造算法：基于贪心算法策略
- Prim算法：初始时从图中任选一顶点，之后选择一个与当前顶点距离最近的顶点，如此反复（王道P227页）
- Prim算法的时间复杂度为 O( V^2 ) ，适用于求解 边稠密的图 的最小生成树
- Kruskal算法：按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，如此反复（王道P227页）
- Kruskal算法的时间复杂度为 O(E*logE) ，适用于求解 边稀疏而顶点多的图 的最小生成树
- Kruskal算法采用 堆 来存放边的集合，每次选择最小权值的边需要 O( logE ) 的时间
- 最短路径
- 定义：带权有向图的应用
- 问题分类：
- Dijkstra算法求解单源最短路径问题：求图中某一顶点到其它各顶点的最短路径（王道P229页）
- Dijkstra算法基于 贪心策略，时间复杂度为 O( V^2 )
- 边上带有 负权值 时，Dijkstra算法 不适用
- Floyd算法求解各顶点之间最短路径问题：求每对顶点间最短路径 （王道P230页）
- Floyd算法是一个 迭代 的过程，每迭代一次，从 vi 到 vj 的最短路径就多考虑一个顶点，经过多次迭代后，就保存了任意一对顶点之间最短路径长度
- Floyd算法时间复杂度为 O( V^3 )
- Floyd算法允许图中带有 负权值 的边，Floyd算法同样也适用于 带权无向图
- 拓扑排序
- 定义：无权有向图中，顶点表示活动，有向边表示活动的先后顺序，称为 AOV （王道P232页）
- AOV特点：
- 每个顶点出现且只出现一次
- 每个AOV网都有一个或多个拓扑排序序列
- AOV的拓扑排序算法：正排序思想 \ 逆排序思想
- 关键路径
- 定义：带权有向图中，顶点表示事件，有向边表示活动，边上 权值 表示完成活动的开销，称为 AOE （王道P233页）
- AOE特点：
- 只有所有路径上的活动都已完成，整个工程才能算结束
- 从源点到汇点路径上各个活动的时间总和 最长路径 称为 关键路径 ，而把关键路径上的活动称为 关键活动
- 关键活动 影响整个工程的时间，只要找到关键活动，就 找到了关键路径，也就可以得出最短完成时间
- 寻找关键活动的几个参量：ve( k ) \ vl( k ) ：———–未填补的知识遗漏点！！
- 关键路径注意点：
- 不能任意缩短关键活动，一旦缩短到某程度，该关键活动可能变成非关键活动
- 关键路径并不是唯一的，对于 有几条关键路径的网，只有加快那些 包括在所有关键路径上的关键活动 才能达到缩短工期的目的
六、查找
- 用于查找的数据集合称为 查找表 ，由 同一类型 的数据元素组成
- 静态查找表的操作有：查询某个特定元素是否在查找表中，检索满足条件的某个特定元素
- 动态查找表的操作有：具有静态查找表的操作，并且可以往查找表中插入或删除某个数据元素
- 适合静态查找表的查找方法： 顺序查找 、折半查找 、散列查找
- 适合动态查找表的查找方法： 二叉排序树的查找 、散列查找
- 平均查找长度 是衡量查找算法效率的主要指标 ———————————————————————————————————————————————————————————————
- 一般线性表顺序查找，查找成功的平均查找长度为 (n+1)/2 ，查找失败的平均查找长度为 n+1 。
- 有序线性表顺序查找，查找失败时不一定要遍历整个线性表，查找成功的平均查找长度也为 (n+1) / 2 ，但查找失败的平均查找长度为 n / 2 + n / (n+1)
- 顺序查找：又称线性查找，对 顺序表和链表 都是适用的
- 一般线性表的顺序查找
- 查找成功的平均查找长度： ( n+1 ) / 2
- 查找失败的平均查找长度： n + 1
- 特点：顺序查找的缺点是当 n 较大时，平均查找长度大，效率低
- 有序表的顺序查找
- 查找成功的平均查找长度： ( n+1 ) / 2
- 查找失败的平均查找长度： n / 2 + n / (n+1)
- 特点：查找成功的平均长度是一样的，而可以降低顺序查找失败的平均查找长度 ———————————————————————————————————————————————————————————————
- 折半查找：又称二分查找，仅适用于 有序的顺序表 （王道P260页）
- 折半查找可以用二叉树来表示，称为判定树， 判定树是一棵平衡二叉树
- 若有序序列有 n 个元素，则对应的判定树有 n 个圆形的非叶子结点和 n+1 个方形的叶子结点
- 查找成功的平均查找长度： log2 ( n+1 ) – 1
- 特点： 折半查找的时间复杂度 O( log2n )，平均情况下比顺序查找效率高，仅适用于 顺序存储结构，且元素是 有序的 ———————————————————————————————————————————————————————————————
- 采用分块查找时，数组的组织方式为数据分成若干块，每块内数据不必有序，但 块间必须有序，每块内 最大的数据组成索引块。
- 对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行 (16 ) 次关键字比较。 解析： 每个索引块大小为 (根号下65025) = 255 ，块间与块内均使用折半查找 log255+1 = 16次，比较次数=块间+块内。若使用顺序查找，则进行 255+1 = 256次。
- 分块查找：又称索引顺序查找，结合 顺序查找和折半查找的优点 （王道P261页）
- 定义：将查找表分成若干子块，块之间是有序的，用折半查找；而块内是无序的，用顺序查找
- 平均查找长度 = 块间索引查找平均长度 + 块内查找平均长度
- 将长度为 n 的查找表均匀分成 b 块，每块有 s 个记录，若在块内和块间 均采用顺序查找，则平均查找长度为： ( s^2 + 2s + n ) / 2s
- 若对快间采用折半查找，块内顺序查找，则平均查找长度为 log2( b + 1 ) + ( s + 1 ) / 2 ———————————————————————————————————————————————————————————————
- 散列法存储的思想是由关键字值决定数据的存储地址。 ( × )
- 在散列表中，评判一个散列函数优劣的两个主要条件是 计算简单 和 散列之后得到的元素分布均匀 。
- 散列函数：把查找表的关键字映射成该关键字对应的地址的函数，地址可以是数组下标，索引或内存地址
- 冲突：散列函数把两个或两个以上的关键字映射到同一地址，称为冲突，这种 冲突是不可避免的
- 散列表：根据关键字直接进行访问的数据结构，理想状态下， 对散列表进行查找的时间复杂度为 O( 1 )
- 散列函数构造方法：
- 直接定址法：直接取关键字的某个线性函数值为散列地址， 适合关键字分布基本连续的
- 除留余数法：散列表表长为 m，取一个 < m 但接近的 质数 k 。 H = key % k
- 数字分析法：适合已知的关键字集合，若更换了关键字则需要重新构造新的散列函数
- 平方取中法：适合关键字的每位取值都不够均匀或均小于散列地址所需的位数
- 处理冲突的方法：
- 开放定址法： 不能随便物理删除表中已有元素，要删除的话只能采用逻辑删除进行删除标记
- 线性探测法： 冲突发生时，顺序查看下一个单元，造成大量元素在相邻地址堆积起来，降低查找效率
- 平分探测法：可以避免堆积问题，缺点是不能探测到散列表上所有的单元，但至少能探测到一半
- 再散列法：在再散列法中，最多经过 m – 1 次探测就会遍历表中所有的位置，回到初始探测位置，m 是质数
- 伪随机序列法
- 拉链法： 采用链表结构，适用于 经常进行插入和删除 的情况
- 在散列（哈希）查找方法中，要解决两方面的问题，它们分别是 散列函数的选择 及 冲突的解决。
- 散列查找：
- 对同一组关键字，设定相同的散列函数，则不同的处理冲突方法得到的散列表不同，他们的平均查找长度也不同
- 散列表的查找效率取决三个因素：散列函数、处理冲突的方法、装填因子
- 装填因子 = 表中记录数 / 散列表长度， 装填因子越大，则发生冲突的可能性越大
- 平均查找长度 = 各关键字比较次数之和 / 关键字个数
七、排序
- 算法的稳定性：待排序表中有两个相同的关键字，且 A1 在 A2 前面。使用某一排序算法后，A1 仍在 A2 前面，则称这个排序算法是稳定的，否则不稳定
- 内部排序：指排序期间元素全部存放在内存中的排序
- 外部排序：指排序期间元素无法全部同时存在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序
- 排序算法进行两种操作：比较和移动
- 内部排序算法分为： 插入排序 、交换排序 、选择排序 、归并排序 、基数排序 五大类
- 插入排序：
- 直接插入排序 （王道P296页）
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率： 最好情况下，表中元素已经有序，只需比较而不用移动，为 O( n )；最坏情况下，完全逆序，总的比较次数和移动次数最大。 平均时间复杂度为 O ( n^2 )
- 稳定性：直接插入排序是个 稳定 的排序算法
- 适用性：适用于 顺序存储和链式存储 的线性表
- 折半插入排序 （王道P297页）
- 特点：比较次数与待排序表初始状态无关，仅取决于元素个数；而元素的移动次数没有改变，依赖于待排序表的初始状态
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率：时间复杂度为 O ( n^2 )
- 稳定性：折半插入排序是 稳定 的排序算法
- 适用性：对 数据量不是很大的有序顺序表 ，折半插入排序有很好的性能
- 希尔排序 （王道P298页）
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率：当 n 在某个特定范围时，希尔排序时间复杂度为 O( n^1.3 ) ；在 最坏的情况下希尔排序时间复杂度为 O( n^2 )
- 稳定性：希尔排序是 不稳定 的排序算法
- 适用性：仅适用于 线性表为顺序存储 的情况 ———————————————————————————————————————————————————————————————
- 交换排序：
- 冒泡排序 （王道P302页）
- 定义：每趟冒泡的结果是把序列中最小元素（或最大元素）放在序列的最终位置，这样最多做 n-1 趟冒泡就可以把所有元素排好
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率：最好的情况下时间复杂度为 O( n )；最坏的情况下 = 平均时间复杂度 O( n^2 )
- 补充：当初始序列有序时，比较次数为 n – 1，移动次数为 0 ，时间复杂度为 O( n ) ；当 初始序列为逆序时，需要进行 n – 1趟排序， 第 k 趟排序要进行 n – k 次关键字的比较，且 每次比较后要移动元素 3 次来交换位置，因此最坏的情况下时间复杂度 O( n^2 )
- 稳定性：冒泡排序是一种 稳定 的排序算法
- 快速排序 （王道P303页）
- 定义：快速排序基于 分治法 思想
- 空间效率：快速排序是 递归 的，借助一个 递归工作栈 ，其容量应与递归调用的最大深度一致， 最好情况下是 O( log2n )； 最坏情况下，要进行 n – 1 次递归调用，所以栈的深度为 O( n )；平均情况下，栈的深度为 O( log2n )
- 时间效率：最坏情况下时间复杂度为 O( n^2 )；最理想状态下，得到两个子问题的大小都不可能大于 n / 2，此时时间复杂度为 O( nlog2n )
- 补充： 快速排序运行时间与划分是否对称有关，初始排序表基本有序或逆序时，就是最坏的情况。有很多方法可以 提高算法效率，一种方法是 尽量选取一个可以将数据中分的枢轴元素，如 从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终枢轴元素；或 随机地从当前表中选取枢轴元素。
- 稳定性：快速排序是一种 不稳定 的排序算法
- 地位：快速排序是 所有内部排序算法中平均性能最优 的排序算法 ———————————————————————————————————————————————————————————————
- 选择排序：
- 简单选择排序 （王道P313页）
- 定义：每一趟排序可以确定一个元素的最终位置，经过 n – 1 趟排序就可以让排序表有序
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率：简单选择排序中， 最好情况下是移动 0 次，而最坏情况下移动次数也不会超过 3( n-1 ) 次； 元素间比较次数与序列的初始状态无关，始终是 n ( n-1 ) / 2 次，所以时间复杂度为 O( n^2 )
- 稳定性：简单选择排序是一种 不稳定 的排序算法
- 堆排序 （王道P314页）
- 定义：n 个关键字序列 L[ 1…n ] 称为堆，且满足 ① L( k ) >= L( 2k ) 且 L( k ) >= L( 2k+1 ) ② L( k ) ****
- 大根堆定义：满足①为大根堆，最大元素存放在根结点
- 小根堆定义：满足②为小根堆，最小元素存放在根节点
- 空间效率：使用了常数个辅助单元， 空间复杂度为 O( 1 )
- 时间效率： 建堆时间为 O( n ) ，而每次调整的时间复杂度为 O( h )，故 最好 = 最坏 = 平均时间复杂度为 O( nlog2n )
- 稳定性：堆排序是一种 不稳定 的排序算法
- 适用性：堆排序 适合关键字较多 的情况，比如在 1E个数中选出前100个最大值 ———————————————————————————————————————————————————————————————
- 归并排序：
- 2路归并排序 （王道P322页）
- 定义：2路归并排序算法是 递归 形式的，基于 分治 思想，整个归并排序需要进行 log2n 趟
- 空间效率：Merge( ) 操作中，需要辅助数组空间 n 个单元，因此 空间复杂度为 O( n )
- 时间效率： 每趟归并的时间复杂度为 O( n ) ，共需要 log2n 趟，所以总的时间复杂度为 O( nlog2n )
- 稳定性：2路归并排序是一种 稳定 的排序算法 ———————————————————————————————————————————————————————————————
- 基数排序： （王道P323页）
- 定义：不基于比较和移动进行排序，而基于各位 关键字 的大小进行排序，需要借助到 辅助队列
-
关键字排序方法：
- 最高位优先（MSD)：按关键字位权重递减依次逐层划分成若干更小的子序列
- 最低位优先（LSD）：按关键字位权重递增….
-
空间效率：一趟排序需要辅助空间为 r 个队列，所以空间复杂度为 O( r )
- 时间效率：需要进行 d 趟分配和手机，一趟分配需要 O( n ) ，一趟收集需要 O( r )，所以 总的时间复杂度为 O( d( n + r ) ) ，它 与初始序列状态无关
- 稳定性：基数排序是一种 稳定 的排序算法 ———————————————————————————————————————————————————————————————
- 各种内部排序算法比较
- 内部排序算法比较考虑三个因素： 时空复杂度 、算法的稳定性 、算法的过程特征
- 时间复杂度：
- O ( n ) ：直接插入排序最好情况 、冒泡排序最好情况
- O ( n^2 ) ：简单选择排序 、直接插入排序最坏 + 平均情况 、冒泡排序最坏 + 平均情况 、快速排序最坏 、希尔排序最坏
- O ( nlog2n ) ：快速排序最好 + 平均情况 、堆排序 、2路归并排序
- O ( d( n+ r ) ) ：基数排序
- 空间复杂度：
- O ( 1 )：简单选择排序 、直接插入排序 、希尔排序 、冒泡排序 、堆排序
- O ( log2n ) ：快速排序
- O ( n )：2路归并排序
- O ( r )： 基数排序
-
稳定性：
- 稳定：直接插入排序 、冒泡排序 、2路归并排序 、基数排序
- 不稳定：剩下的..
-
过程特征：
- 冒泡排序 和 堆排序 每趟处理后都能 产生当前的最大值或最小值
- 快速排序 一趟处理就能确定一个元素的 最终位置
- 内部排序算法的应用
- 若 n 较小，可采用 直接插入排序 或 简单选择排序 ，当 记录本身信息量较大 时，用 简单选择排序 避免移动多次元素
- 若 文件初始状态已按关键字基本有序 ，用 直接插入排序 或 冒泡排序
- 若 n 较大，则采用 时间复杂度为 O( nlog2n ) 的排序方法： 快速排序 、 堆排序 、 归并排序
- 快速排序 是目前基于比较的内部排序方法中最好的方法，当 关键字随机分布时， 快速排序平均时间最短
- 要求 排序稳定，且时间复杂度为 O ( nlog2n ) ，选用 归并排序
- 直接插入排序 与 归并排序 结合使用，先利用 直接插入排序求得较长的有序子文件，然后两两归并，最后改进的算法是 稳定 的
- 当 文件的 n 个关键字随机分布 时，任何借助于 比较 的排序算法，至少需要 O ( nlog2n ) 的时间
- 当 n 很大，记录的 关键字位数较少且可以分解 时，采用 基数排序
- 当 记录本身信息量较大 时，为避免耗费大量时间移动元素，可用 链表 作为存储结构 ———————————————————————————————————————————————————————————————
- 外部排序： （王道P335页）
- 外部排序概念：指排序期间元素无法全部同时存在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序
- 外部排序方法： 归并排序法
- 外部排序总时间 = 内部排序所需时间 + 外存信息读写时间 + 内部归并所需时间
- 补充1：外存信息读写时间 》内部排序时间 + 内部归并时间，因此应该着力减少 I/O次数
- 多路平衡归并
- 作用：增大归并路数，可以减少归并趟数，从而减少 I/O次数
- 缺点：增加归并路数 k，内部归并的时间也将增加，将抵消效益
- 败者树
- 作用： 增大归并路数 k，并且使得内部归并的比较次数与 k 无关
- 补充：归并路数 k 并不是越大越好，当 k 值过大，虽然归并趟数会减少，但读写外存的次数仍会增加
- 置换-选择排序（生成初始归并段）
- 作用： 增大归并段长度 从而 减少归并段个数
八、数组
- 对特殊矩阵压缩可以降低运算的复杂度。 (√)
- 稀疏矩阵一般的压缩存储方法主要有两种，即 三元组存储 和 十字链表 。
九、算法填空
1. 斐波那契数列递归与非递归实现
//递归实现
int Fib(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
//非递归实现
int Fib(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
int a = 0;
int b = 1;
for (int i = 1; i < n; i++){
int temp = a;
a = b;
b = temp + a;
}
return b;
}
2.树遍历算法
2.1 中序遍历非递归算法
void InOrder2(BiTree T){
InitStack(S);
BiTree p = T;
while(p ||!isEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,p);
visit(p);
p=p->rchild;
}
}
}
2.2 层次遍历
void levelOrder(BiTree T){
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!isEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild != NULL)
EnQueue(Q,P->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
3. 线索二叉树
3.1 线索二叉树结点结构
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild.*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
3.2 中序线索二叉树线索化
void InThread(ThreadTree &p,ThreadTree &pre){
if(p!=NULL){
InThread(p->lchild,pre);
if(p->lchild == NULL){
p->lchild = pre;
p->ltag = 1;
}
if(pre!=NULL && p->rchild == NULL){
p->rchild = p;
p->rtag = 1;
}
pre = p;
InThread(p->rchild,pre);
}
}
4. 折半查找
int Binary_Search(SeqList L, ElemType key){
int low = 0, high = L.TableLen-1,mid;
while(lowkey)
high = mid-1;
else
low = mid+1;
}
return -1;
}
5. 广度优先搜索
bool visited[MAX_TREE_SIZE];
void BFSTraverse(Graph G){
for(int i=0;i=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
visited[w];
visited[w] = TRUE;
EnQueue(Q,w);
}
}
}
5.1 无权图单源最短路径——广搜应用
void BFS_MIN_Distance(Graph G,int u){
for(int i=0;i=0;w=NextNeighbor(G,u,w))
if(!visit[w]){
visited[w] = TRUE;
d[w] = d[u] +1;
EnQueue(Q,w);
}
}
}
6. 深度优先搜索
bool visited[MAX_TREE_SIZE];
void DFSTraverse(Graph G){
for(int i=0;i=0; w=NextNeighbor(G,v,w))
if(!visited[w])
DFS(G,w);
}
7. 拓扑排序
bool TopologicalSort(Graph G){
InitStack(S);
for(int i=0; inextarc){
v = p->adjvex;
if(!(--indegree[v]))
Push(S,v);
}
}
if(count < G.vexnum)
return false;
else
return true;
}
8. 最小生成树
8.1 Prim算法——最小生成树
void MST_Prim(Graph G){
int min_weight[G.vexnum];
int adjvex[G.vexnum];
for(int i=0; i
8.2 Kruskal算法——最小生成树
typedef struct Edge{
int a,b;
int weight;
};
void MST_Kruskal(Graph G,Edge* edges,int* parent){
heap_sort(edges);
Initial(parent);
for(int i=0; i
9. 最短路径
9.1 Dijkstra算法——最短路径
void Dijkstra(Graph G,int v){
int s[G.vexnum];
int path[G.vexnum];
int dist[G.vexnum];
for(int i=0;i
9.2 Floyd算法——最短路径
void Floyd(Graph G){
int A[G.vexnum][G.vexnum];
for(int i=0;j A[i][k]+A[k][j])
A[i][j] = A[i][k] + A[k][j];
}
10. 大根堆的建立
void BuildMaxHeap(ElemType A[],int len){
for(int i=len/2; i>0 ;i--)
AdjustDown(A,i,len);
}
void AdjustDonw(ElemType A[],int k,int len){
A[0] = A[k];
for(int i=2*k;i1;i--){
Swap(A[i],A[1]);
AdjustDown(A,1,i-1);
}
}
Original: https://www.cnblogs.com/blog-cjz/p/16514829.html
Author: 陈景中
Title: 【填空题】考研数据结构填空题整理
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/606376/
转载文章受原作者版权保护。转载请注明原作者出处！