数据结构复习：算法与试题解析

"数据结构复习试题及答案" 这篇资料提供了数据结构相关的复习试题及答案，主要涵盖单选题和运算题，旨在帮助学习者检验和巩固数据结构的基础知识。 1. **算法评价**：算法评价通常包括正确性、时空复杂度、可读性和健壮性。选项B的“并行性”不是标准算法评价的常规内容，因此选择B。 2. **单链表插入**：在带有头结点的单链表中，向表头插入节点，需要将新节点的next指向原头结点的next，并将头结点指向新节点。所以正确答案是B。 3. **线性表的选择**：如果需要频繁进行插入和删除操作，链表更适合，因为链表的插入和删除操作相比数组更灵活，不需要移动元素。因此，答案是B。 4. **栈的输出序列**：栈遵循后进先出（LIFO）原则，选项C的312违反了这一原则，因此不可能是栈的输出序列。 5. **AOV网**：AOV网代表Activity On Vertex，即有向无环图（DAG），用于表示活动的开始和结束时间。 6. **散列表冲突处理**：开放定址法处理冲突时，平均查找长度通常高于链接法，因为链接法可以通过链表直接找到目标，而开放定址法则可能需要多次探测。 7. **形参与实参**：如果需要通过形参直接访问实参，应使用引用参数（D），因为引用参数可以修改实参的值。 8. **稀疏矩阵**：在带行指针的稀疏矩阵中，每个单链表中的结点具有相同的行号（A），方便按行进行操作。 9. **快速排序**：最坏情况下，快速排序的时间复杂度是O(n^2)，当输入数组已经完全逆序排列时会出现这种情况。 10. **二叉搜索树查找**：在二叉搜索树中查找元素的时间复杂度大致为O(logn)，因为树的结构保证了查找效率。 运算题部分： 1. 数据结构指的是数据以及它们之间的关系。当结点间存在M对N的联系时，这种结构称为M:N关联或多对多关系。 2. 队列的插入（入队）操作在队尾进行，删除（出队）操作在队头进行。 3. 顺序存储的栈中，用top==N表示栈空，当top==N-1时，表示栈满，因为数组下标从0开始，所以满的条件是top等于数组长度减一。 4. 在长度为n的单链表表头插入元素的时间复杂度为O(1)，因为在表头插入只需要改变几个指针；在表尾插入元素的时间复杂度为O(n)，因为需要遍历到表尾才能插入。 这些题目涉及的数据结构知识包括链表、栈、队列、数组、矩阵表示、算法复杂度、散列表、二叉搜索树等基础概念和操作。解答这些问题有助于理解这些核心概念及其应用。