2014年计算机三级数据库背诵资料：第二章

第二章 数据结构算法

　　1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位

　　2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算

　　3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构

　　顺序存储结构：

　　顺序存储计算公式 Li=L0+(i-1)×K 顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动

　　链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小

　　b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点

　　4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。

　　5、链表：线性链表(单链表和双向链表等等)和非线性链表

　　线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。(注意结点的插入和删除操作)

　　6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等

　　7、队列：“先进先出”线性表。应用：树的层次遍历

　　8、串：由零个或多个字符组成的有限序列。

　　9、多维数组的顺序存储：

　　10、稀疏矩阵的存储：下三角矩阵顺序存储

　　其他常见的存储方法还有三元组法和十字链表法

　　11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表

　　12、树型结构：非线性结构。常用的树型结构有树和二叉树。

　　二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

　　13、树(森林)与二叉树之间的转换(要会转换)

　　14、二叉树和树的周游(遍历)

　　二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN)

　　周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游

　　树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同

　　按广度优先方式就是层次次序周游

　　相关推荐：

　　2014年计算机等考上机六大注意事项

　　2014年计算机三级数据库技术重点笔记汇总

　　2014年计算机三级数据库技术上机试题及答案汇总