文档介绍：全国计算机等级考试二级公共基础知识总结
第一章数据结构与算法
算法
:可行性;确定性,有穷性;拥有足够的情报。,
:列举法、归纳法、递推、递归、减斗递推技术、回溯法。
:算法时间复杂度和算法空间复杂度。
。
。
:一是对数据对象的运算和操作;二是算法的控制结构。
数据结构的基本基本概念
:数据的逻辑结构;数据的存储结构(物理结构);数据运算。
,与所用的计算机无关
。
。
。
,一般将数据结构分为两大类型:线性结构与非线性结构。
,对于数据集合中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点或结点
。除此之外,对数据结构的运算还有查找、分类、合并、分解、复制和修改等。
,用一组地址连续的存储单元依次存储数据元素的方式是线性结构。
,还可以直观地用图形表示
线性表及其顺序存储结构
,
。,数据元素之间的相对位置是线性的。
。
:
(1)且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。
:
(1)线性表中所有元素的所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
栈和队列
,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。
“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。
(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。
“先进行出”(FIFO)或“后进后出”(LILO)的线性表。
(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满
线性链表
,线性链表属于存储结构。
,这种存储单元(一个一个小块)称为存储结点,简称结点。
:(1)用于存储数据元素值,称为数据域;(2)用于存放指针,称为指针域,用于指向前一个或后一个结点。
:插入、删除、查找、排序。
,这两个指针分别指向它的前驱结点和后继结点。
树与二叉树
,所有元素之间具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。
二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
,结点最少的树为只有一个结点的树;二叉树的结点数可以为0,结点最少的二叉树为空的二叉树。
,对含有100个结点的二叉树,可能的最大树深和最小树深分别是99和6(要使二叉树在规定结点下有最大树深,这时二叉树退化成一个线性链表,如果对应二叉树的根结点的层次为0,那么对应二叉树的树深为结点个数减1,即99;要使二叉树有最小树深,则此二叉树为满二叉树,当满二叉树的根结点的层次为1时,结点个数n和树深h之间的关系为:n=2^h-1,所以当二叉树的根结点层次为0时,对应关系为n=2^(h+1)-1。)
1