计算机二级公共基础知识：算法复杂度与数据结构要点

经过对部分考生调查和近年真题的总结分析，计算机二级公共基础知识的笔试部分经常考查算法复杂度、数据结构的概念、栈、二叉树的遍历和二分法查找。本文将对这些重点知识点进行详细总结。 1. 算法的概念、算法时间复杂度及空间复杂度的概念： 算法是解决问题的一系列有穷步骤，包括可行性、确定性、有穷性和拥有足够情报等基本特征。算法对数据的运算和操作包括算术运算、逻辑运算、关系运算和数据传输。算法的控制结构是指算法中各操作之间的执行顺序。算法时间复杂度是指算法执行所需的时间，而空间复杂度是指算法执行所需的空间。 2. 数据结构的定义、数据逻辑结构及物理结构的定义： 数据结构是指组织和存储数据的方式，包括数据的逻辑结构和物理结构。数据的逻辑结构是指数据之间的关系，包括线性结构（如线性链表、栈、队列）和非线性结构（如树、图）。数据的物理结构是指数据在内存中的存储方式，包括顺序存储结构和链式存储结构等。 3. 栈的定义及其运算、线性链表的存储方式： 栈是一种先进后出（LIFO）的线性表，具有插入和删除操作的限制。栈的运算包括压栈（将元素插入栈顶）、出栈（将栈顶元素删除）和取栈顶元素等。线性链表是一种常见的数据结构存储方式，它通过指针将数据元素连接起来，每个节点都包含存储数据的信息和指向下一个节点的指针。 4. 树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历： 树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。二叉树是一种特殊类型的树，每个节点最多只有两个子节点。二叉树的基本性质包括根节点、左子树和右子树。完全二叉树是指除了最后一层外，其他层都是满的，且最后一层的节点都靠左排列。二叉树的遍历包括前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。 5. 二分查找法： 二分查找法是一种高效的查找算法，它通过将已排序的数组分成两部分，根据目标值与中间元素的比较结果来确定目标值的位置。通过每次取中间元素，可以将查找范围逐渐缩小一半，直到找到目标值或查找范围为空。 6. 冒泡排序法： 冒泡排序是一种简单但效率较低的排序算法，通过多次比较相邻元素的大小并交换位置来实现排序。每次比较都会将最大（或最小）的元素“冒泡”到最后（或最前）的位置，然后再对剩余的未排序元素进行相同的操作，直到所有元素都有序。 在考试中，算法的基本概念是一个重要的考点，通常以填空题的形式出现，该考点的考核概率为30%，分值为2分。除了识记算法的基本特征和要素外，读者还应了解算法中对数据的基本运算。此外，数据结构、栈、二叉树的遍历和二分法查找也是重点学习内容。通过总结整理好的超完整计算机二级公共基础知识文档中的相关知识点，读者可以更好地准备考试。