《数据结构》复习重点.doc

《数据结构》复习重点主要涵盖了数据结构的基本概念、术语、分类以及算法和算法分析的关键点。以下是详细的知识点解析： 1. **数据结构**：数据结构是研究非数值计算问题中计算机操作对象及其关系和操作的学科。它关注的是如何组织、存储和处理数据，以便高效地执行算法。 2. **基本概念**： - **数据**：是客观事物的符号表示，可以是计算机程序处理的任何符号。 - **数据项**：数据的最小不可分割单位。 - **数据元素/数据结点**：数据的基本处理单元，由一个或多个数据项组成。 - **数据对象**：具有相同性质的数据元素集合，是数据的子集。 - **数据结构的分类**：分为线性结构（如数组、链表）和非线性结构（如树、图）。 3. **数据结构的形式化定义**：Data_Structure=(D,S)，其中D是数据元素的有限集合，S是D上的关系的有限集合。 4. **物理结构/存储结构**：数据在计算机内存中的表示方式，分为顺序存储结构和链式存储结构。 - **顺序存储结构**：数据元素在内存中按其逻辑顺序连续存放，适合随机访问。 - **链式存储结构**：通过指针连接数据元素，逻辑上相邻的元素在内存中不一定相邻，支持动态分配。 5. **数据类型**：是值的集合和定义在该集合上的操作集，规定了变量或表达式的值域和允许的操作。 6. **算法**：是解决问题的明确规范，是一系列有限的指令，有穷性、确定性、可行性、输入和输出是算法的五大特性。 7. **算法分析**：评估算法性能的主要指标是时间复杂度和空间复杂度，衡量算法运行时间和所需内存。 - **时间复杂度**：关注算法执行的最基本操作次数，常用大O记法表示，如O(1)、O(n)、O(n^2)等。 - **空间复杂度**：关注算法执行过程中所需的内存空间。 8. **算法分析的其他方面**：包括正确性、可读性、健壮性，以及效率和低存储量需求。 复习题答案： 1. 填空题： - 数据元素 - 数据元素 - 关系 - 线性结构 - 非线性结构 2. 选择题： - B. 输入性、输出性、可行性、确定性和有穷性 - A. 空间复杂度和时间复杂度 3. 计算题： - 求算法`sort(int *x, int n)`的时间复杂度及带@语句的频度，需要分析具体算法代码来计算。通常，嵌套循环的时间复杂度是外层循环乘以内层循环的复杂度，如示例中给出的算法部分，第一层循环执行n-1次，第二层循环在每次外层循环中执行n-i次，所以时间复杂度为O(n^2)。 数据结构的学习是计算机科学的基础，理解和掌握这些知识点对于编写高效、优化的代码至关重要。在复习时，应重点理解数据结构的逻辑结构和物理结构的区别，算法的时间复杂度分析方法，以及如何根据问题选择合适的数据结构和算法。同时，通过实际编程练习来加深对这些概念的理解。