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