《数据结构考试重点必背》由会员分享，可在线阅读，更多相关《数据结构考试重点必背（12页珍藏版）》请在金锄头文库上搜索。
1、第一章：绪论1.1 :数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及 各种操作的算法设计。1.2 :数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机 接收的各种集合的统称。数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位数据项：是数据元素中有独立含义的、不可分割的最小标识单位。数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合 上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。1.4 :数据元素及其关系在计算机中的存储
2、表示称为数据的存储结构，也称为物理结构。数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问 题的操作序列。算法规则需满足以下五个特性：输入算法有零个或多个输入数据。输出算法有一个或多个输出数据，与输入数据有某种特定关系。有穷性一一算法必须在执行又穷步之后结束。确定性一一算法的每个步骤必须含义明确，无二义性。可行性一一算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和 纸做有穷次就可以完成。有穷性和可行性是算法最重要的两个特征。2.2 :算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法
3、来描述。算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。2.3 :算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结 高时间效率：算法的执行时间越短，时间效率越高。果。高空间效率：算法执行时占用的存储空间越少，空间效率越高。可读性：算法的可读性有利于人们对算法的理解。2.4 :度量算法的时间效率，时间复杂度，（课本39页）。2.5 :递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：至少有一条初始定义是非递归的，如1 ！ =1.由已知函数值逐步递推计算出未
4、知函数值，如用（n-1）！定义n ！。第二章：线性表1.1线性表：线性表是由n（n=0）个类型相同的数据元素a0,a1,a2,.an-1,组成的有限 序列,记作：LinearList = （a0,a1,a2,.an-1）其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数， 成为线性表长度。若n=0，则LinearList为空表。若n0，则a0没有前驱元素，an-1 没有后继元素，ai（ 0in-1）有且仅有一个直接前驱元素ai-1和一个直接后继元素 ai+1。1.2线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内 存的物理存储次序与它们在线性表中
5、的逻辑次序相同。线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为Loc（ a0），则 ai 的存储地址 Loc（ ai）为:Loc（ ai）= Loc（ a0）+ i*c数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素, 元素地址是下标的线性函数。1.3 :顺序表的插入和删除操作要移动数据元素。平均移动次数是属数据表长度的一半。（课本第50页）1.4 :线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数 据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。它有两个域组成：数据域和地址域。通常成为节点。（
6、课本第55页及56页）1.5单链表（课本56页）单链表的遍历:Node p = head; while（p!=null）访问 p 节点；p = p.next;单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。冷冷冷册口都偷冷冷冷一f(head HH nu=) NodeAEV q H new NodeAEV(x)； head H new NodeAEV(x)； q.nexr-l-H p.rlexu)e_se p.nexr-l-H qNodeAEV qnnew NodeAEV(x)#画mswm-B q.nexr-l-H head;s* 骅Thead。head H q-浮崖
7、编-head H head.nexr;#画 fwJW沙二f(p nexrITnu=) p.nexr-l-H p.nexLnexea-B藩-君湖藩淅珈训今击汕昏nexr-l-落4n藩昏浮碰母head fi、wsf(s 67)fflrear湖藩淅昏瑚碰母、目吾令(rear-nexw head;)丽回、演*藩殊苛滴al 藩。联 head.nexwHhead 枝、a-B苛明。联 head.nexrHHnu-一 枝、沼藩苛附。沛 PK回浸浦-#JLm3ffis*3、=DT、ws-71湮* 演-PHP.nexLprevHp.prev.nexr。沼藩sm君崖编二)m2)崖编qHnewDL-nkNode(x)
8、- qprevHPpreqmexr-l-HP- pprevmexr-l-H qpprevnq-pprevmexr-l-H pmex；一f(pmexrnnu=)(pmexn-prev Hppre=0,s是串名，一对双引号括起来的字符序列 s0s1s2.sn-1是串值，si（i=0，1，2，.n-1）为特定字符集合中的一个字符。一个串 中包含的字符个数称为串的长度。长度为0的串称为空串，记作，而由一个或多个空格字符构成的字符串称为空格串。子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。 子串的序号是指该子串的第一个字符在主串中的序号。串比较：两个串可比较是否相等，
9、也可比较大小。两个串（子串）相等的充要条件是 两个串（子串）的长度相同，并且各对应位置上的字符也相同。两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依 次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较大。第五章：数组和广义表1.1 :数组是一种数据结构，数据元素具有相同的数据类型。一维数组的逻辑结构是线 性表，多维数组是线性表的扩展。1.2 :一维数组：一维数组采用顺序存储结构。一个一维数组占用一组连续的存储单元设数组第一个元素a0的存储地址为Loc（ a0），每个元素占用c字节，则数组其他元 素 ai 的存储地址 Loc（ ai）为：Loc（ ai
10、）= Loc（ a0）+i*c数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元 素，所划给的时间是O（ 1）。因此数组是随机存取结构，这是数组最大的优点。1.3 :多维数组的遍历：有两种次序：行主序和列主序。行主序：以行为主序，按行递增访问数组元素，访问完第行的所有元素之后再访问第 i+1行的元素，同一行上按列递增访问数组元素。a00,a01,.a0(n-1), a10,a11,.a1(n-1),.a(m-1)0,a(m-1)1,.,a(m-1)(n-1)2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的所有元素之后再 访问第j+1列的元素，同一列上按列递增
11、访问数组元素。多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两 种。静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。按行主序存储时，元素aij的地址为：Loc( aij)= Loc( a00)+( i*n+j)*c按列主序存储时，Loc( aij)= Loc( a00)+( j*m+i)*c动态多维数组的存储结构。二维数组元素地址就是两个下标的线性函数。无论采用哪种存储结构，多维数组都 是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除 操作。第六早.树是数据元素(结点)之间具有层次关系的m核戋性结构。在树结构中，除根以外的结 点只有
12、一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。树是由n(n=0 )个结点组成的有限集合(树中元素通常称为结点)。N=0的树称为 空树；n0大的树T;有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。除根结点之外的其他结点分为m ( m=0 )个互不相交的集合T0,T1,T3.,Tm-1 , 其中每个集合Ti ( 0 = im )本身又是一棵树，称为根的子树。树是递归定义的。结点是树大的基本单位，若干个结点组成一棵子树，若干棵互不相 交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点 组成的、结点之间具有层次关系大的非线性结构。结点的前驱结点称为其
13、父母结点，反之，结点大的后继结点称为其孩子结点。一棵树 中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父 母结点所经过大的所有结点。结点的后代是指该结点的所有孩子结点，以及孩子的孩结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树 中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度 是指树中各结点度的最大值。结点的层次属性反应结点处于树中的层次位置。约定根结点的层次为1，其他结点的 层次是其父母结点的层次加1。显然，兄弟结点的层次相同。树的高度或深度是树中结点的最大层次树。设树中X结点是y结点的父母结点，有序对（x，y）称为连接这两个结点的分支，也 称为边。设（X0,X1,.,Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（ 0=i=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树， 将树的根节点删除就变成森林。二叉树的性质1 ：若根结点的层次为1，则二叉树
