计算机等级考试二级公共基础考前背诵版

### 计算机等级考试二级公共基础考前背诵版知识点详解 #### 一、算法与数据结构（历年比例41%） ##### 1.1 算法 - **定义**：算法是对解决问题方法的一种精确描述。它具有**可行性**、**确定性**、**有穷性**的特点，并且在解决问题时需要足够的信息支持。 - **有穷性**：算法在有限时间内完成。 - **复杂度**：用于衡量算法效率，分为**时间复杂度**和**空间复杂度**。 - **时间复杂度**：执行算法所需计算工作量。 - **空间复杂度**：算法执行过程中所需的存储空间。 - **关系**：时间复杂度和空间复杂度之间不存在必然联系。 ##### 1.2 数据结构 - **分类**：数据结构可以分为**逻辑结构**和**存储结构**。 - **逻辑结构**：如线性结构（链表、栈等）、非线性结构（树、图等）。 - **存储结构**（物理结构）：顺序存储、链式存储、索引存储等。 - **循环队列**：属于存储结构。 - **存储结构的重要性**：数据的逻辑结构决定了存储结构的选择，不同的存储结构影响数据处理效率。 - **线性结构**：线性表、队列、栈等。 - **非线性结构**：树、图等。 - **线性表存储**：顺序存储和链式存储。 - **顺序存储**：元素连续存储。 - **链式存储**：元素存储位置可不连续。 - **有序线性表**：可以采用顺序存储或链式存储。 - **队列**：一种特殊线性表，遵循先进先出(FIFO)原则。 - **循环队列**：队列的顺序存储结构，队头指针和队尾指针共同决定队列中元素的数量。 ##### 1.3 栈和队列 - **栈**：特殊的线性表，遵循先进后出(FILO)原则。 - **特点**：仅在一端进行插入和删除操作。 - **记忆作用**：栈顶元素总是最后入栈的元素。 - **操作**：入栈和出栈操作中栈底指针不变。 - **队列**：允许在一端插入，在另一端删除的线性表。 - **特点**：先进先出(FIFO)。 - **循环队列**：利用队头指针和队尾指针计算队列中元素的数量。 - **栈与队列的共性**：都只允许在端点处进行插入和删除操作。 - **栈的应用**：支持子程序调用。 - **存储方式**：栈不仅可以顺序存储，还可以链式存储。 ##### 1.4 线性链表 - **定义**：线性链表是线性表的一种链式存储结构。 - **优点**：便于插入和删除操作。 - **特性**：存储空间不一定连续，元素存储顺序任意。 ##### 1.5 树与二叉树 - **树结构**：结点度数、树的度。 - **二叉树**：结点度数只可能是0、1、2。 - **结点数量计算**： - **性质1**：叶子结点数比度为2的结点多一个。 - **性质2**：对于完全二叉树，当结点总数N为奇数时，叶子结点数为(N+1)/2；N为偶数时，叶子结点数为N/2。 - **性质3**：满二叉树第k层结点数为2^(k-1)，总结点数为2^k-1。 - **二叉树遍历**：前序遍历（根->左->右）、中序遍历（左->根->右）、后序遍历（左->右->根）。 - **前序遍历**：访问根节点，然后递归遍历左子树，再递归遍历右子树。 - **中序遍历**：递归遍历左子树，访问根节点，递归遍历右子树。 - **后序遍历**：递归遍历左子树，递归遍历右子树，访问根节点。 以上知识点是针对计算机等级考试二级公共基础部分的重要概念和理论基础，理解并掌握这些内容对于通过考试至关重要。特别是标记了多个星号的部分，几乎每次考试都会涉及，考生需要特别关注。