计算机二级 公共基础知识部分
? ?
线性表中所有元素所占的存储空间是连续的.
线性表中各数据元素在存储空间中是按逻辑顺序以此存放的.
2.3 栈和队列
1. 栈
? 栈是限定在一端进行插入与删除的线性表.
? 在栈中，允许插入与删除的一端成为栈顶，不允许插入与删除的另一端称为栈底.
? 通常用指针top来指示栈顶的位置，用指针bottom指向栈底. 用一维数组S(1:m)作为栈的顺序存储空
间，其中m为栈的最大容量. top=0表示栈空，top=m表示栈满. ? 元素插入、删除实例
2. 队列
? 队列是允许在一端进行插入、而在另一端进行删除的线性表.
6
计算机二级 公共基础知识部分
? 允许插入的一端称为队尾，通常用尾指针rear指向队尾元素，即尾指针总是指向最后被插入的元素. 允
许删除的一端称为排头，通常用排头指针front指向排头元素的前一个位置. ? 元素插入、删除实例：
3. 循环队列
? 循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用. ? 循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置.
? ? ?
循环队列的初始状态为空，rear=front=m.
入队运算：每进行一次入队运算，rear=rear+1. 当rear=m+1时，置rear=1. 退队运算：每进行一次退队运算，front=front+1. 当front=m+1时，置front=1.
7
计算机二级 公共基础知识部分
2.4 线性链表
? 在链式存储方式中，要求每个结点有两部分组成：一部分用于存放数据元素值，称为数据域；另一部分
用于存放指针，称为指针域. 其中指针用于指向该结点的前一个或后一个结点.
? 在线性链表中，用一个专门的指针HEAD指向线性链表中的第一个数据元素的结点. 线性表中的最后一
个元素没有后件，因此，线性链表中最后一个结点的指针域为空(用NULL或0表示). ? 带链的栈与带链的队列：
2.5 树与二叉树
1. 树的基本概念
? 父节点和子结点：一个结点的前件和后件结点. ? 根：没有前件的结点. ? 叶子节点：没有后件的结点.
? 结点的度：一个结点所拥有的后件个数.
? 树的度：在树中，所有结点中最大的度. ? 树的深度：树的最大层次.
? 树中的结点数为树中所有结点的度再加1.
2. 二叉树
? 二叉树的基本性质：
? ? ?
在二叉树的第k层上，最多有2k-1个结点. 深度为m的二叉树最多有2m-1个结点.
在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个.
8
计算机二级 公共基础知识部分
?
具有n个结点的二叉树，其深度至少是[log2n]+1，“[]”表示向下取整.
? 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干节点. ? 在计算机中，二叉树采用链式存储结构. 存储二叉树的存储结点的指针域有两个：一个用于指向该结点
的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域.
3. 二叉树的遍历
? 前序遍历DLR：首先访问根节点，然后遍历左子树，最后遍历右子树. ? 中序遍历LDR：首先遍历左子树，然后访问根节点，最后遍历右子树. ? 后序遍历LRD：首先遍历左子树，然后遍历右子树，最后访问根节点. ? 一个实例：
? ? ?
前序遍历：FCADBEGHP 中序遍历：ACBDFEHGP 后序遍历：ABDCHPGEF
9
计算机二级 公共基础知识部分
2.6 查找与排序
? 查找与排序技术的比较
查找与排序技术名称 查找技术 顺序查找 二分法查找 冒泡法查找最大项 交换类排序法 排序技术 插入类排序法 选择类排序法 冒泡排序法 快速排序法 简单插入排序法 希尔排序法 简单选择排序法 堆排序法 最坏情况下比较次数 n log2n n-1 n(n-1)/2 也就是O(n2) n(n-1)/2也就是O(n2) n(n-1)/2也就是O(n2) 增量序列ht=n/2k (k=1,2,…,[log2n])时为O(n1.5) 每轮元素移动 可能移去多个逆序 可能移去多个逆序，也会产生新的逆序 最多移去一个逆序 可能移去多个逆序 n(n-1)/2也就是O(n2) O(nlog2n) 10
计算机二级公共基础知识部分
