2020数据结构题库回顾：树形、队列、图论基础

本题库包含了数据结构相关的基础概念和练习题，主要涉及树形结构、队列与栈、线性表、二叉树、逻辑结构、时间复杂度、图论、搜索算法以及特定数据结构的操作。以下是部分知识点的详细解析： 1. **树形结构特点**： 树形结构的特点之一是每个节点最多有一个父节点（选项D错误），即树是分层次的，非终端节点（内节点）只有一个后继（子节点）。选项A描述了树的正常情况，但题目要求指出不具备的特点，因此选择B，每个节点可能有多个前驱（父节点）并不符合树形结构的一般定义。 2. **顺序队列特性**： 在顺序队列中，元素的排列顺序是由它们的插入顺序决定的，与元素值大小、队首指针和队尾指针取值无关，也与数组大小无关，因此答案是A。 3. **线性关系的数据结构**： 选项A栈和B队列都属于线性结构，因为它们遵循先进先出（FIFO）或后进先出（LIFO）的规则，而线性表是一种更为一般的概念，包括栈和队列，所以正确答案是D，以上都是。 4. **二叉树的共同点**： 二叉树和度数为2的树不同之处在于，二叉树允许每个节点最多有两个子节点（选项A），而选项C提到的至少有一个度数为2的节点是二叉树的特性之一，但不是它们的共同点。因此，正确答案是B，至少有一个根节点。 5. **逻辑结构**： 逻辑结构关注数据元素之间的关系，而非具体的实现方式。A顺序表和C有序表反映了元素的线性顺序关系，属于逻辑结构，而B哈希表和D单链表虽然也是常见的数据结构，但哈希表不是基于线性关系组织的，所以答案是AC。 6. **循环嵌套for循环的时间复杂度**： 题目中的双重for循环执行了n * n次操作，因此总的时间复杂度是O(n^2)，选择C。 7. **无向图顶点数量**： 对于无向图的28条边，由于非连通图可能存在多个独立的子图，要达到最少的顶点数，应假设这些边分布在两个最大独立集之间，每增加一个顶点可以连接两个已有的顶点，所以至少需要8个顶点，选择C。 8. **二分查找比较次数**： 对于有序表，二分查找法每次比较都能将搜索范围缩小一半。在查找85时，第一次比较会定位到50左右，第二次比较会定位到80，第三次会找到85，所以共需3次比较，选C。 9. **无向图边数与连通性**： 在无向图中，要使所有顶点连通，至少需要n-1条边，因为可以从一个顶点出发，通过n-1条边连接到其他所有顶点，选B。 10. **快速排序结果**： 快速排序的问题没有给出具体的划分策略，但从提供的选项来看，没有一个符合题目给出的初始序列，所以无法确定具体结果。快速排序可能会得到不同的排列，选项中没有提供正确的答案。 11. **栈和队列操作**： 栈遵循后进先出的原则，若p1=3，说明3是最后一个出栈的元素，而2是入栈后被3覆盖的元素，所以p2应该是2，选A。 12. **二叉树的性质**： 双分支结点（度为2的节点）数加上单分支结点数（度为1的节点）应等于叶子结点数加1（每个叶子结点度为0），根据题目数据计算，15 + 30 = 45，因此叶子结点数为45，选A。 13. **环形队列元素个数**： 队列元素个数 = (队尾指针 - 队头指针) % 存储空间大小 + 1。代入f=8, r=3得 (3-8+20)%20+1=6，选B。 14. **二叉树中/前序遍历**： 中序遍历为 ABCDE，说明根节点在中间，前序遍历没有给出，但前序遍历通常根节点在最前面，因此可能是DEABC或者DCBAE，不能确定具体结果，选项中没有提供正确答案。 这些题目涵盖了数据结构中的关键概念和常见问题类型，通过解答这些题目，学生可以巩固对树、队列、线性表、图论等基础知识的理解。