数据库系统工程师考点知识精讲

《数据库系统工程师考点知识精讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章：数据结构与算法　　1、线性表的定义及特点　　线性表是若干数据元素组成的有限集合。　　线性表的特点是，有惟一的起始结点和惟一的终端结点，其它元素都有惟一的直接前驱和惟一的直接后继。　　线性表的抽像数据类型定义包括2方面：　　数据对象、关系的定义；　　线性表有关操作的定义；　　线性表的数据对象是具有相同性质数据元素的集合。　　线性表的有关操作有：　　基本操作：初始化线性表、撤消线性表、判/置空表、取表长、取前驱元素、取后继元素、取第i个元素、遍历等。　　插删操作：在顺序结构下，结点的插入（n/2）和删除[（n-1）/2]

2、主要是进行元素的移动；在链式结构下，结点的插删是调整指针的指向。　　查找操作：在顺序表中可以进行折半查找，在链表中只能进行顺序查找。　　2、线性表的基本存储结构及特点，线性表有顺序和链式两种存储结构。　　顺序存储结构是：用一组地址连续的存储单元依次存储线性表中的数据元素。　　链式存储结构是：用一组地址任意的存储单元存储线性表中的数据元素。（存储单元节点可以是连续的，也可以是不连续的）。　　链式存储结构包括：　　单链表（又称线性链表），结点的结构体有两个域，分别存储数据元素和当前元素有关系的其它元素所在结点的指针。　　双向链表

3、，每个结点包含两个指针，分别指明直接前驱和直接后继元素，可以在两个方向上遍历其后及其前的元素。　　循环链表，链表中最后一个结点的指针指向第一个结点，开成环状结构，可以在任意位置上方向不变地遍历全表。　　静态链表，借助数组描述线性表的链式存储结构。　　3、栈的定义：是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。　　栈的特点：是先进后出（FILO）。在线结构中，允许进行插、删操作的一端称为栈顶，相应另一端称为栈底。不含数据的栈称为空栈。　　栈的基本运算有：置空栈、判空栈、元素入栈、出栈和读取栈顶元素的值。　　栈的

4、存储结构：顺序栈和链栈。　　顺序栈指，用一组连续的存储单元依次存储自栈顶到栈底的元素，同时设置指针top指示栈顶元素的位置。顺序栈的空间容量是有限的，要预先定义。顺序栈的入栈和出栈操作是通过修改数组下标来完成。假设栈底对应于数组下标较大的一端，那么在元素入栈时就是下标减1,而元素出栈时就是下标加1。　　链栈，类似于线性链表，栈顶指针就是链表首结点的位置，元素的插删操作限定在首结点处进行。　　栈的应用：表达式计算，数制转换，括号匹配，迷宫问题，递归问题。　　4、队列的定义：是一种先进先出（FIFO）的线性表。　　队列的特点：它

5、只允许在表的一端插入元素而在表的另一端删除元素。在队列中允许插的一端叫队尾（rear），允许删的一端叫队头（front）。　　队列的基本运算：置队空、判队空、入队、出队、读队头元素等。　　队列的存储结构：顺序队列和链队列。　　顺序队列，又被叫作循环队列，设顺序队列Q,Q.front表示队头指针，Q.rear表示队尾指针，则Q.front和Q.rear相等且为0时为空队列；元素入队时Q.rear加1,元素出队时Q.front加1.因为顺序队列的空间容量是提前设定的，所以当Q.rear达到了上限时表示队列满。    为区别队列空

6、和队列满两种情况下可能出现的Q.front==Q.rear,有两种方法。一个是设置一个标识位，以区别头尾指针相同时队列是空还是满；另一个方法是牺牲一个元素空间，约定以Q.rear所指的下一个位置是Q.front时表示队列满。　　链队列，链队列为空的判定条件是头尾指针相同且均指向头结点。　　队列的应用：常用于需要排队的场合，如操作系统中的打印队列，离散事件的复读机模拟等。　　5、串的定义：是仅由字符构成的有限序列。是取值范围受限的线性表。一般记为S='a1a2an'。　　串的几个概念：空串、空格串、子串、串相等、串比较。　　串

7、的几个操作：赋值操作StrAssign（s,t）、联接操作Concat（s,t）、求串长StrLength（s）、串比较StrCompare（s,t）、求子串SubString（s,start,len）。　　串的存储：静态存储（顺序存储），是定长的存储结构。当串超长时，超过部分将被截断。　　堆存储，通过程序语言提供的字符数组定义串的存储空间，事先不限定串的长度，在程序执行过程中动态地申请地址连续的串值的空间。　　块链存储，使用链表存储串值，每个结点可以存储一个或多个字符，同时每个结点设置一个指针指向后继结点。　　串的模式匹配

8、：朴素的模式匹配法、KMP算法。　　6、数组：是定长线性表在维数上的扩张，即线性表中的每个元素又是一个线性表。N维数组是一种同构的数据结构，其每个数据元素类型相同，结构一致。　　数组的特点：数组元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化；　　数据元素具有相同的类型；　　数据