计算机二级考试选择题必背知识点(公共基础+计算机基础).docx 计算机二级考试选择题必背知识点 公共基础 第一章 数据结构与算法 §1.1 算法 算法的定义：是指解题方案的准确而完整的描述。（算法不等于程序，程序的设计不可能优于算法的设计） 算法的基本特征：可行性、确定性、有穷性、足够的情报。 算法的基本要素： 对数据对象的运算和操作 算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构 算法中各操作之间的执行顺序； 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等； 一个算法一般可以用顺序、选择（分支）、循环（重复）三种基本结构组合而成。 算法的时间和空间复杂度：算法的时间复杂度和算法的空间复杂度相互独立。 时间复杂度 指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量。 空间复杂度 指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间。 §1.2 数据结构的基本概念 数据：需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征。 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可有若干数据项组成。数据项是数据的最小单位。 结构：是集合中各个数据元素之间存在的某种关系（或联系）。 数据结构：是指相互有关联的数据元素的集合。 数据结构的分类： 逻辑结构：线性结构（线性表、栈、队列）；非线性结构（树、图）。 存储结构：顺序存储；链式存储。 运算：插入、删除、查找、排序。 逻辑结构：反应数据元素间的逻辑关系（即前后件关系）的数据结构。 线性结构（线性表）：（举例：春→夏→秋→冬） a.有且只有一个根节点，它无前件； b.每一个节点最多有一个前件，也最多有一个后件。 非线性结构： a.不满足以上两个条件的数据结构就称为非线性结构； b.非线性结构主要是指树形结构和网状结构。 存储结构：又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式 顺序存储结构：主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 链式存储结构：每一个结点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系。 §1.3 线性表及其顺序存储结构 线性表：线性表是n（n≥0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。 举例：英文字母表、地理学中的四向、表格 线性表的顺序存储结构：通常线性表可以采用顺序存储和链式存储，但一般使用顺序存储结构。线性表的顺序存储又叫做顺序表（顺序分配）。 特点： 线性表中所有元素所占的存储空间是连续的； 线性表中数据元素在存储空间中是按逻辑顺序依次存放的； 可以随机访问数据元素； 做插入、删除时需移动大量元素，因此线性表不便于插入和删除元素。 §1.4 栈和队列 栈：栈是限定在一端进行插入和删除的线性表。 特点：★ 栈是只能在栈顶进行插入和删除； 栈的修改原则是“先进后出”或“后进先出”； 栈底指针boottom，栈顶指针top，入栈，栈满，出栈； 栈底指针不变，栈中元素随栈顶指针的变化而动态变化； 栈具有记忆功能； 栈支持子程序调用。 队列：队列是指允许在一端进行插入，而在另一端进行删除的线性表。 特点： 队列只允许在队尾进行插入，而在队头进行删除； 队列的修改原则是“先进先出”或“后进后出”； 队头指针front，队尾指针rear，入队，出队； 队列中元素随队头指针和队尾指针的变化而动态变化。 循环队列：是讲队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间 rear＞front：s=rear-front rear＜front：s=容量+rear-front rear=front：s=1或者s=0 §1.5 线性链表 线性链表：线性表可以采用顺序存储和链式存储。线性表的顺序存储叫做顺序表，线性表的链式存储结构叫做线性链表。 特点： 各数据结点的存储空间可以不连续； 各数据元素的存储顺序和逻辑循序可以不一致； 线性表的链式存储所占存储空间大于顺序存储结构； 查找结点时链式储存要比顺序存储慢； 链式存储插入删除元素比顺序存储灵活。 线性链表的操作：在线性链表中进行插入与删除，不需要移动链表中的元素。 线性表：①线性表顺序存储结构；②线性表链式存储结构（还包括双向链表、循环链表）。★ §1.6 树与二叉树（★） 树：是n（n>0）个元素的有限集合。它有且仅有一个称为根的元素；其余元素是互不相交的子树。 常用术语： 父结点、子结点； 根结点、叶子结点； 结点的度、树的度（所有结点中最大的度称为树的度）； 树的深度； 子树（以某个结点的一个子结点为根构成的树称为该结点的一颗子树）。 2. 二叉树：是一个有限的结点集合，该集合或者为空，或者有一个根结点及其两颗互不相交的左右