数据结构考试重点：算法评价与链表操作

"数据结构考试题(三).doc" 这篇文档是一个数据结构的考试题目集，包含选择题和运算题，涵盖了数据结构的基础概念和操作。以下是相关知识点的详细说明： 1. **算法评价标准**： - 正确性：算法必须能够正确地解决预期问题。 - 时空复杂度：算法运行所需的时间（时间复杂度）和空间（空间复杂度）是衡量效率的重要指标。 - 健壮性：算法对异常输入的处理能力。 - 可读性：代码的清晰度和易理解性，便于维护和调试。 2. **链表操作**： - 在带有头结点的单链表中，向表头插入节点需要将新节点的`next`指针指向当前头结点的`next`，然后将头结点的`next`指针指向新节点。 3. **线性表的表示**： - 链表适合频繁的插入和删除操作，因为这些操作只需要改变指针，而不需要移动元素。 4. **栈的操作性质**： - 栈是一种后进先出（LIFO）的数据结构，栈的输出序列不可能违反这一原则。例如，输入序列123，不可能通过正常的栈操作得到312的输出序列。 5. **AOV网**： - AOV网是Activity On Vertex的缩写，指的是有向无环图（DAG），用于表示活动的开始和结束时间。 6. **散列表冲突处理**： - 开放定址法处理冲突可能导致平均查找长度高于链接法，因为可能需要线性探测，而链接法则通过链表连接冲突的元素。 7. **形参与实参**： - 引用参数允许形参直接修改实参的值，实现类似指针的效果，但更安全且不需要解引用。 8. **稀疏矩阵的存储**： - 稀疏矩阵的带行指针向量的链接存储中，每个单链表代表一行，链表中的结点具有相同的行号，列号和元素值可能不同。 9. **快速排序的时间复杂度**： - 最坏情况下，即每次划分都只能减少一个元素，时间复杂度为O(n^2)。 10. **二叉搜索树查找效率**： - 二叉搜索树的查找时间复杂度在平衡时是O(logn)，但在最坏情况下（退化成链表）是O(n)。 1. **数据结构概念**： - 数据结构是数据的组织方式，它描述了数据之间的关系以及操作这些数据的方法。 - M对N的联系通常对应于多对多的关系，这种结构可以是关联数组、多维数组或图。 2. **队列的性质**： - 队列遵循先进先出（FIFO）原则，元素在队尾加入，队首移除。 3. **顺序存储栈的满与空**： - 用数组存储栈时，栈顶指针`top`等于数组长度表示栈空，等于0表示栈满（因为下标从0开始，满时无法再插入）。 4. **链表插入操作的时间复杂度**： - 在链表头部插入元素的时间复杂度为O(1)，因为只需要改变几个指针。 以上就是文档中涉及的数据结构相关知识点，包括算法评价、链表操作、线性表、栈、图、散列表、引用参数、稀疏矩阵、排序和查找等。