数据结构重点知识梳理

"该文档是关于数据结构的复习资料，包含选择题和应用题，涉及数据结构的基础概念，如链表、树、图、排序算法等。" 在数据结构的学习中，以下是一些重要的知识点： 1. 双重循环：在给定的代码段中，可以看到一个双重循环，其时间复杂度为O(n(n+1))/2，因此正确答案是D。这种结构通常用于计算组合数量、矩阵乘法或填充某种数组。 2. 线性链表特性：线性链表的优点在于插入和删除操作不需要移动元素，但无法实现随机访问，选项A描述的是线性链表的缺点。 3. 链表操作：在单链表中插入节点，正确做法是首先将新节点`s`的`next`指向当前节点`p`的下一个节点，然后更新`p`的`next`指向`s`。因此，正确答案是C。 4. 树的度和性质：在树的度数问题中，公式为n0 = n2 + 1，其中n0是终端结点（叶子结点）的数量，n2是度为2的结点数量。给定的度数分别为1、2、3、4，根据这个公式，正确答案是B。 5. 图的深度优先搜索（DFS）：从顶点1开始的DFS遍历可能会产生多种序列，但题目给出的选项中，只有A选项符合DFS的特点，从起点出发，沿着边向下探索。 6. 拓扑排序：拓扑排序只能应用于无环有向图（DAG），因此正确答案是C。有环图无法进行拓扑排序。 7. 二分查找：二分查找要求线性表以顺序方式存储，并且元素按关键字有序排列，所以正确答案是C。 8. 关键路径：在事件结点图中，关键路径是从源点到汇点的最长路径，因为它决定了项目的最短完成时间。 9. 堆排序与筛选法：筛选法建堆过程中，会形成小顶堆，即父节点的键值不大于其子节点。给定的关键码序列经过筛选后，会形成小顶堆B。 10. 排序算法效率：在平均时间复杂度方面，最差的情况通常是直接选择排序，因为其平均时间复杂度为O(n^2)，而其他选项的平均时间复杂度通常优于O(n^2)。 此外，题目还涉及到栈的操作（元素的入栈和出栈顺序）以及二叉树的遍历。前序遍历（根左右）为ABECDFGHIJ，中序遍历（左根右）为EBCDAFHIGJ，可以用来重构二叉树的形状。