《数据库系统工程师考点知识精讲》由会员分享，可在线阅读，更多相关《数据库系统工程师考点知识精讲（16页珍藏版）》请在金锄头文库上搜索。
1、第二章：数据结构与算法1、线性表的定义及特点线性表是若干数据元素组成的有限集合。线性表的特点是，有惟一的起始结点和惟一的终端结点，其它元素都有惟一的直接前驱和惟一的直接后继。线性表的抽像数据类型定义包括2方面：数据对象、关系的定义；线性表有关操作的定义；线性表的数据对象是具有相同性质数据元素的集合。线性表的有关操作有：基本操作：初始化线性表、撤消线性表、判/置空表、取表长、取前驱元素、取后继元素、取第i个元素、遍历等。插删操作：在顺序结构下，结点的插入（n/2）和删除（n-1）/2主要是进行元素的移动；在链式结构下，结点的插删是调整指针的指向。查找操作：在顺序表中可以进行折半查找，在链表中只能
2、进行顺序查找。2、线性表的基本存储结构及特点，线性表有顺序和链式两种存储结构。顺序存储结构是：用一组地址连续的存储单元依次存储线性表中的数据元素。链式存储结构是：用一组地址任意的存储单元存储线性表中的数据元素。（存储单元节点可以是连续的，也可以是不连续的）。链式存储结构包括：单链表（又称线性链表），结点的结构体有两个域，分别存储数据元素和当前元素有关系的其它元素所在结点的指针。双向链表，每个结点包含两个指针，分别指明直接前驱和直接后继元素，可以在两个方向上遍历其后及其前的元素。循环链表，链表中最后一个结点的指针指向第一个结点，开成环状结构，可以在任意位置上方向不变地遍历全表。静态链表，借助数组
3、描述线性表的链式存储结构。3、栈的定义：是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的特点：是先进后出（FILO）。在线结构中，允许进行插、删操作的一端称为栈顶，相应另一端称为栈底。不含数据的栈称为空栈。栈的基本运算有：置空栈、判空栈、元素入栈、出栈和读取栈顶元素的值。栈的存储结构：顺序栈和链栈。顺序栈指，用一组连续的存储单元依次存储自栈顶到栈底的元素，同时设置指针top指示栈顶元素的位置。顺序栈的空间容量是有限的，要预先定义。顺序栈的入栈和出栈操作是通过修改数组下标来完成。假设栈底对应于数组下标较大的一端，那么在元素入栈时就是下标减1,而元素出栈时就是下标加1。链栈，类似
4、于线性链表，栈顶指针就是链表首结点的位置，元素的插删操作限定在首结点处进行。栈的应用：表达式计算，数制转换，括号匹配，迷宫问题，递归问题。4、队列的定义：是一种先进先出（FIFO）的线性表。队列的特点：它只允许在表的一端插入元素而在表的另一端删除元素。在队列中允许插的一端叫队尾（rear），允许删的一端叫队头（front）。队列的基本运算：置队空、判队空、入队、出队、读队头元素等。队列的存储结构：顺序队列和链队列。顺序队列，又被叫作循环队列，设顺序队列Q,Q.front表示队头指针，Q.rear表示队尾指针，则Q.front和Q.rear相等且为0时为空队列；元素入队时Q.rear加1,元素出
5、队时Q.front加1.因为顺序队列的空间容量是提前设定的，所以当Q.rear达到了上限时表示队列满。 为区别队列空和队列满两种情况下可能出现的Q.front = Q.rear,有两种方法。一个是设置一个标识位，以区别头尾指针相同时队列是空还是满；另一个方法是牺牲一个元素空间，约定以Q.rear所指的下一个位置是Q.front时表示队列满。链队列，链队列为空的判定条件是头尾指针相同且均指向头结点。队列的应用：常用于需要排队的场合，如操作系统中的打印队列，离散事件的复读机模拟等。5、串的定义：是仅由字符构成的有限序列。是取值范围受限的线性表。一般记为S = a1a2an。串的几个概念：空串、空格
6、串、子串、串相等、串比较。串的几个操作：赋值操作StrAssign（s,t）、联接操作Concat（s,t）、求串长StrLength（s）、串比较StrCompare（s,t）、求子串SubString（s,start,len）。串的存储：静态存储（顺序存储），是定长的存储结构。当串超长时，超过部分将被截断。堆存储，通过程序语言提供的字符数组定义串的存储空间，事先不限定串的长度，在程序执行过程中动态地申请地址连续的串值的空间。块链存储，使用链表存储串值，每个结点可以存储一个或多个字符，同时每个结点设置一个指针指向后继结点。串的模式匹配：朴素的模式匹配法、KMP算法。6、数组：是定长线性表在维
7、数上的扩张，即线性表中的每个元素又是一个线性表。N维数组是一种同构的数据结构，其每个数据元素类型相同，结构一致。数组的特点： 数组元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化；数据元素具有相同的类型；数据元素的下标关系受上下界的约束且下标有序。数组的基本运算：给定一组下标，存取相应的数据元素；给定一组下标，修改相应的数据元素中的某个数据项的值。数组的存储： 数组的固定结构适于使用顺序存储。对于数组，只要知道它的维数和长度，就可以为它分配存储空间。反之，只要给出一组下标就可以求出该数组元素的存储位置。就是说，在数组的顺序存储结构中，数据元素的位置是其下标的线性函数。以行为主序； L
8、oc（Aij） = Loc（Aij） + （i-1）*n + （j-1）*L以列为主序； Loc（Aij） = Loc（Aij） + （j-1）*m + （i-1）*L多维数组的顺序存储计算：例如3维数组A110, 58, -36,数组空间的起始位置是a,每个元素占4个存储单元，试以行为主存储和以列为主存储时给出数组元素Ai,j,k的存储地址。解：理解上面给出的以行为主序和以列为主序的两个线性函数公式。把3维数组拆开计算，例如以行为主序时先将3维数组看成是有一个行和2个列的数组，算出此时以行为主占用了多少空间。然后再单独看两个列的组合Bj,k又会占用多少空间。前后结果相加就是这个3维数组元素在
9、以行为主序存储时的地址。如下，以行为主序时，Ai,j,k前面的元素个数是： （i-1）（8-5+1）（6-（-3）+1） + （j-5）（6-（-3）+1） + k-（-3） = 40i-40 + 10j-50 + k+3 = 40i + 10j + k -87因此Ai,j,k的地址为a + （40i+10j+k-87）*4以列为主序时，Ai,j,k的地址为a + （40k+10j+i+69）*47、特殊矩阵与稀疏矩阵，稀疏矩阵就是非零元素很少的矩阵，而特殊矩阵是非零元素分布有规律的一类矩阵。为节省空间，在存储它们时都使用压缩存储，特殊矩阵有压缩算法，稀疏矩阵使用三元组顺序表或使用十字链表存储
10、矩阵元素。8、广义表的定义：是由零个或多个单元素或子表所组成的有限序列。广义表的长度是指广义表中元素的个数，深度是指广义表展开后所含的括号的最大层数。广义表的基本运算：取表头head（LS），非空广义表的第一个元素称为表头；取表尾tail（LS），非空广义表中除第一个元素之外，由其余元素构成的表称为表尾。表尾必定是一个表。Head（LS）=a1, Tail（LS）=（a2,a3,，an）9、树的定义：树是n（n=0）个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余m个结点可分为m（m=0）个互不相交的有限集，其中每个子集合又都是一棵树，称为根结点的子树。树的
11、定义是递归的，树形结构具有明显的层次结构。树的术语：双亲和孩子，兄弟，结点的度，叶子结点，内部结点，结点的层次，树的高度，有序树和无序树，森林。树的基本操作是：先根遍历和后根遍历。10、二叉树的定义：二叉树是另一种树形结构，它的特点是每个结点至多有两棵子树并且有左右之分，且左、右子树的次序不能颠倒。满二叉树，若二叉树上每一层的结点数目都达到最大值，则称为满二叉树；完全二叉树，若二叉树的除第H层以外，其余各层的结点数目达到了最大值，而第H层上的结点集中存放在左侧，则称为完全二叉树；非完全二叉树，就是完全二叉树的相反情况。二叉树的性质： 1）二叉树第i层（i=1）上至多有2（i-1）个结点。2）深
12、度为K的二叉树至多有2k -1 个结点（k=1）。3）对任何一棵二叉树，若其终端结点个数为N0,度为2的结点个数为N2,则N0 = N2 + 1 。4）具有n个结点的完全二叉树的深度为log（2,n）+1。5）对一棵有n个结点的完全二叉树的结点按层次自左至右进行编号，则对任一结点i （1=i1则其双亲为i/2。若2in,则结点i无左孩子，否则其左孩子为2i。若2i+1n,则结点i无右孩子，否则其右孩子为2i+1。例：一棵有124个叶结点的完全二叉树，最多有多少结点？N0=N2+1N=N0+N1+N2N1=1综合上面3个表达式可以求解。例2:具有N个结点的满二叉树，其叶子结点个数为多少？设其深度
13、为h,则： N0=2（h-1）N = 2h - 1所以N0 = （n+1）/2二叉树的存储结构：二叉树的顺序存储结构，若采用二叉树的性质5对树中的结点进行编号，即树根结点的编号为1,若编号为i的结点存在左孩子，则其左孩子的编号为2i;若编号为i的结点存在右孩子，则其右孩子的编号为2i+1,这样利用数组元素的下标作为结点的编号，表示出结点间的关系。二叉树的链式存储结构，二叉链表（有单向性）和三叉链表（有双向性）。遍历二叉树，有4种方式：先序、中序、后序和层序遍历。先序遍历二叉树的操作定义为：访问根结点；先序遍历根的左子树；先序遍历根的右子树。（若二叉树为空，则进行空操作）。中序遍历二叉树的操作定
14、义为：中序遍历根的左子树；访问根结点；中序遍历根的右子树。（若二叉树为空，则进行空操作）。后序遍历二叉树的操作定义为：后序遍历根的左子树；后序遍历根的右子树；访问根结点。层序遍历二叉树的操作定义为：从根结点开始，从或到右依次访问每层上的结点。二叉树遍历思想的关键：首先在想象中把二叉树补齐为满二叉树，叶子结点也要被想象为有2个子结点。然后，画一条路线，从根出发，逆时针沿着二叉树的外缘移动，全程对每个结点均途经三次。若第一次经过时即访问，则是先序遍历；若是第二次经过结点时访问结点，则是中序遍历；若是第3次经过时访问则是后序遍历。这3种方法的路径相同，但结果不同。遍历二叉树的基本操作就是，访问结点。
15、-遍历二叉树实质上是按一定规则，将树中的结点排成一个线性序列。11、线索二叉树：对于有N个结点的二叉树的二叉链表存储表示，其中必有N+1个空指针。遍历时使结点中原本为空的左孩子指针或（和）右孩子指针指向结点的前驱或（和）后继，这样的处理称为对二叉树的线索化，指向前驱或后继的指针称为线索。加上线索的二叉树称为线索二叉树。为了区分结点中的指针是孩子还是线索，在结点结构中增加标志域ltag, rtag。两个标志取值0,则lchild,rchild域分别指向左孩子和右孩子；两个标志取值1,则lchild,rchild域分别指向直接前驱和直接后继。访问线索二叉树时，如何查找结点的前驱和后继？以中序线索二叉树为例，令P指向树中的某个结点。当p-ltag =
