名词解析

1、逻辑结构和存储结构

• 逻辑结构：指的是数据元素之间的相互关系和组织方式，描述数据元素之间如何连接、关联。常见的逻辑结构有线性结构（如数组、链表）、树形结构（如二叉树）、图形结构等。
• 存储结构：指的是数据在计算机内存中具体的存储方式，是实现逻辑结构的具体方式。常见的存储结构有顺序存储（如数组）、链式存储（如链表）等。

2、稳定的排序方法和不稳定的排序方法

• 稳定的排序方法：在排序过程中，相等的元素在排序后相对位置不变。例如，冒泡排序、插入排序、归并排序。
• 不稳定的排序方法：在排序过程中，相等的元素在排序后相对位置可能发生改变。例如，快速排序、选择排序、堆排序。

3.完全二叉树

• 完全二叉树：是一种特殊的二叉树，除了最底层外，其余每一层的节点数都达到最大，并且最底层的节点从左到右排列。完全二叉树的节点编号是按照从上到下、从左到右的顺序编号的。

4.什么是关键路径？什么是关键活动？

• 关键路径：在项目管理中，关键路径是指从项目开始到项目结束的所有任务所组成的路径，这条路径上的每个任务都不能延误，否则整个项目的完成时间将延长。关键路径上的活动即为关键活动。
• 关键活动：指在项目中，任何延误都将直接影响项目总工期的活动。它们位于关键路径上，是项目中最重要的活动。

5.什么是前缀编码？哈夫曼编码为什么是前缀编码？

• 前缀编码：是一种编码方式，任何一个编码都不是另一个编码的前缀。即没有任何一个编码是另一个编码的开头部分。常见的前缀编码有哈夫曼编码。
• 哈夫曼编码是前缀编码：因为在哈夫曼编码中，编码的构造保证了任何一个字符的编码都不可能是另一个字符编码的前缀，因此满足前缀编码的性质。哈夫曼编码通过使用变长的编码，使得频繁出现的字符用短的编码表示，而不常见的字符用长的编码表示，从而提高了编码效率。\

6.什么是数据结构？常见的数据结构类型有哪些？

• 数据结构：是计算机中存储、组织数据的方式，它定义了数据元素之间的关系以及存取数据的方法。数据结构是实现算法的基础，它影响程序的执行效率和资源使用。
• 常见的数据结构类型:
  1. 线性数据结构：如数组、链表、栈、队列。
  2. 树形数据结构：如二叉树、AVL树、红黑树、B树、堆。
  3. 图形数据结构：如无向图、有向图、加权图、邻接矩阵、邻接表。
  4. 哈希表：通过哈希函数实现高效的查找和插入。
  5. 集合与映射：如集合、字典、集合运算等。

其他基础名词

1. 线性表：由若干数据元素构成的集合，其中的元素之间存在一对一的关系。常见的线性表有数组、链表、栈、队列等。
2. 栈：一种线性数据结构，遵循后进先出（LIFO）原则，只有一个端口可以插入和删除元素。
3. 队列：一种线性数据结构，遵循先进先出（FIFO）原则，元素从队尾插入，从队头删除。
4. 数组：一种线性数据结构，通过连续的内存单元存储相同类型的数据元素，可以通过索引进行访问。
5. 链表：一种线性数据结构，元素通过指针连接，每个元素包含数据和指向下一个元素的指针。
6. 双向链表：一种链表结构，除了每个元素指向下一个元素的指针外，还包含指向前一个元素的指针。
7. 树：由若干个节点组成的非线性数据结构，节点之间有父子关系。
8. 二叉树：每个节点最多有两个子节点的树。
9. 二叉搜索树：一种特殊的二叉树，左子树的值小于根节点的值，右子树的值大于根节点的值。
10. 平衡二叉树：一种特殊的二叉树，**任何节点的左右子树的高度差不超过1。**时间复杂度为 O(log n)
11. 哈希表：通过哈希函数将键值映射到一个位置，常用于实现高效的查找、插入操作。
12. 图：由顶点和边组成的数据结构，边表示顶点之间的关系。
13. 邻接矩阵：一种表示图的方式，使用二维数组表示顶点之间的连接关系。
14. 邻接表：另一种表示图的方式，使用链表或动态数组表示每个顶点的邻接节点。
15. 深度优先搜索（DFS）：一种图的遍历方法，优先访问深层节点，直到没有未访问的邻接节点时返回。
16. 广度优先搜索（BFS）：一种图的遍历方法，优先访问浅层节点，逐层遍历图的节点。
17. 递归：一种函数调用自身的编程方式，通常用于解决可以分解为更小规模相同问题的任务。
18. 动态数组：一种数组类型，具有可变大小的特性，支持动态扩展
19. 堆：一种完全二叉树结构，用于实现优先队列。最大堆或最小堆根据优先级决定元素的排列。
20. 动态规划：一种将复杂问题分解成小问题，解决小问题并存储其解，最后合成大问题解的算法设计方法。
21. 迭代：通过循环结构逐步逼近目标结果的方法，适用于不需要递归的场景。
22. 队列（Queue）：一种先进先出（FIFO）的线性数据结构，支持从队尾插入，从队头删除。
23. 并查集：一种用于处理不相交集合合并和查询的问题的数据结构。支持两种操作：查找（判断两个元素是否属于同一集合）和 合并（将两个集合合并成一个）。
    • 路径压缩：优化查找操作，减少树的高度。
    • 按秩合并：优化合并操作，避免形成过高的树
