2021考研计算机408数据结构选择题详解及时间复杂度分析

本文档是针对考研计算机408考试的数据结构部分复习资料，由一位2021年的应届考生整理，涵盖了数据结构的基本概念、术语以及算法复杂度的分析。以下是部分内容的详细解读： 1. 数据结构概述 - 数据结构相关概念包括数据的逻辑结构、物理结构和数据运算。逻辑结构描述数据元素之间的关系，如线性结构（如数组、链表）、树形结构和图等。物理结构涉及数据在内存中的存储方式，如顺序存储、链式存储、索引存储和散列存储。循环队列和链表属于物理结构，而栈更多体现的是逻辑结构。 2. 抽象数据类型 (ADT) ADT 是数据结构的重要组成部分，它定义了一个数据集的抽象概念，包含数据对象、数据关系和基本操作集合。例如，一个栈可以通过其入栈和出栈操作来定义，而无需关心具体的存储细节。 3. 算法复杂度分析 - 时间复杂度考察的是执行算法所需的基本操作次数与问题规模的关系。如2013年的真题中，合并两个升序链表为降序链表，由于可能需要遍历所有元素，最坏情况下的时间复杂度为O(max(m,n))。 - 2019年的真题涉及一个while循环，其时间复杂度是O(n 1/2)，因为每次循环使得n减小为原来的一半，直到n小于等于1。 4. 算法复杂度理解误区 - 选项I提到的“原地工作”指的是算法在执行过程中不需要额外的存储空间，仅占用常量空间。但这并不意味着在所有情况下，O(n)复杂度的算法都优于O(2 n)，因为效率还取决于具体问题和实现细节。选项II错误地认为时间复杂度简单的算法总是更快，而选项IV认为编程语言级别对效率的影响被忽略了，这也是不正确的，实际执行效率受到多种因素影响。 这份资料对于准备考研计算机408考试的学生来说，提供了实用的复习材料，帮助他们理解和掌握数据结构的基础理论以及算法复杂度的评估方法。通过学习和做题，考生可以增强对数据结构的理解，提高解题能力。