2017计算机二级公共基础知识

### 2017计算机二级公共基础知识知识点解析 #### 一、数据结构与算法 根据提供的文件信息，我们可以总结出2017年计算机二级考试中关于数据结构与算法的重要知识点，具体包括： 1. **算法的概念、算法时间复杂度及空间复杂度的概念** - **算法的基本特征**：可行性、确定性、有穷性和拥有足够的情报。 - **算法的基本要素**： - 对数据的运算和操作：主要包括算术运算、逻辑运算、关系运算和数据传输。 - 算法的控制结构：顺序、选择、循环三种基本控制结构。 - **算法的时间复杂度**：执行算法所需的计算工作量，通常用大O记号表示。 - **算法的空间复杂度**：执行算法所需的内存空间。 2. **数据结构的定义、数据逻辑结构及物理结构的定义** - 数据结构研究的是数据元素之间固有的逻辑关系、数据元素在计算机中的存储关系以及对数据结构进行的操作。 - **数据的逻辑结构**：表示数据元素之间的逻辑关系，常用的数据逻辑结构包括线性结构、非线性结构等。 - **数据的物理结构**：数据的逻辑结构在计算机存储空间中的表示形式，常见的存储结构有顺序存储、链式存储等。 3. **栈的定义及其运算、线性链表的存储方式** - **栈**：一种特殊的线性表，只允许在表的一端进行插入和删除操作，遵循后进先出的原则。 - **线性链表**：通过指针将数据元素链接起来的数据结构，每个节点包含数据域和指向下一个节点的指针。 4. **树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历** - **树**：非线性的数据结构，表示多个元素之间具有层次关系的结构。 - **二叉树**：每个节点最多有两个子节点的树形结构。 - **二叉树的遍历**：前序遍历、中序遍历和后序遍历。 5. **二分查找法** - 在有序数组中查找指定元素的一种高效算法，通过不断将搜索区间减半来缩小搜索范围。 6. **冒泡排序法** - 一种简单的排序算法，重复走访过要排序的列表，依次比较相邻两个元素，如果顺序错误就交换它们的位置。 #### 二、详细解析 1. **算法的概念** - 算法是一系列解决问题的步骤集合，能够解决特定问题或完成特定任务。 2. **算法复杂度** - **时间复杂度**：描述算法执行时间随问题规模增长的速度，通常用大O记号表示。 - **空间复杂度**：描述算法执行过程中所需内存空间的大小。 3. **数据结构的定义** - 数据结构是计算机中组织和存储数据的方式，使得数据能够有效地访问和修改。 4. **栈与链表** - **栈**：栈是一种特殊的数据结构，支持快速的压栈和弹栈操作。 - **链表**：链表是由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。 5. **树与二叉树** - **树**：树是一种非线性的数据结构，用于表示具有层次关系的数据集合。 - **二叉树**：每个节点最多有两个子节点的树形结构。 - **二叉树遍历**：遍历二叉树的方法有前序遍历、中序遍历和后序遍历，每种遍历方式都按照一定的规则访问节点。 6. **查找与排序** - **二分查找**：在有序数组中查找特定元素的一种方法，通过不断将搜索区间减半来提高查找效率。 - **冒泡排序**：通过重复比较相邻两个元素并交换位置来对数组进行排序的方法。 对于准备2017年计算机二级考试的学生来说，掌握以上知识点是非常重要的。不仅需要理解这些概念的基本含义，还需要能够灵活应用它们来解决实际问题。此外，还需要通过大量的练习来加深理解和记忆。