2012计算机三级考试数据库考点串讲资料2

会计考友

第二章 数据结构算法
1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位
2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算
3、主要的数据存储方式：顺序存储结构（逻辑和物理相邻，存储密度大）和链式存储结构
顺序存储结构：
顺序存储计算公式 Li＝L0＋(i－1)×K  顺序结构可以进行随机存取；插人、删除运算会引起相应节点的大量移动
( }& G5 m+ m# c6 w   链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小
                 b、逻辑上相邻的节点物理上不一定相邻。  c、插人、删除等不需要大量移动节点
4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2（插入）和（n-1）/2（删除）。
4 a0 A/ j! K# q( w$ L5、链表：线性链表（单链表和双向链表等等）和非线性链表
线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。（注意结点的插入和删除操作）
+ g# j& Q; w5 V. p! g( U6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等
7、队列：“先进先出”线性表。应用：树的层次遍历
) [2 {1 ^  c2 C7 x% M/ J8、串：由零个或多个字符组成的有限序列。
9、多维数组的顺序存储：
10、稀疏矩阵的存储：下三角矩阵顺序存储
其他常见的存储方法还有三元组法和十字链表法
11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表
3 e% d& S& ]$ O* T12、树型结构：非线性结构。常用的树型结构有树和二叉树。
  n! r) f8 w, w# t) q- U& T( K二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
9 w  I7 E, N* ~* @13、树（森林）与二叉树之间的转换（要会转换）
14、二叉树和树的周游（遍历）
   二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN)
   周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游
/ s$ ~; c  X# `5 [   树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同
) z2 y$ e& h+ x) Y5 @9 S  按广度优先方式就是层次次序周游
7 d, |! j* {4 f4 b4 i$ ~! B" b15、二叉树的存储和线索
   二叉树的存储结构：二叉树的llink一rlink法存储表示
- n/ u* \6 G8 U- u   线索二叉树：在有n个节点的二叉树的且llink - rlink法存储表示中，必定有n+1个空指针域
! D. @( I/ b( q5 y3 J) w16、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。
  ^' p& |1 `" v% q. a( P  v17、查找：
# w! A  L3 M5 Y6 [; X: e（1）顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)
) o' E3 C+ X% r* r; N) E6 E（2）二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+1
9 c% A! N* t- K; o（3）分块查找：先是块间查找，然后块内查找。
（4）散列表（哈希表Hash）的存储和查找：处理冲突的方法：开地址法（线性探测法）、拉链法等
负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数（即表长）
二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度O（log2n）
( G/ ~! \8 c4 w: E# eB树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。
18、排序
   直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。
直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序