全国计算机等级考试公共基础的知识.pdf

全国计算机等级考试的公共基础部分，重点涵盖了数据结构与算法的知识。这部分内容是考试的核心，主要涉及算法的基本概念、算法复杂度、数据结构的定义、数据逻辑结构与物理结构、栈、二叉树的遍历、二分查找法以及简单的排序算法如冒泡排序。 1. **算法的基本概念**： - 算法具有可行性、确定性、有穷性和足够的信息四个基本特征。它是由对数据对象的操作和运算以及控制结构组成的。 - 数据运算包括算术运算、逻辑运算、关系运算和数据传输。 - 算法的控制结构则涉及算法执行顺序，通常通过顺序、选择和循环三种基本结构来描述。 2. **算法复杂度**： - 时间复杂度衡量的是算法执行所需计算工作量，通常用问题规模n的函数f(n)来表示，不受硬件或软件因素影响。 - 空间复杂度关注算法执行所需的内存空间，包括初始数据、工作单元和额外空间。原地工作算法的额外空间相对于问题规模是常数。 3. **数据结构**： - 数据结构是数据元素间的逻辑关系和存储关系的研究，包括逻辑结构（如集合、线性结构、树形结构和图形结构）和存储结构（如顺序存储、链式存储、索引存储）。 - 数据元素是数据的基本单位，数据对象是相同类型数据元素的集合。 - 逻辑结构描述了数据元素之间的关系，而存储结构则关注这些关系在计算机内存中的实际表示。 4. **线性结构与非线性结构**： - 线性结构如数组和链表，数据元素呈线性排列，每个元素只有一个前驱和一个后继。 - 非线性结构如树和图，元素之间的关系更为复杂，可以有多于两个的前后件关系。 在复习时，考生需要特别注意算法的时间复杂度和空间复杂度概念，因为这是考试中的高频考点，通常以选择题形式出现。同时，理解数据结构的逻辑结构和存储结构的区别，以及如何根据需求选择合适的数据结构，也是至关重要的。对于栈、二叉树的遍历和二分查找等具体知识点，考生应熟练掌握它们的基本原理和应用。 总结来说，全国计算机等级考试公共基础的这部分内容需要考生深入理解和应用，不仅要在理论层面理解算法和数据结构的基本概念，还要能够进行实际问题的求解和分析。通过大量的练习和实例分析，考生才能更好地应对考试中的各种问题。