2022年计算机二级公共基础知识点梳理：数据结构与算法

2022年计算机二级公共基础知识点梳理数据结构与算法2022年计算机二级公共根底学问点梳理数据构造与算法

1、算法算法是指解题方案的精确而完整的描述算法不等于程序，也不等计算机方法，程序的编制不行能优于算法的设计算法的根本特征是一组严谨地定义运算挨次的规章，每一个规章都是有效的，是明确的，此挨次将在有限的次数下终止特征包括1可行性；2确定性，算法中每一步骤都必需有明确定义，不充许有模棱两可的解释，不允许有多义性；3有穷性，算法必需能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；4拥有足够的情报算法的根本要素一是对数据对象的运算和操作；二是算法的掌握构造指令系统一个计算机系统能执行的全部指令的集合根本运算和操作包括算术运算、规律运算、关系运算、数据传输算法的掌握构造挨次构造、选择构造、循环构造算法根本设计方法列举法、归纳法、递推、递归、减斗递推技术、回溯法算法简单度算法时间简单度和算法空间简单度算法时间简单度是指执行算法所需要的计算工作量算法空间简单度是指执行这个算法所需要的内存空间

2、数据构造的根本根本概念数据构造讨论的三个方面1数据集合中各数据元素之间所固有的规律关系，即数据的规律构造；2在对数据进展处理时，各数据元素在计算机中的存储关系，即数据的存储构造；3对各种数据构造进展的运算数据构造是指相互有关联的数据元素的集合数据的规律构造包含1表示数据元素的信息；2表示各数据元素之间的前后件关系数据的存储构造有挨次、链接、索引等线性构造条件1有且只有一个根结点；2每一个结点多有一个前件，也多有一个后件非线性构造不满意线性构造条件的数据构造

3、线性表及其挨次存储构造线性表由一组数据元素构成，数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的在简单线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件非空线性表的构造特征1且只有一个根结点al,它无前件；2有且只有一个终端结点an,它无后件；3除根结点与终端结点外，其他全部结点有且只有一个前件，也有且只有一个后件结点个数n称为线性表的长度，当nR时，称为空表线性表的挨次存储构造具有以下两个根本特点1线性表中全部元素的所占的存储空间是连续的；2线性表中各数据元素在存储空间中是按规律挨次依次存放的ai的存储地址为adrai=adra1+i-1k,,adral为个元素的地址，k代表每个元素占的字节数挨次表的运算插入、删除

4、栈和队列栈是限定在一端进展插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底栈根据“先进后出”（理）或“后进先出”（lif）组织数据，栈具有记忆作用用top表示栈顶位置，用bottom表示栈底栈的根本运算

（1）插入元素称为入栈运算；

（2）删除元素称为退栈运算；⑶读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化队列是指允许在一端（队尾）进入插入，而在另一端（队头）进展删除的线性表rear指针指向队尾，fimt指针指向队头队列是“先进展出”（行fo）或“后进后出”（山）的线性表队列运算包括⑴入队运算从队尾插入一个元素；⑵退队运算从队头删除一个元素循环队列s=0表示队列空，s=l且front=rear表示队列满

5、线性链表数据构造中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点结点由两局部组成

（1）用于存储数据元素值，称为数据域；

（2）用于存放指针，称为指针域，用于指向前一个或后一个结点在链式存储构造中，存储数据构造的存储空间可以不连续，各数据结点的存储挨次与数据元素之间的规律关系可以不全都，而数据元素之间的规律关系是由指针域来确定的链式存储方式即可用于表示线性构造，也可用于表示非线性构造线性链表，head称为头指针，head=null或0称为空表，假如是两指针左指针llink指向前件结点，右指针rlink指向后件结点线性链表的根本运算查找、插入、删除

6、树与二叉树树是一种简洁的非线性构造，全部元素之间具有明显的层次特性在树构造中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根每一个结点可以有多个后件，称为该结点的子结点没有后件的结点称为叶子结点在树构造中，一个结点所拥有的后件的个数称为该结点的度，全部结点中的度称为树的度树的层次称为树的深度二叉树的特点1非空二叉树只有一个根结点；2每一个结点多有两棵子树，且分别称为该结点的左子树与右子树二叉树的根本性质1在二叉树的第k层上，多有2k-lkNl个结点；2深度为m的二叉树多有2m-1个结点；3度为0的结点即叶子结点总是比度为2的结点多一个；⑷具有n个结点的二叉树，其深度至少为［log2n］+l,其中［log2n］表示取log2n的整数局部;5具有n个结点的完全二叉树的深度为[log2n]+l；6设完全二叉树共有n个结点假如从根结点开头，按层序每一层从左到右用自然数1,2,....n给结点进展编号k=

12...n,有以下结论

①若k=L则该结点为根结点，它没有父结点；若k〉l,则该结点的父结点编号为父k/2；

②若2kSi,则编号为k的结点的左子结点编号为2k；否则该结点无左子结点也无右子结点；

③若2k+lSi,则编号为k的结点的右子结点编号为2k+l；否则该结点无右子结点满二叉树是指除后一层外，每一层上的全部结点有两个子结点，贝依层上有2k-1个结点深度为m的满二叉树有2m-1个结点完全二叉树是指除后一层外，每一层上的结点数均到达值，在后一层上只缺少右边的若干结点二叉树存储构造采纳链式存储构造，对于满二叉树与完全二叉树可以按层序进展挨次存储二叉树的遍历1前序遍历dlr,首先访问根结点，然后遍历左子树，后遍历右子树；2中序遍历Idr,首先遍历左子树，然后访问根结点，后遍历右子树；3后序遍历Ird首先遍历左子树，然后访问遍历右子树，后访问根结点

7、查找技术挨次查找的使用状况1线性表为无序表；2表采纳链式存储构造二分法查找只适用于挨次存储的有序表，对于长度为n的有序线性表,坏状况只需比拟log2n次

8、排序技术排序是指将一个无序序列整理成按值非递减挨次排列的有序序列交换类排序法1冒泡排序法，需要比拟的次数为nn-l/2；2快速排序法插入类排序法⑴简洁插入排序法，坏状况需要nn-l/2次比拟；2希尔排序法，坏状况需要nl.5次比拟选择类排序法⑴简洁选择排序法，坏状况需要nn-l/2次比拟；2堆排序法，坏状况需要nlog2n次比拟。