第一章 数据结构与算法
! C* G/ R* {* a& D& j- @+ P0 b( d5 z
算法---是一组严谨地定义运算顺序的规则 % e& x+ C6 Y: ~* M* i
算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构
5 ^7 I5 A; {; n8 u% U 算法设计基本方法---列举法、归纳法、递推、递归、减半递推
2 V7 j( p8 k) S8 I; \ 算法的复杂度---包括时间复杂度和空间复杂度 - c/ m4 B6 r9 \# o! }
时间复杂度---执行算法所需的计算工作量
; n J5 d, Y3 K! D7 L G 空间复杂度---执行算法所需的内存空间 ) A+ \1 c2 u+ s5 r' F' C+ b, G
数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父亲、儿子、女儿等都是数据元素。 % L' V% Z c0 D( N: t
前件---数据元素之间的关系，如父亲是儿子和女儿的前件 4 f1 E8 n9 W; f4 M. x
后件---如儿子是父亲的后件
$ A) Y- }4 Z" l$ |! X 结构---指数据元素之间的前后件关系 $ f! O. W' f5 k, S7 u, ]" S3 y& l
数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关
- v4 \- _0 I6 X! ^! X: y' S$ l 数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。 / q; H+ x. J4 E
根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与非线性结构 / K% z5 H& ?6 C6 P7 f
线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件和后件。则称该数据结构为线性结构，否则为非线性结构。 - R( m9 w& f) z3 [8 t2 p
线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组
& L: l; \6 ~5 N2 ~# ]% e 栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈的运算有入栈、退栈、读栈顶元素
4 Q( k9 U) A6 f 队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操作规则是“先进先出”，其运算有入队和退队。 & C4 x3 q- i4 A# p3 J7 ~- L
树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结点、叶子结点。根结点在第一层，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为 树的度，树的最大层次称为树的深度。 5 z+ c% ~" F5 d/ \
二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式。 + J3 b" B/ O2 `2 `
二叉树性质---（1）K层上最多有2（K-1）个结点（2）深度为m的二叉树最多有2m-1个结点 ! E+ ~* z$ K: O3 `9 H
（3）度为0的结点（叶子结点）比度为2的结点多一个（4）具有n个结点的二叉树，其深度至少为[Log2n]+1，其中[Log2n]表示对Log2n取整
6 B. J# [, I* B$ h3 c" P' I 满二叉树---除最后一层外，其余层的结点都有两个子结点 : T; ]. {; \5 _9 r2 Z! _
完全二叉树---除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点，叶子结点只可能在层次最大的两层上出现。满二叉树是完全二叉树，而完全二叉树不是满二叉树。完全二叉树有两个性质：（1）具有n个结点的完全二叉树的深度为[Log2n]+1（2）
! a* n; c8 L, X+ S4 J7 F 二叉树遍历---不重复地访问各个结点。分为前序遍历(DLR-根左右)、中序遍历(LDR-左根右)和后序遍历（LRD-左右根） , }: i0 }# T" Y2 r" {
查找技术---顺序查找——对于长度为n的有序线性表，查找时需要比较n次
- G1 `) p8 `8 r 二分法查找——对于长度为n的有序线性表，查找时需要比较log2n次 7 F) L W4 o9 B, o
排序技术---假设线性表的长度为n，则冒泡排序和简单插入排序的比较次数（时间复杂度）为n(n-1)/2;希尔排序的比较次数为O(n1.5);简单选择排序的比较次数为n(n-1)/2;堆排序的比较次数为O(nlog2n).
5 I$ {; U3 P8 M: W习题1
$ q4 d2 A X) [$ s 算法的时间复杂度是指（ ），算法的空间复杂度是指（ ）； 8 ?; v. L2 V7 w1 u/ ~" Q6 L9 v
队列是（先进先出），栈是（先进后出）； 6 Y$ t! s& L( F% o# `, |5 K) ]
下列二叉树的遍历结果：前序遍历（ABDECF）、中序遍历（DBEAFC）、后续遍历（DEBFCA）； 
U6 v1 J+ s7 g! U* C 在深度为5的满二叉树中，叶子结点的个数为（16）；设树T的度为4，其中度为1，2，3；
/ C& y8 N/ e) x, C2 O8 w+ x 线性表、栈、队列、线性链表是（线性结构），树是（非线性结构）；数据的存储结构是指（ ）；，4的结点的个数分别为4，2，1，1。则T中的叶子结点的个数为（8）；对于长度为n的有序线性表，顺序查找次数为（n）,二分法查找次数为（log2n）；一棵完全二叉树共有700个结点，则在该二叉树中有（350）个叶子结点；一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后续遍历结果为（DEBFCA）；冒泡排序的时间复杂度为（n(n-1)/2）;在一个容量为15的循环队列中，若头指针front=6,尾指针rear=9,则该循环队列中共有（3）元素； |
发表于 2012-7-31 21:44:12
