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

"数据结构考试题(卷）（三）.doc" 这篇文档是一份关于数据结构的考试题目，涵盖了单选题和运算题，主要测试考生对数据结构基础概念、算法分析、数据结构实现以及操作的理解。以下是部分知识点的详细说明： 1. 算法评价标准：选项B中的“并行性”不是一般算法评价的基本内容，正确的评价通常包括正确性、时空复杂度、健壮性和可读性。 2. 链表操作：在带有头结点的单链表中，向表头插入节点的操作是将新节点的`next`指针指向当前头结点的`next`，然后将头结点的`next`指向新节点。正确操作为A选项。 3. 线性表的表示选择：如果经常需要插入和删除操作，链式存储（如链表）比顺序存储（如数组）更合适，因为链表在插入和删除时无需移动元素。 4. 栈的性质：栈是后进先出（LIFO）的数据结构。选项C（312）是不可能的栈输出序列，因为它违反了LIFO原则。 5. AOV网：AOV网代表Activity On Vertex，即有向无环图（DAG），用于表示项目或任务的依赖关系。 6. 散列表冲突处理：开放定址法处理冲突时，平均查找长度通常高于链地址法，因为链地址法可以在找到空槽时立即插入，而开放定址法则可能需要多次探测。 7. 形参与实参：如果需要形参直接访问实参，应该使用指针或引用作为形参类型，这里选择D（引用）。 8. 稀疏矩阵存储：带行指针向量的存储方式中，每个单链表对应一行，因此链表中的节点具有相同的行号。 9. 快速排序最坏情况：快速排序在最坏情况下，即待排序序列已经完全有序或逆序时，时间复杂度为O(n^2)。 10. 二叉搜索树查找：二叉搜索树是有序的，查找时间复杂度在平均和最好情况下为O(logn)，最坏情况下为O(n)，但通常为O(logn)。 运算题部分： 1. 数据结构是指数据及其相互之间的组织方式。当结点间存在M对N的关系时，称为多对多关联或M:N关系。 2. 队列遵循先进先出（FIFO）原则，插入操作在队尾，删除操作在队首。 3. 在数组中顺序存储栈时，栈空的表示是`top==N`，栈满的条件是`top==0`（因为栈顶指针满时会回到数组的起始位置）。 4. 在长度为n的单链存储线性表头部插入元素，时间复杂度为O(1)，因为不需要移动已有元素。 这些题目涉及到的数据结构和算法知识包括但不限于：算法评价、链表操作、线性表存储、栈的性质、有向图、散列表、引用参数、稀疏矩阵、快速排序和二叉搜索树。这份试卷旨在考察学生对这些基本概念的理解和应用能力。