《数据结构》知识总结

知识点：

• 稀疏矩阵一般的压缩存储方式有两种，即 三元组 和 十字链表

• n的链队列用单循环链表表示,若只设头指针,则入队操作的时间复杂度为 O(n)

• n的链队列用单循环链表表示,若只设尾指针,则入队操作的时间复杂度为 O(1)

• 线性表中第一个结点没有 前驱 ，最后一个结点没有 后继

• 模式匹配成功的起始位置称为 有效位移

• 在n个结点的线索二叉链表中，有 n+1 个线索指针

• 线索二叉树的左线索指向其 前驱 ，右线索指向其 后继

• 对于二维或多维数，分为按 行 优先顺序存储和 列 优先顺序存储两种不同的存储方式

• 一个算法的时间复杂性是算法 问题规模 的函数

• 向一个循环队列中插入元素时，首先要判断队列是否已 满 ，然后再向指针所指的位置写入新的数据。

• 数据的基本单位是 数据项

• 某线性表最常用的操作是存取任一指定序号的元素和在表后进行插入和删除运算，则利用 顺序表 存储方式最节省时间

• 循环队列占用的空间 必须连续

• 现有一棵结点总数 20的二叉树,它含有4个度为2的结点,由此可知其叶子结点数为 5

• 树的后根遍历类似于二叉树的 中序遍历

• 当广义表中的每个元素都是原子时，广义表便成了 线性表

• 设广义表 L=(a,(a,b),d,e,((i,j),k))，则L的长度是 5

• 静态查找和动态查找的区别是 施加在其上的基本操作不同

• A+B/C-D*E的后缀表达式是 A B C / + D E * –

• 无向图的顶点度数最小值大于等于 2 时，该图至少有一条回路

• 在发生非法操作时，算法能够做出适当的处理的特性是 健壮性

• 在长度为n的顺序表中删除的第i(1≤i≤n)位置上的元素，元素的移动次数为 n-i

• 在长度为n的顺序表的第i(1≤i≤n+1)位置上插入一个元素,元素的移动次数为 n-i+1

• 在具有n个单元的顺序循环队列中，假定font和rear分别为队首指针和队尾指针，则判定队空的条件是 front=rear

• 一个循环队列一旦说明，其占用空间的大小 已固定

• 设二维数组 A[1…m][1…n](即m行n列)按行存储在数组 B[1…m*n]中，则二位数组元素 A[i][j]在一维数组 B中的下标为 (i-1)*n+j

• 森林的中序遍历类似于二叉树的 中序遍历

• 不带头结点的链栈 LS 为空的条件是 其栈顶指针为NULL

• 若 LS 是带头结点的链栈，指向栈顶元素的指针是 头结点的下一个节点的指针

• G是一个非连通无向图，共有28条边，则该图至少有 9 个顶点

• 已知表达式，求它的后缀表达式是 二叉树遍历 的典型应用

• 如果从一个顶点出发又回到该顶点，则此路径叫做 回路

• 由3个结点可以构造出 5 种不同形态的二叉树

• 对于一个具有n个顶点e条边的有向图的邻接的表示，则表头向量大小为 n ，邻接表的边结点个数为 e 。

判断：

• 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 ✗

• 将十进制数转换为二进制数是栈的典型应用之一。 ✓

• 从逻辑结构上看,n维数组的每个元素均属于n个向量。 ✓

• 串的堆分配存储是一种动态存储结构。 ✓

• 稀疏矩阵的压缩存储可以用一个三元组表来示矩阵中的非0元素。 ✓

• 串是n个字符的有限序列。 ✓

• 树有有序树和无序树之分。 ✓

• 具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵大小是n*n。 ✓

• 数据的存储结构是数据的逻辑结构的存储映像。 ✓

• 在循环链队列中无溢出现象。 ✗ （无假溢出是对的）

• 树中结点的度指的是和该结点相连的分支的数目。 ✓

• 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。 ✓

• 串的数据元素是一个字符。 ✓

• 链表(link-rink)存储包含n个结点的二叉树时，结点的2n个指针区域中有 n+1个空指针。 ✓

• 有e条边的无向图，在邻接表中有e个结点。 ✗

• 数据的逻辑结构与数据元素本身的内容和形式无关。 ✓

• 十字链表是无向图的一种存储结构。 ✗

• 强连通分量是有问图的强连通子图。 ✓

• 链队列与循环队列相比，前者不会发生溢出。 ✓

• 在中序线索二叉树中，每一非空的线索均指向其祖先节点。 ✗

• 在n个结点的无向图中，若要求在任意情况下都是连通的，则边数至少是n(n-1)/2。 ✗ (1+(n-1)*(n-2)/2)