东华大学数据结构期末复习：关键概念与选择题详解

在《数据结构期末复习题》中，主要涉及了数据结构和算法的基本概念，以及线性表的相关知识点。以下是对章节内容的详细解读： 第1章绪论： 1. **算法复杂性**：算法的计算量大小通常用其**时间复杂度**来衡量，即算法执行过程中随着问题规模增长所需资源的数量。时间复杂度A.效率、C.问题的规模和B.待处理数据的初态都可能影响它，但答案是C，因为它是两者共同决定的。 2. **算法定义**：计算机算法是指**解决问题的步骤序列**，它必须具备三个基本特性：**确定性**（每一步都有明确的定义）、**有穷性**（算法会在有限步骤内结束）和**可行性**（指令无二义性，即能清晰执行）。正确答案是B。 3. **算法性质**：算法是**问题求解步骤的描述**，并非具体程序，它描述了如何解决问题而不是如何实现。因此，B选项是最合适的。 4. **算法理解误区**：虽然算法最终会通过编程实现，但算法和程序并不完全相同；算法的含义更抽象，而程序是具体的代码实现。错误的说法包括B和C，算法可以有不同的实现方式，且指令的二义性不是算法可行性的一部分。 5. **时间复杂度与空间复杂度**：时间复杂度关注的是时间增长，空间复杂度则关注所需存储空间。原地工作的算法确实不需要额外空间，但O(n)和O(2n)的比较仅在特定情况下才有意义，如常数因子等，因此错误说法是B或C中的某个或全部。 6. **数据结构分类**：逻辑上，数据结构分为**线性结构**和**非线性结构**，它们描述了数据元素之间的关系，并非物理存储的连续性，所以C是正确的。 7. **与存储结构相关的术语**：循环队列、链表和哈希表都与数据的存储结构有关，而栈可能是逻辑结构的一部分，所以D是无关的。 8. **连续存储与地址连续**：在连续存储设计中，存储单元地址通常是**连续的**，答案是A。 9. **逻辑结构示例**：顺序表和有序表反映了数据的逻辑组织，这些是逻辑结构，而哈希表和单链表既可以看作逻辑结构也可以看作存储结构。 第2章线性表： 1. **顺序存储优点**：顺序存储结构的优势在于**存储密度大**，即单位存储空间内可以存储的数据量大，A是正确选项。 2. **线性表的特点**：线性表采用**顺序存储**时，要求连续的存储单元，不利于插入和删除，B和C是错误的；采用**链接存储**则可以避免这个问题，D是正确的。 3. **线性表元素类型**：线性表是一系列**数据元素**的集合，答案是C。 4. **线性表操作**：如果频繁进行存取指定序号的操作，说明对索引访问要求较高，这通常是顺序表的优点，但具体题目没有给出完整信息，这里无法给出唯一答案。 复习资料涵盖了数据结构的基础概念、线性表的存储和操作方式，以及算法的特性，对于期末考试复习有着重要的参考价值。