24. 哈希冲突：当两个不同的键值通过哈希函数映射到相同的位置时，称为哈希冲突。常见的解决方法有链式法和开放地址法。
    • 链式法：使用链表来解决冲突，多个元素可以存储在同一个位置。
    • 开放地址法：当发生冲突时，寻找下一个空闲位置进行插入。
25. 红黑树：一种自平衡的二叉搜索树，具有更多的约束条件，能够保证最坏情况下的 O(log n) 查找、插入和删除操作。
26. 时间复杂度：衡量算法执行时间随输入规模变化的增长率。常用的时间复杂度有 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 等。
27. 空间复杂度：衡量算法所需空间随输入规模变化的增长率
28. 最小生成树
    • Prim算法：从一个点开始逐步加入最小的边，直到包含所有点。
    • Kruskal算法：从最小的边开始逐步加入，不形成环，直到生成树完整。
29. 常见排序算法：
    • 冒泡排序：O(n^2)
    • 选择排序：O(n^2)
    • 插入排序：O(n^2)
    • 归并排序：O(n log n)
    • 快速排序：O(n log n)（平均）
    • 堆排序：O(n log n)
30. 图的存储方式
    • 邻接矩阵：适用于稠密图。
    • 邻接表：适用于稀疏图。
31. 线索二叉树是对二叉树的一个改进，用来避免在遍历时使用栈或递归，使用线索指针替代空指针。

图片展示

简答

队列计算

队列的长度

1

length=(r-f+m)%m

队满的条件

1

(r+1)%m == f

队列不满的时候入队

1

r=(r+1)%m

队空的条件

1

f == r

队列不为空时出队

1

f = (f+1)%m

• r 是队尾指针
• f 是队头指针
• m 是队列的最大容量

广义表计算

广义表的表长是指广义表中直接包含的元素个数，而这些元素可以是原子（如 a、b）或者子表。注意是直接包含

例：

1

LS = (a, b, c), (d, e, f)

上面LS的表长即为2

广义表的提取：

下面

1

head(tail(tail(head(LS))))

即结果为元素c

就是先分析里面的，然后一层一层的套，最后只剩下一个了得head取出

例如：

取出元素e

1

head(tail(head(tail(LS)))) = e

树的计算

对于完全二叉树来说，n为总节点树，[x]为向上取整

叶子节点的数量L

1

L=[n/2]

对于完全二叉树，除了最后一层外，其他层的结点都是满的，所以大部分叶子结点都在最后一层或倒数第二层。

树的深度：

是指从根结点到最深叶子结点的路径长度，对于完全二叉树则深度d为

1

d=⌈log2(n)⌉

完全二叉树的深度为 d，则结点数 n 满足：
$$
2^{d-1} \leq n \leq 2^d - 1
$$

• 一个完全二叉树的最小结点数发生在只有根节点的情况下，深度为 dd 的完全二叉树的最小结点数是 2d−12d−1。
• 完全二叉树的最大结点数是满二叉树的结点数，即 2d−12d−1。

非叶子结点的个数可以通过以下公式计算：

$$
N_{non-leaf} = n - L
$$

图的计算

完全图的边和顶点的关系，假设m条边和n个顶点，图的边数为
$$
m= n(n−1)/2
$$
非连通无向图考虑至少顶点数的情况下，该图由两个子图构成，一个是完全图一个是只有一个顶点，所以如果边数为28的话，最后至少9个顶点。

那我们接下来来考虑至多的情况

对于非连通无向图，最多顶点数的情况是图中每个连通分量都为一个孤立的顶点，即每个顶点都没有边。但是题目限定了28条边，那我们就每个连通分量都拥有尽可能少的边数，也就是两个顶点一条边。边数为28的话，那么顶点数就是56。所以至多顶点数为56

时间复杂度分析

1
2
3
4
5

x = 0;
for(i = l; i < n; i++)
  for(j = l; j <= n - i; j++)
    x++;

时间复杂度为O(n^2)

1
2
3
4
5

i = -l;
for(j = l; j <= n; j++)
  while(i <= n)
    i = i * 2;

时间复杂度为O(n \log n)

在简单for循环中时间复杂度可以为

1

外层时间复杂度*内层时间复杂度

数组计算

1、设有一个二维数组 A[m][n]按行优先顺序存储，假设 A[0][0]存放位置在
644(10)，A[2][2]存放位置在 676(10)，每个元素占一个字节的空间，问 A[3]3
存放在什么位置？脚注(10)表示用 10 进制表示。

元素 A[i][j]A[i][j] 的存储地址可以通过以下公式计算：
$$
地址(A[i][j])=地址(A[0][0])+(i×n+j)
$$

• i 是行号，
• jj 是列号，
• nn 是数组的列数，
• 地址(A[0][0])地址(A[0][0]) 是数组的起始位置。

这样解出n=15然后获得a33的位置

查找算法

折半查找

在折半查找中，判定树是根据每次比较将序列分为两部分来进行的

假设我们有一个长度为 12 的序列，元素的下标从 1 到 12。

• 初始查找范围：整个序列，长度为 12，范围是从 1 到 12。

• 选择中间的元素。中间元素的下标是 (1 + 12) / 2 = 6，所以在第一次比较时，根结点的值是序列中的第 6 个元素。

• 如果要找的值比根结点的值小，查找范围变为 1 到 5。

• 如果要找的值比根结点的值大，查找范围变为 7 到 12。

• 如果查找范围是 7 到 12，那么新的中间元素下标为 (7 + 12) / 2 = 9。此时，根结点的右孩子的值对应的是序列中的第 9 个元素。

在折半查找中，若得到的中间元素位置是小数，则需要向下取整。

孩子节点就是子节点