计算机二级公共基础知识点（一）思维导图

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列

冒泡排序法，需要比较的次数为n(n-1)/2

快速排序法

简单插入排序法，最坏情况需要n(n-1)/2次比较

希尔排序法，最坏情况需要O(n1.5)次比较

简单选择排序法, 最坏情况需要n(n-1)/2次比较

堆排序法，最坏情况需要O(nlog2n)次比较

（1）线性表为无序表；

（2）表采用链式存储结构

树是一种简单的非线性结构，所有元素之间具有明显的层次特性

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根

每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中的度称为树的度

树的层次称为树的深度

非空二叉树只有一个根结点

每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树

（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；

（2）深度为m的二叉树最多有2m-1个结点；

（2）深度为m的二叉树最多有2m-1个结点；

（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；

（5）具有n个结点的完全二叉树的深度为[log2n]+1；

（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n）

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；

（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点

用于存储数据元素值，称为数据域

用于存放指针，称为指针域，用于指向前一个或后一个结点

栈的基本运算

删除元素称为退栈运算

读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化

入队运算：从队尾插入一个元素

退队运算：从队头删除一个元素。

由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件

（1）且只有一个根结点a1，它无前件；

（2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表

（1）线性表中所有元素的所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的