2024年计算机二级考试选择题必背知识点公共基础计算机基础.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（n0）个元素的有限集合。它有且仅有一种称為根的元素；其他元素是互不相交的子树。

常用术語：

父結点、子結点；

根結点、叶子結点；

結点的度、树的度（所有結点中最大的度称為树的度）；

树的深度；

子树（以某个結点的一种子結点為根构成的树称為该結点的一颗子树）。

2.二叉树：是一种有限的結点集合，该集合或者為空，或者有一种根結点及其两颗互不相交的