C++数据结构期末考试：拓扑排序与操作复杂性

"这份资料是关于数据结构的英文考试题目，主要涵盖C++编程语言。" 在数据结构领域，这些题目涉及了多个核心概念，下面将对其中的一些知识点进行详细解释： 1. **有向无环图(DAG)**：题目提到“Only...graph has topological order”，指的是有向无环图（Directed Acyclic Graph）具有拓扑排序。拓扑排序是将有向无环图的顶点排成线性序列，使得对于每一条有向边 (u, v)，顶点 u 在序列中都出现在顶点 v 之前。 2. **队列**：描述中提到“all insertions and deletions of entries are made at one end”，这是对队列数据结构的描述。队列是一种先进先出（First In First Out, FIFO）的数据结构，适用于处理顺序访问的情况，如任务调度或打印作业等。 3. **C++中的循环队列**：在C++中，可以使用`std::deque`(双端队列)来实现循环队列，因为`deque`可以在两端进行插入和删除操作。 4. **链表操作的时间复杂度**：链表的插入和删除通常需要O(1)的时间，而清除、检查空、满、大小、替换和检索操作在平均情况下都是O(1)时间复杂度。 5. **二分查找**：提及的“searching method that requires ordered list”是二分查找法，它在有序列表中查找元素，每次比较后将搜索范围缩小一半，时间复杂度为O(log n)。 6. **插入操作的平均时间复杂度**：没有具体指明是哪种数据结构，但如果是平衡二叉搜索树（如AVL树或红黑树），插入操作的平均时间复杂度是O(log n)。 7. **递归**：描述了一个函数调用自身或一系列函数，最终导致再次调用自身的情况，这是递归的概念。递归是计算机科学中一种重要的算法，常用于解决分治策略和树形结构的问题。 接下来是多选题的部分： 1. **队列的定义**：D. FIFO list（先进先出列表）正确。队列遵循FIFO原则，与栈（LIFO，后进先出）不同。 2. **树中的术语**：B. sibling（兄弟节点）正确。在树中，具有相同父节点的节点称为兄弟节点。 3. **三节点的二叉树形状**：在二叉树中，有五种不同的形状，包括完全二叉树、满二叉树、斜树以及两种只有一个孩子节点的树。 以上就是这份数据结构考试题涉及到的一些关键知识点，涵盖了图、队列、链表操作、查找算法、递归、树结构等基础概念。对于学习和理解数据结构以及C++编程至关重要。