数据结构复习资料

数据结构是计算机科学中的核心概念，它涉及到如何高效地组织和操作数据。这份复习资料涵盖了数据结构的基础知识，包括各种数据结构的定义、操作以及它们的时间复杂度分析。以下是其中的一些关键知识点： 1. 数据的存储结构主要有顺序结构、链式结构、索引结构和散列结构四种类型。顺序结构如数组，直接通过下标访问元素；链式结构通过指针连接节点；索引结构通过额外的索引表找到数据；散列结构则通过哈希函数快速定位数据。 2. 时间复杂度是衡量算法效率的重要指标，大 O 表示法用于描述算法运行时间的增长速度。例如，给定的代码片段是一个简单的循环，时间复杂度为 O(n)，因为循环执行了 n/2 次。 3. 队列是一种先进先出（FIFO）的数据结构，类似于现实生活中的排队等待。 4. 线性表的顺序存储结构通常采用顺序访问和随机访问。顺序访问按照元素在内存中的顺序逐个访问，而随机访问则可以直接跳转到指定位置。 5. 完全二叉树的叶子节点数量与总节点数有特定关系，对于有 n 个结点的完全二叉树，其叶子结点数量可以通过公式 n/2 向上取整来计算。 6. 删除顺序表中的第 i 个元素，需要将后面的元素向前移动 i-1 个位置。 7. 数组的地址计算通常基于起始地址和元素大小，若以行序为主序顺序存储，a[3,5]的地址为 100 + (3-1)*20*4 + (5-1)*4。 8. 排序方法的稳定性指的是排序后相等的元素原有的相对顺序不变。 9. 折半查找中，查找 10 会依次与 25、10 进行比较。 10. 数据的存储结构主要包括顺序结构、链式结构、索引结构和散列结构。 11. 表达式求值是编译器和解释器应用中的典型例子。 12. 循环累加的程序段时间复杂度为 O(n)。 13. 空串不含任何字符，而空格串包含一个或多个空格。 14. 单链表使用指针链接相邻节点，实现逻辑关系。 15. 在树结构中，子孙结点是指除子节点外，所有下级节点。 16. 连通图中，最少的边数是 n-1，保证任意两个顶点间都有路径可达。 17. 有三个结点的二叉树形态包括左-右子树、右-左子树、只有一个左子树、只有一个右子树、没有子树五种。 18. 排序稳定性的含义是相同元素的相对顺序在排序后保持不变。 19. 稠密图采用邻接矩阵存储较省空间，因为它记录了所有可能的边。 20. 删除顺序表中第 i 个元素时，需向前移动 n-i 个元素。 21. 以列序为主序顺序存储的数组，a[6,16]的地址为 100 + (6-1)*20*4 + (16-1)*4。 22. 二分查找的平均查找长度与结点个数 n 无关。 23. 数据的逻辑结构包括线性结构、树形结构和图状结构。 24. 表达式求值也是编译器和解释器应用的典型实例。 25. 此循环的时间复杂度为 O(n)。 26. 空串不包含任何字符，而空格串至少包含一个空格。 27. 单链表用指针来表示节点间的逻辑关系。 28. 树的度是树中最大分支数，即一个节点的最大孩子数。 29. 交换排序如冒泡排序和快速排序，都涉及元素的交换操作。 30. 无向图的最大边数为 n*(n-1)/2，因为每对不同的顶点之间最多有一条边。 31. 深度为 7 的完全二叉树至少有 2^1 + 2^2 + ... + 2^7 - 1 = 127 个结点。 32. 图的存储方式主要有邻接矩阵和邻接表。 以上内容仅是数据结构复习资料中的一部分，实际学习过程中还需要深入理解每个概念，并通过实践加深对数据结构操作的理解。