2012年计算机二级考试公共基础知识：数据结构与算法要点

会计考友

第一章　数据结构与算法
" D/ d9 y! F" g0 Z1 v7 _: r" J1.1 算法
. e; c7 O1 L4 N
　　算法：是指解题方案的切确而完整的描述。
, J* d6 S6 {" Z! o+ D  l8 R　　算法不等于轨范，也不等计较机体例，轨范的编制不成能优于算法的设计。
　　算法的根基特征：是一组严谨地界耸ё偎算挨次的轨则，每一个轨则都是有用的，是明晰的，此挨次将在有限的次数下终止。特征搜罗：
　　（1）可行性；
　　（2）确定性，算法中每一轨范都必需有明晰界说，不充许有迷糊其词的诠释，不许可有多义性；
! {. ~0 R3 a) J2 C　　（3）有穷性，算法必需能在有限的时刻内做完，即能在执行有限个轨范后终止，搜罗合理的执行时刻的寄义；
　　（4）拥有足够的情报。
# E: _5 C. q) t- ]; O6 f, J　　算法的根基要素：一是对数据对象的运算和操作；二是算法的节制结构。
0 }& i" I# t4 a/ n/ r　　指令系统：一个计较机系统能执行的所有指令的集结。
　　根基运算搜罗：算术运算、逻辑运算、关鲜ё偎算、数据传输。
7 ]# r4 _+ {6 G　　算法的节制结构：挨次结构、选择结构、轮回结构。
　　算法根基设计体例：列举法、归纳法、递推、递归、减斗递推手艺、回溯法。
　　算法复杂度：算法时刻复杂度和算法空间复杂度。
# l5 c& b4 }' k1 f" y: A　　算法时刻复杂度是指执行算法所需要的计较工作量。
  Q5 a3 v% H3 b: m　　算法空间复杂度是指执行这个算法所需要的内存空间。

会计考友

1.2 数据结构的根基概念
3 f: H; I1 j! c( ^! N0 p　　数据结构研究的三个方面：
　　（1）数据集结中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
: w8 }9 ?) _4 |7 _9 t8 R　　（2）在对数据进行措置时，各数据元素在计较机中的存储关系，即数据的存储结构；
　　（3）对各类数据结构进行的运算。
# V& \, a# m* @4 `  I3 `& U2 k　　数据结构是指彼此有联系关系的数据元素的集结。
) {) s0 z1 F3 Z' j& z5 D　　数据的逻辑结构包含：
　　（1）暗示数据元素的信息；
1 A. ?5 a" ~5 t　　（2）暗示各数据元素之间的前后件关系。
$ q% ?: }2 C1 E" B8 k% x　　数据的存储结构有挨次、链接、索引等。
6 E. u! c5 J1 C# {6 F　　线性结构前提：
+ y% S9 K6 B# |' T　　（1）有且只有一个根结点；
　　（2）每一个结点最多有一个前件，也最多有一个后件。
/ I! e4 m/ J% {, z1 r9 i5 l% n　　非线性结构：不知足线性结构前提的数据结构。 1．3 线性表及其挨次存储结构
8 A, Y. r+ b, W/ H. h　　线性表是由一组数据元素组成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
; R! X+ S9 N5 _　　在复杂线性表中，由若干项数据元素组成的数据元素称为记实，而由多个记实组成的线性表又称为文件。
　　非空线性表的结构特征：
　　（1）且只有一个根结点a1，它无前件；
. g3 B9 @2 T6 c　　（2）有且只有一个终端结点an，它无后件；
　　（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。
, [  ^% I6 _; R& |　　线性表的挨次存储结构具有以下两个根基特点：
2 Y# o& s  G8 e　　（1）线性表中所有元素的所占的存储空间是持续的；
　　（2）线性表中各数据元素在存储空间中是按逻辑挨次依次存放的。
　　ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 　　挨次表的运算：插入、删除。