数据库系统工程师——第三章 数据结构与算法

第三章、数据结构与算法

数据结构是指数据元素的集合及元素间的相互关系和构造方法结构就是元素之间的关系。在数据结构中元素之间的相互关系是数据的逻辑结构。按照逻辑关系的不同将数据结构分为线性结构和非线性结构其中线性结构包括线性表、栈、队列、串非线性结构主要包括树和图。数据元素及元素之间关系的存储形式称为存储结构主要有顺序存储和链式存储两种基本方式。

3.1 线性结构

线性结构的特点是数据集合中的元素之间是一种线性关系数据元素“一个接一个地排列”也就是一个序列。

3.1.1 线性表

线性表是指一个序列常采用两种存储方法:顺序存储和链式存储主要的基本操作是插入、删除和查找。

线性表的定义

一个线性表是n个有限序列n≥0通常表示为( a1 , a2 , … , an )其特点是在非空的线性表中

a存在唯一的一个称作“第一个”的元素
b存在唯一的一个称作“最后一个”的元素
c除第一个元素外序列中的每个元素均只有一个直接前驱
d除最后一个元素外序列中的每个元素均只有一个直接后继。

线性表的存储结构 ⭐ ⭐ ⭐

线性表的顺序存储
指用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。这种存储方式下元素间的逻辑关系无须占用额外的空间来存储。

优点可以随机存取表中的元素按序号查找元素的速度很快
缺点插入和删除操作需要移动元素。

一般地以 LOC(a)表示线性表中第一个元素的存储位置L表示每个元素所占空间的大小
则顺序存储结构中第i个元素a的存储位置为:
 
LOC(a)=LOC(a)+(i-1)* L

线性表的链式存储链表

线性表的链式存储用节点来存储数据元素元素的节点地址可以连续也可以不连续因此存储数据元素的同时必须存储元素之间的逻辑关系。另外节点空间只有在需要的时候才申请无须实现分配基本的节点结构

数据域存储数据元素的值指针域存储当前元素的直接前驱或直接后继元素的位置信息指针域中所存储的信息称为指针或链单链表节点中只有一个指针域。

在链式存储结构中只需要一个指针指向第一个结点就可以按照链接关系顺序地访问表中的任意一个元素。 Head指针不存储实际的数据元素用于辅助数据元素的定位方便插入和删除操作。

优点链式存储结构下进行插入和删除实质是对相关指针的修改不需要移动元素
缺点只能顺序地访问元素而不能对元素进行随机存储。

链表的类别

根据节点中指针信息的实现方式有

a单链表包含两个域一个信息域和一个指针域这个链接指向列表中的下一个节点而最后一个节点则指向一个空值。 单链表存储不能随机访问表中的任一结点必须从头结点依次.next。

b双向链表每个节点包含两个指针分别指明当前元素的直接前驱和直接后继信息可在两个方向上遍历链表中的元素。

c循环链表表尾节点的指针指向表中的第一个节点可从表中任意节点开始遍历整个链表。

d) 静态链表借助数组来描述线性表的链式存储结构。

线性表的查找方法 ⭐ ⭐ ⭐

a) 顺序查找
算法非常简单但是效率较低因为它是用所给关键字与线性表中各元素的关键字逐个比较直到成功或失败。
 
b) 折半查找
优点是比较次数少查找速度快平均性能好
缺点是要求待查表是有序表且插入和删除困难。
适用于不经常变动而查找频繁的有序列表。
一般不进行表的插入和删除操作。
需要对中间元素进行快速定位在链表结构上无法实现。
 
c) 分块查找
又称索引查找主要用于分块有序表的查找。
所谓分块有序是指将线性表 L (一堆数组)分成m个子表(要求每个子表的长度相等)
且第 i+1 个子表中的每一个项目均大于第 i 个子表中的所有项目。
因此分块查找的关键在于建立索引表其查找的平均长度介于顺序查找和折半查找之间。

3.1.2 栈和队列

栈和队列是常用的两种数据结构它们的逻辑结构与线性表相同其特点在于运算受到了限制。栈按“后进先出”规则进行操作类似杯子喝水队列“先进先出”规则进行操作类似沙漏。

栈 只能通过访问它的一端来实现数据存储和检索操作按先进后出FILOFirst In Last Out或后进先出LIFO规则进行插入删除操作。在栈中进行插入和删除操作的一端成为栈顶Top另一端成为栈底Bottom。

栈的基本运算

a) 初始化栈initStack(S):创建一个空栈 S;
b) 判栈空isEmpty(S):当S为空时返回“真”值否则返回“假”值;
c) 入栈 push(S,x):将元素x 加入栈顶并更新栈顶指针;
d) 出栈 pop(S): 将栈顶元素从栈中删除并更新栈顶指针。若需要得到栈顶元素的值可将 pop(S)定义为一个函数它返回栈顶元素的值;
e) 读栈顶元素 top(S): 返回顶元素的值但不修改栈顶指针。

栈的存储结构

a) 栈的顺序存储
栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素同时附设指针 top 指示栈顶元素的位置。
采用顺序存储结构的栈也称为顺序栈。
在顺序存储方式下需要预先定义或申请栈的存储空间也就是说栈空间的容量是有限的。
因此在顺序栈中当一个元素入栈时需要判断是否栈满(栈空间中没有空闲单元)若栈满,则元素入栈会发生上溢现象。
 
b) 栈的链式存储
为了克服顺序存储的栈可能存在上溢的不足可以用链表存储栈中的元素。
用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行
因此不必设置头结点链表的头指针就是栈顶指针。

栈的应用

栈的典型应用包括表达式求值、括号匹配等在计算机语言的实现以及将递归过程转变为非递归过程的处理中栈有重要的作用。

函数调用和返回控制是用栈实现的。 ⭐ ⭐ ⭐

队列 是一种先进先出FIFOFirst In First Out线性表只允许在标的一段插入元素而在标的另一端删除元素。允许插入元素的一端称为队尾允许删除元素的一端称为对队头。

队列的基本运算

a初始化队列 initQucue(Q): 创建一个空的队列 Q
b判队空 isEmpty(Q):当队列为空时返回“真”值否则返回“假”值
c入队 enQueue(Q,x):将元素 x 加入到队列Q的队尾并更新队尾指针
d出队 deQueue(Q):将队头元素从队列Q 中删除并更新队头指针
e读队头元素 frontQucue(Q): 返回队头元素的值但不更新队头指针。

队列的存储结构

a) 队列的顺序存储
队列的顺序存储结构又称为顺序队列由于队中元素的插入 和删除限定在表的两端进行因此设置队头指针和队尾指针分别指示出当前的队首元素和队尾元素。
在顺序队列中为了简化运算元素入队时只修改队尾指针;元素出队时只修改队头指针。
由于顺序队列的存储空间是提前设定的因此队尾指针会有一个上限值当队尾指针达到其上限时
就不能只通过修改队尾指针来实现新元素的入队操作了。此时可将顺序队列假想成一个环状结构称之为循环队列。
 
b) 队列的链式存储
队列的链式存储也称为链队列。为了便于操作可给链队列添加一个头结点并令头指针指向头结点因此队列为空的判定条件是头指针和尾指针的值相同且均指向头结点。

队列的应用

队列常用于处理需要排队的场合如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

3.1.3 串

串 是仅有字符构成的有限序列是取值范围受限的线性表。

串的基本运算

a) 赋值操作 SrAssign(s,t):将串t的值赋给串s;
b) 连接操作 Concat(s,t):将串t接续在串s的部形成一个新串;
c) 求串长 StrLength(s):返回串s 的长度;
d) 串比较 StCompare(s,t): 比较两个串的大小。返回值-1、0和1分别表示s<t、s=t 和s>t三种情况;
e) 求子串 SubString(s,start,len):返回串s中从start 开始的长度为len 的字符序列。

串的存储结构

a) 串的顺序存储
该方式是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符
所以可通过程序语言提供的字符数组定义串的存储空间(即存储空间的容量固定)
也可以根据串长的需要动态申请字符串的空间(即存储空间的容量可扩充或缩减)。
 
b) 串的链式存储
字符串也可以采用链表作为存储结构当用链表存储串中的字符时每个结点中可以存储一个字符也可以存储多个字符
需要考虑存储密度问题。

通常情况下字符串存储在一维字符数组中每个字符串的末尾都有一个串结束符在C/C++程序中以特殊字符“\0”作为结束标记。

3.2 数组和矩阵

数组可看作是线性表的推广其特点是多维数组的数据元素仍然是一个表。

数组

数组的定义及基本运算

一维数组是长度固定的线性表数组中的每个数据元素类型相同。n 维数组是定长线性表在维数上的扩张即线性表中的元素又是一个线性表。

数组结构的特点

a) 数据元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化。
b) 数据元素具有相同的类型。
c) 数据元素的下标关系具有上下界的约束且下标有序
 
在数组中通常做下面两种操作:
(1) 取值操作。给定一组下标读其对应的数据元素
(2) 赋值操作。给定一组下标存储或修改与其相对应的数据元素

数组顺序存储

由于数组一般不作插入和删除运算也就是说一旦定义了数组则结构中的数据元素个数和元素之间的关系就不再发生变动因此数组适合于采用顺序存储结构。

矩阵

在一些矩阵中存在很多值相同的元素或者是零元素。为了节省存储空间可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元对零元不分配存储单元。

矩阵分类

党见的特殊知阵有对称矩阵、三角矩阵和对角矩阵等。
a) 对称矩阵 若矩阵An*n中的元素有aij =aji 1≤ij≤n,则称之为对称矩阵。
 
特性
1.对称矩阵是一个方阵即就是行和列长度相等
2.对称矩阵中的所有元素都是相互对称的即就是矩阵的下三角和上三角是对称的
 
元素的位置
1.行=列时此时表明此元素位于对角线
2.行>列时表明此元素位于下三角中
3.行<列时表明此元素位于上三角中
 
b三对角矩阵
• 对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中其余的矩阵元素都为零。
• 下面主要考虑三对角矩阵即只有主对角线及其左右两边为非零元素。
• 若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B[k] 0≤k<3n-2中
则元素位置之间的对应关系为 k=3 × (i-1)-1+j-i+1=2i+j-3 (1≤i,j≤n)。
 
c) 稀疏矩阵 在一个矩阵中若非零元素的个数远远少于零元素的个数且非零元素的分布没有规律,则称之为稀疏矩阵。
可以用一个三元组(i,j,aij唯一确定矩阵中的一个元素。

3.3 树和图

3.3.1 树

树

树是nn≥0个节点的有限集合当n=0时称为空树在任一非空树n0中有且仅有一个称为根的节点其余节点可分为mm≥0个互不相交的有限集T1 , T2 ,…, Tm其中每个集合又是一棵树并且称为根节点的子树。

树的相关术语

a) 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点如上图中B节点是E、F节点的双亲节点
 
b) 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点如上图中B、C、D是A的子节点
 
c) 兄弟节点具有相同双亲节点的节点互称为兄弟节点B、C、D和E、F互为兄弟节点
 
d) 节点的度一个节点含有的子树的个数称为该节点的度
 
e) 叶子节点或终端节点度为0的节点称为叶子节点如上图C、E、F、G
 
f) 非终端节点或分支节点度不为0的节点
 
g) 树的度一棵树中最大的节点的度称为树的度
 
h) 节点的层次从根开始定义根为第1层根的子节点为第2层以此类推
 
i) 树的高度或深度树中节点的最大层次上图中树的深度为2
 
j) 子孙以某节点为根的子树中任一节点都称为该节点的子孙。
 
k) 有序无序树若将树中节点的各子树看成是从左到右具有次序的即不能交换则称该树为有序树否则称为无序树。
 
l) 森林mm>=0棵互不相交的树的集合

二叉树

二叉树是nn≥0个节点的有限集合它或者是空树n=0或者是由一个根节点及两颗不相交的、分别称为左子树和右子树的二叉树所组成简单来说就是度不超过2的树节点最多有两个叉。

树与二叉树的区别

a) 二叉树中节点的子树要区分左子树和右子树即使在节点只有一颗子树的情况下也要明确指出该子树是左子树还是右子树树种则不区分
b) 二叉树中节点的最大度为2而树中不限制节点的度数。

二叉树的性质

a) 二叉树第i层i≥1上至多有2^{i-1}个节点
b) 深度为k的二叉树至多有2^k-1个节点 k ≥ 1 ;
c) 对任何一棵二叉树若其终端节点数为n0度为2的节点数为n2则n0 = n2 + 1
d) 具有n个节点的完全二叉树的深度为⌊log2^n+1⌋向下取整小于等于。

满二叉树和完全二叉树

满二叉树一个二叉树深度为k每一个层的节点数都达到最大值2^k-1。

完全二叉树当深度k、有n个节点的二叉树其每一个节点都与深度为k的满二叉树中编号为1~n的节点一一对应。叶子节点只能出现在最下层和次下层并且最下面一层的节点都集中在该层最左边的若干位置的二叉树。

满二叉树一定是完全二叉树但是完全二叉树不一定是满二叉树。

二叉树的存储结构

顺序存储:

用一组地址连续的存储单元存储二叉树中的节点必须把节点排成一个适当的线性序列并且节点再这个序列中的相互位置能反映出节点之间的逻辑关系,对于深度为k的完全二叉树除第k层外其余各层中含有最大的结点数即每一层的结点数恰为其上一层结点数的两倍,由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。

假设有编号为i的结点则有:
若 i=1则该结点为根结点无双亲;若 >1则该结点的双亲结点为[i/2]
若 2i ≤ n则该结点的左孩子编号为 2i否则无左孩子
若 2+1 ≤ n则该结点的右孩子编号为2i+1否则无右孩子

显然顺序存储结构对完全二叉树而言既简单又节省空间而对于一般二叉树来说浪费空间了不适用。

在坏的情况下一个深度为h 且只有 h 个结点的二叉树(单枝树却需要2^k-1个存储单元。

链式存储:

由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息因此可以用三叉链表或二叉链表即一个节点含有3个指针或2个指针来存储二叉树链表的头指针指向二叉树的根节点。
二叉树的遍历

遍历是按某种策略访问树中的每个节点且仅访问一次。

按照遍历左子树要在遍历右子树之前进行的约定依据访问根节点的位置的不同可以得到二叉树的前序、中序和后序三种遍历方法。

a) 前序遍历根→左→右
访问根结点的操作发生在遍历其左右子树之前若二叉树非空操作步骤
(1)访问根节点(2)遍历左子树(3)遍历右子树。
 
b) 中序遍历左→根→右
访问根结点的操作发生在遍历其左右子树之中间若二叉树非空操作步骤
(1)中序遍历左子树(2)访问根节点(3)中序遍历右子树。
 
c) 后序遍历左→右→根
访问根结点的操作发生在遍历其左右子树之后若二叉树非空操作步骤
(1)遍历左子树(2)遍历右子树(3)访问根节点。
 
d) 层次遍历按层自上而下自左而右逐层访问树中各层节点。

最优二叉树

最优二叉树又称为哈夫曼树是一类带权路径长度最短的树。

权是一个人为的概念表示计算机对每个结点的访问频率。

路径长度从树中一个节点到另一个节点之间的通路称为节点间的路径该通路上分支数目。

树的路径长度树根到每一个叶子之间的路径长度之和。

节点的带权路径长度从该节点到树根之间的路径长度与该节点权的乘积。

树的带权路径长度为树中所有叶子节点的带权路径长度之和记为

其中n为带权叶子节点数目wk为叶子节点的权值lk为叶子节点到根节点的路径长度根据定义如下b图的为最优二叉树。

Tips

1、最优二叉树的一个应用是对字符集中的字符进行编码和译码。

2、给定N个权值作为N个叶子结点构造一颗二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。

3、霍夫曼树可以用来进行通信电文的编码和解码。

4、B-树是一种平衡的多路查找树:

a) B-树中所有非终端结点也就是非叶子结点都会包含关键字
 
b) 所有叶子结点都出现在同一层次上并且不带信息可以看作是外部结点或查找失败的结点。
层次相同也就是高度相同从根结点到每个叶子结点的路径长度相同
 
c) 所有非终端结点包含的关键字数量是不确定的指向的子树个数也是不确定的。

5、树的前序遍历与二叉树的先序遍历一样树的后序与二叉树的中序遍历一样。

6、散列就是把任意长度的输入通过散列算法变换成固定长度的输出该输出就是散列值如此建立的表为散列表散列表是可以动态创建的。

7、二分查找折半查找要求关键字必须采用顺序存储结构并且必须按关键字的大小有序排序。

二叉查找树

二叉查找树又称为二叉排序树它或者是一棵空树或者是具有如下性质的二叉树

a) 若其左子树非空则其左子树中每个节点的值关键码都小于该节点值关键码
b) 若其右子树非空则其右子树中每个节点的值关键码都大于该节点值关键码
c) 左、右子树本身就是2棵二叉查找树。
d) 平衡二叉树或者是空树或者是满足树中任一节点左右子树的深度相差不超过1。
结点的平衡度其右子树的深度减去左子树的深度因此平衡度只能为1,0-1。

对二叉树进行中序遍历可得到一个关键码递增有序的节点序列使用二叉查找树来查找树中的数值比普通的二叉树更方便。

构造二叉树时需进行平衡化处理使每个节点左右子树的高度的绝对值不超过1。

3.3.2 图

图GGraph是由两个集合V和E构成的二元组其中VVertex是图中顶点的非空有限集合EEdge是图中边的有限集合图G的顶点集和边集分别记为VG和EG而将图G记作G=(VE)。

可以看出一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。从数据结构的逻辑关系角度来看图中任一顶点都有可能与图中其他顶点有关系而图中所有顶点都有可能与某一顶点有关系所以图中一个节点的前驱和后继的数目是没有限制的。

在图中数据结构中的数据元素用顶点表示数据元素之间的关系用边表示。

边数等于所有顶点的度数之和的一半。

有向图

图中每条边都是有方向的从顶点vi到vj的有向边< v i , v j >,vi称为弧尾v j称为弧头< v i , v j >和< v j , v i >为两条弧。

无向图

图中每条边都是无方向的< v i , v j > 和< v j , v i > 为同一条边。

Tips

1、有向图中所有顶点的出度数之和等于入度数之和。

2、在有向图中顶点为n的边数等于n(n-1) / 2 无向图中边数等于n(n-1) 。

完全图

一个无向图具有n个顶点且每个顶点与其他n − 1个顶点之间都有边则称为无向完全图n个顶点的无向完全图的弧数目为n ( n − 1 ) / 2n个顶点的有向完全图的弧数目为n ( n−1 )因为任意两个不同顶点之间都存在方向相反的两条弧。

度、出度、入度

顶点 v 的度是指关联于该顶点的边的数目记作D(v),若为有向图度表示该顶点的入度和出度之和。

顶点的入度是以该顶点为终点的有向边的数目
顶点的出度指以该顶点为起点的有向边的数目。

路径:

第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了顶点Vp和顶点Vq可以相同外其余顶点均不相同这种路径称为一条简单路径。

子图:

连通图:

如果无向图 G中任意两个顶点都是连通的则称其为连通图。图 3-22(b所的无向图是连通图。

强连通图:

从顶点Vi到顶点Vj和从顶点Vj到顶点Vi都存在路径则称图G为强连通图。

网 边或者弧具有权值的图

图的存储结构

邻接矩阵表示法

利用一个矩阵来表示图中顶点之间的关系

邻接链表表示法

为图中的每个顶点建立一个单链表第i个单链表中的节点表示依附于定点v i 的边对于有向图是以v i为尾的弧。

邻接链表中的表节点有表节点和表头节点两种类型

其中各参数的含义如下:

adjvex:指示与顶点v邻接的顶点的序号
nextarc:指示下一条边或弧的结点。
info:存储和边或弧有关的信息如权值等
data:存储顶点的名或其他有关信息。
firstarc:指示链表中的第一个结点。

图的遍历

深度优先搜索( DFS )

访问起始点 v;
若v的第1个邻接点没访问过深度遍历此邻接点
若当前邻接点已访问过再找v的第2个邻接点重新遍历。

广度优先搜索( BFS )

在访问了起始点v之后依次访问 v的邻接点
然后再依次顺序访问这些点下一层中未被访问过的邻接点
直到所有顶点都被访问过为止。

3.4 常用算法

3.4.1 算法概述

算法是问题求解过程的精确描述它为解决某一特定类型的问题规定了一个运算过程。

算法特性

a)有穷性一个算法必须在执行有穷步骤之后结束且每一步都可在有穷时间内完成。
b)确定性算法的每一步必须是确切定义的不能有歧义。
c)可行性算法应该是可行的这意味着算法中所有要进行的运算都能够由相应的计算装置所理解和实现并可通过有穷次运算完成。
d)输入一个算法有零个或多个输入它们是算法所需的初始量或被加工的对象的表示这些输入取自特定的对象集合。
e)输出一个算法有一个或多个输出它们是与输入有特定关系的量。

算法考查

a)正确性正确性也称为有效性是指算法能满足具体问题的要求。即对任何合法的输入算法都能得到正确的结果。
b)可读性可读性指算法被理解的难易程度。人们常把算法的可读性放在比较重要的位置因为晦涩难懂的算法不易交流和推广使用也难以修改和扩展。因此设计的算法应尽可能简单易懂。
c)健壮性健壮性也称为鲁棒性即对非法输入的抵抗能力。对于非法的输入数据算法应能加以识别和处理而不会产生误动作或执行过程失控。
d)效率粗略地讲就是算法运行时花费的时间和使用的空间。对算法的理想要求是运行时间短、占用空间小。

算法与数据结构

算法实现时总是建立在一定的数据结构基础之上计算机程序从根本上看包括两方面的内容:一是对数据的描述二是对操作(运算)的描述。概括来讲在程序中需要指定数据的类型和数据的组织形式就是定义数据结构描述的操作步骤就构成了算法。因此从某种意义上可以说“数据结构+算法 = 程序”。

算法描述

常用的算法描述方法有流程图、N/S 盒图、伪代码和决策表等。

流程图

流程图 (fow chart)即程序框图是历史最久、流行最广的一种算法的图形表示方法。每个算法都可由若干张流程图描述。流程图给出了算法中所进行的操作以及这些操作执行的逻辑顺序。程序流程图包括三种基本成分:加工步骤用方框表示逻辑条件用菱形表示控制流用箭头表示。

N/S 盒图

盒图是结构化程序设计出现之后为支持这种设计方法而产生的一种描述工具。在 N/S 图中每个处理步用一个盒子表示盒子可以嵌套。对于每个盒子只能从上面进入从下面走出除此之外别无其他出入口所以盒图限制了随意的控制转移保证了程序的良好结构。

伪代码

用伪代码描述算法的特点是借助于程序语言的语法结构和自然语言叙述使算法具有良好的结构又不拘泥于程序语言的限制。这样的算法易读易写而且容易转换成程序。

决策表

决策表是一种图形工具它将比较复杂的决策问题简洁、明确、一目了然地描述出来。

3.4.2 排序

假设含有n个记录的文件内容为{ R 1 , R 2 , … , R n }其相应的关键字为{ k 1 , k 2 , … , k n }。
  
常见的内部排序算法

直接插入排序

在插入第i个记录时R 1 , R 2 , … , R i − 1已经排好序这时将记录R i的关键字依次与关键字k i − 1 , k i − 2 , … , k 1进行比较从而找到Ri 应该插入的位置插入位置及其后的记录依次向后移动。

直接插入排序是一种稳定的排序方法其时间复杂度为 O(n^2)。排序过程中仅需要一个元素的辅助空间空间复杂度为 O(1)。

void insertSort(int data[], int n)
/*将数组 data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列*/
{
    int i j;
    int tmp;
    for (i = 1; i < n; i++) {
        if (data[i] < data[i - 1]) {
            tmp = data[i];
            data[i] = data[i - 1];
            for (j = i - 1; j >= 0 && data[j] > tmp; j--)
                data[j + 1] = data[j];
            data[j + 1] = tmp;
        } /*if*/
    } /*for*/
} /*insertSort*/

冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较若为逆序则交换两个记录的值然后比较第二个记录和第三个记录的关键字以此类推直至第n-1个记录和第n个记录的关键字比较完为止。

void bubbleSort(int data[], int n)
/*将数组data[]~data[n-1]中的n个整数按非递减有序的方式进行排列*/
{
    int i, j, tag;
    /*用tag 表示排序过程中是否交换过元素值*/
    int tmp;
    for (i = 1, tag = 1; tag == 1 && i < n; i++) {
        tag = 0;
        for (j = 0; j < n - i; j++)
            if (data[j] > data[j + 1]) {
                tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
                tag = 1;
            } /*if*/
    } /*for*/
} /*bubbleSort*/

简单选择排序

void selectSort(int data[], int n)
/*将数组 data[]~data[n-1]中的n个整数按非递减有序的方式进行排列*/
{
    int i, j, k;
    int tmp;
    for (i = 1; i < n; i++) {
        k = i;
        for (j = i + 1; j <= n; j++)
            /*找出最小元素的下标用 k 表示*/
            if (data[j] < data[k]) k = j;
        if (k != i)[tmp = data[i]; data[i] = data[k]; data[k] = tmp;
        } /*if*/
    } /*for*/
} /*selectSort*/

每次选出关键字最小的记录并和未排序记录进行交换。

希尔排序

又称为“缩小增量排序”是对直接插入排序方法的改进先将整个待排记录序列分割成若干个子序列然后分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

快速排序

通过一趟排序将待排的记录划分为独立的两部分称为前半区和后半区其中前半区中记录的关键字均不大于后半区记录的关键字然后再分别对这两部分记录继续进行快速排序从而使整个序列有序。

1、直接插入排序:按顺序插入待排关键字插入时依次查找位置直接插入后面的依次后移。
 
2、冒泡排序:依次把相邻的两个记录进行比较然后交换位置。
 
3、简单选择排序:每次选择最小的与第一个没有排过序的记录交换。
 
4、希尔排序:间隔若干个空的记录分为一组进行直接插入排序依次将间隔缩小到1为止。
 
5、快速排序:设两个指针指示头尾从尾开始首尾交替轮流和枢轴记录(第一个记录)进行比较并交换位置。
 
6、堆排序:反复将待排序列建立成堆并取堆顶。
 
7、归并排序: 两两归并为一组再四个地录归并为一组依此类推。

各种排序方法的性能比较

3.4.3 查找

查找表是指由同一类型的数据元素或记录构成的集合分为静态查找表只进行查找和检索操作和动态查找表还可进行插入和删除操作哈希表是一种动态查找表。
 
对于查找算法来说其基本操作是“将记录的关键字与给定值进行比较”因此通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。为确定记录在查找表中的位置需和给定值进行比较的关键字的个数的期望值称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表查找成功的平均查找长度为

Pi为查找表中第i 个数据元素的概率一般为1/nCi为找到第i个数据元素时已经比较过的次数显然Ci 随查找方法的不同而不同。

顺序查找

从表中的一段开始逐个进行记录的关键字和给定值的比较若找到一个记录的关键字与给定值相等则查找成功若整个表中的记录均比较过仍未找到关键字等于给定值的记录则查找失败。

顺序查找是对顺序存储和链式存储方式的查找表都适用优点算法简单且适用面广缺点查找效率较低。

在等概率的情况下顺序查找成功的平均查找长度为

折半查找二分查找

折半查找基本思想先令查找表中间位置记录的关键字和给定值比较若相等则查找成功若不等则缩小范围直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时表名查找不成功为止。
  
折半查找的平均查找长度为
  

折半查找比顺序查找的效率要高但它要求查找表进行顺序存储并且按关键字有序排列一般不进行表的插入与删除操作。因此折半查找适用于表不易变动且经常进行查找的情况。

索引顺序查找

索引顺序查找又称分块查找是对顺序查找方法的一种改进。

在分块查找过程中首先将表分成若干块每一块中关键字不一定有序但块之间是有序的即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外还建立一个“索引表”索引表按关键字有序。

树表查找
  
二叉查找树是一种动态查找表其特点是表结构本身是在查找过程中动态生成的即对于给定值key若表中存在关键字等于key的记录则查找成功返回否则插入关键字等于key的记录。

哈希查找

前面几种查找方法由于记录的存储位置与其关键码之间不存在确定的关系所以查找时都要通过一系列对关键字的比较才能确定被查记录在表中的位置即这类查找方法都建立在对关键字进行比较的基础之上。

哈希表思想

依据记录的关键码直接得到对应的存储位置即要求记录的关键码与其存储位置之间存在一一对应的关系通过这个关系能很快的由关键码找到记录。

哈希函数

关键字作为自变量关键字存放的地址作为因变量。

哈希冲突

对于某个哈希函数Hash和两个关键字K1和K2如果K1≠ K2而H a s h ( K 1 ) = H a s h ( K 2 )则称为冲突对哈希函数来说K1和K2称为同义词。

采用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。

冲突处理

开放定址法、链地址法、再哈希法等。

a)开放定制法
 
b)链地址法
  链地址法是一种经常使用且很有效的方法它将具有相同哈希函数值得记录组织成一个链表当链域的值为NULL时表示已没有后继记录。
  用链地址法解决冲突构造的哈希表中查找元素就是根据哈希函数得到元素所在链表的头指针然后在链表中进行顺序查找的过程。

3.4.4 递归算法

递归(recursion)是一种描述和解决问题的基本方法用来解决可归纳描述的问题或者是可分解为结构自相似的问题。所谓结构自相似是指构成问题的部分与问题本身在结构上相似。

3.4.5 图的相关算法

生成树
 
 设图G = ( V , E ) 是个连通图如果其子图是一棵包含G 的所有顶点的树则该子图成为G的生成树。
 

对于连通图来说边是带权值的生成树的各边也都带权值于是就把生成树各边的权值总和成为生成树的权把权值最小的生成树称为最小生成树求最小生成树最常用的两种算法

a) 普利姆算法
以顶点为准从已选顶点所关联的未选边中找出权重最小的边并且生成树不存在环。
 
b) 克鲁斯卡尔算法
以边为主找权值最小的边。

求单源点的最短路径算法

是指给定带权有向图G和源点v0求从v0到G中其余各顶点的最短路径按路径长度递增的次序产生最短路径的算法。

---

---

第三章 数据结构与算法经典例题

6、2022上计算机在处理算数表达式78+21*36-34时先将其转换成5的后缀形式表示然后利用6进行计算。
A、栈
B、队列
C、数组
D、串

参考答案A
试题解析 操作符在操作数前面则称为前缀表达式。如果操作符在操作数之间则称为中缀表达如果操作符在操作数后面则称为后缀表达式。
计算机在存储中缀表达式时需要使用树这种数据结构如果表达式过于复杂那么树的高度会变得很高大大增加了时间复杂度和空间复杂度。如果转换成线性结构那么效率将变得高很多所以需要将中缀表达式先转换成前缀或者后缀表达式然后依靠栈这种线性数据结构来进行计算。

7、2022上依次在初始为空的队列中插入元素5、6、7、8以后紧接着做了两次删除操作此时的队头元素是7。
A、5
B、6
C、7
D、8

参考答案C
试题解析队列是一种操作受限制的线性表是先入先出的线性表.

8、2022上以下关于串的叙述中错误的是8。
A、串是仅由字符构成的有限序列
B、串是取值范围受限的线性表
C、空串不包含任何字符
D、串只可以采用顺序存储方式

参考答案D
试题解析串是由零个或多个任意字符组成的有限序列。串可以采用多种存储方式比如顺序存储方式块链存储方式等。

9、2022上折半查找要求查找表中的数据为9。
A、顺序存储、有序排列
B、散列存储、有序排列
C、顺序存储、无序排列
D、散列存储、无序排列

参考答案A
试题解析
折半查找又称二分查找它仅适用于有序的顺序表。
基本思路是:首先将给定值 key 与表中中间位置元素的关键字比较若相等则查找成功返回该元素的存储位置;若不等则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如在查找表升序排列时若给定值 key 大于中间元素的关键字则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找如此重复直到找到为止或确定表中没有所需要香找的元素则香找不成功。返回查找失败的信息。

10、2022上10的基本思想是先将待排的记录划分为独立的两个部分然后分别对这两部分记录再执行该排序算法最终使整个序列有序。
A、快速排序
B、冒泡排序
C、堆排序
D、希尔排序

参考答案A
试题解析
快速排序 (Quick Sort) 是从冒泡排序算法演变而来的实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素并让其他比它大的元素移动到数列一边比它小的元素移动到数列的另一边从而把数列拆解成了两个部分。

5、2021上一个栈的输入序列为12345不可能得到的输出序列是 。

A.2,3,4,1,5
B.5,4,1,3,2
C.2,3,1,4,5
D.1,5,4,3,2

参考答案B
试题解析

6、2021上 算法是不稳定的排序算法。

A.简单选择
B.冒泡
C.直接插入
D.归并排序

参考答案A
试题解析
选择排序的基本思想是
设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录Ri,Ri+1,…,Rn中找出排序码最小的记录i个记录交换。执行n-1趟 后就完成了记录序列的排序。
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变在原序列中r[i]=r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否称为不稳定的。
举个例子序列1081029
我们知道第一遍选择第1个元素10会和2交换那么原序列中2个10的相对前后顺序就被破坏了所以选择排序是一个不稳定的排序算法。

6、2021上 是一种先进先出的线性表只允许在表的一端插入元素而在表的另一端删除元素。

A.栈
B.队列
C.串
D.树

参考答案A
试题解析
选择排序的基本思想是
队列是先入先出的线性表队列仅在表头删除元素、在表尾插入元素。

8、2021上一棵5层的二叉树其最多有 个结点第5层最多有 个结点。

问题1

A.15
B.16
C.31
D.32

问题2

A.15
B.16
C.31
D.32

参考答案C、B
试题解析
二叉树的特性
1、在二叉树的第i层上最多有2 个结点i≥1
2、深度为k的二叉树最多有2 -1个结点k≥1
3、对任何一棵二叉树如果其叶子结点数为n0度为2的结点数为n2则n0=n2+1。
代入公式得到正确答案为CB。

9、2021上 排序又被称为缩小增量排序是对直接插入排序方法的改进。

A.简单选择
B.冒泡
C.快速
D.希尔

参考答案D
试题解析
希尔排序是插入排序的一种又称“缩小增量排序”是直接插入排序算法的一种更高效的改进版本。希尔排序稳定排序算法。
希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止了。

5、2020上在常见的数据结构中 是只能通过访问它的端来实现数据存储和检索的一种线性数据结构它的修改遵循先进后出的原 是一种先进先出的线性表。 是取值范围受限的线性表。
问题1
A.链表
B.队列
C.栈
D.串

问题2
A.链表
B.队列
C.栈
D.串

问题3
A.链表
B.队列
C.栈
D.串

参考答案C、B、D
试题解析
本题考查数据结构方面的基础知识。
栈和队列都是操作受限的线性表栈仅在表尾插入和删除元素队列仅在表头删除元素、在表尾插入元素。
队列是先入先出的线性表栈是后进先出的线性表。一个线性序列经过队列结构后只能得到与原始序列相同的序列而经过一个栈结构后则可以得到多种元素序列。
串是由零个或多个任意字符组成的有限序列。

6、2020上二叉树遍历是按照某种策略访问树中的每个结点且仅访问一次。按照遍历左子树要在遍历右子树之前进行的原则根据访位置的不同可得到二叉树的前序、中序和后序三种遍历方法。

A.根节点
B.导航节点
C.叶子结点
D.兄弟节点

参考答案A
试题解析
本题考查数据结构基础知识。
遍历运算是二叉树的基本运算主要有先序、中序、后序和层序遍历。
先序遍历的基本方法对于非空二叉树先访问根结点然后先序遍历根的左子树最后先序遍历根的右子树此若已知某二叉树的先序遍历序列则可直接得到其树的根结点。
中序遍历的基本方法对于非空二叉树先中序遍历根的左子树然后访问根结点最后中序遍历根的右子树此若已知某二叉树的根结点则可根据中序遍历序列将该二叉树左右子树上的结点划分开。
后序遍历的基本方法对于非空二叉树首先后序遍历根的左子树接着后序遍历根的右子树最后访问根结因此若已知某二叉树的后序遍历序列则可直接得到其树根结点。
因此按照遍历左子树要在遍历右子树之前进行的原则根据访问根结点位置的不同 可得到二叉树的前序、序和后序三种遍历方法。

7、2020上以下有关哈夫曼树的说法中错误的是 。

A.哈夫曼树又被称为最优二叉树
B.哈夫曼树是一种带 权路径长度最短的树
C.具有n个叶子结点的权值为W W … W 的最优二叉树是唯一的
D.哈夫曼树可以用来进行通信电文的编码和解码

参考答案C
试题解析
给定N个权值作为N个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二树也称为哈夫曼树。哈夫曼树是带权路径长度最短的树权值较大的结点离根较近。
哈夫曼树可以用来进行通信电文的编码和解码。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。从根到每个叶子结点都有一条路径对路径上的各分支约定指向左子树的分支表示“0”码指向右子树的分支表示“1”码取每条路径上的“0”或“1”的序列作为各个叶子结点对应的字符编码即是哈夫曼编码。
具有n个叶子结点的权值为W W … W 的最优二叉树的形态不是唯一的。

8、2020上查找算法中 要求查找表进行顺序存储并且按照关键字有序排列一般不进行表的插入与删除操作。

A.顺序查找
B.折半查找
C.分块查找
D.动态查找

参考答案B
试题解析
本题考查数据结构方面的基础知识。
线性表的查找有顺序查找、折半查找、分块查找方法。
其中顺序查找方法的特点是算法非常简单但效率较低.因为它是用所给关键字与线性表中各元素的关键字个比较直到成功或失败。
折半查找方法的优点是比较次数少查找速度快平均性能好其缺点是要求待查表为有序表且插入和删除难。因此折半查找方法适用于不经常变动而查找频繁的有序表。
分块查找方法又称索引查找它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L一维数组分个子表要求每个子表的长度相等且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表I。因此分块查找的关键在于建立索引表I其查找的平均长度介于序查找和折半查找之间。

10、2020上以下关于哈希函数的说法中不正确的是 。

A.哈希表是根据键值直接访问的数据结构
B.随机预言机是完美的哈希函数
C.哈希函数具有单向性
D.哈希函数把固定长度输入转换为变长输出

参考答案D
试题解析
Hash一般翻译为散列、杂凑或音译为哈希是把任意长度的输入通过散列算法变换成固定长度的输出该出就是散列值。这种转换是一种压缩映射也就是散列值的空间通常远小于输入的空间不同的输入可能会散相同的输出所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定的消息摘要的函数。
哈希表是根据键Key而直接访问在内存存储位置的数据结构。
在密码学里面随机预言机英语Random oracle是一部预言机对任何输入都回传一个真正均匀随机的出不过对相同的输入该预言机每次都会用同一方法输出。换句话说随机预言机是一个将所有可能输入与作随机映射的函数。

5、2019上令序列X、Y、Z的每个元素都按顺序进栈且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是 。

A.X Y Z
B.X Z Y
C.Z X Y
D.Y Z X

参考答案C
试题解析
栈的顺序先进后出。如要Z先出则至少需要X-Y-Z依次全部进栈此时栈内容已确定出栈顺序只能为Z-Y因此得不到序列ZXY。

6、2019上以下关于单链表存储结构特征的叙述中不正确的是 。

A.表中结点所占用存储空间的地址不必是连续的
B.在表中任意位置进行插入和删除操作都不用移动元素
C.所需空间与结点个数成正比
D.可随机访问表中的任一结点

参考答案D
试题解析
单链表存储不能随机访问表中的任一结点必须从头结点依次.next。

7、2019上B-树是一种平衡的多路查找树。以下关于B-树的叙述中正确的是 。

A.根结点保存树中所有关键字且有序排列
B.从根结点到每个叶结点的路径长度相同
C.所有结点中的子树指针个数都相同
D.所有结点中的关键字个数都相同

参考答案B
试题解析
B-树中所有非终端结点也就是非叶子结点都会包含关键字A选项错误。
B-树中所有叶子结点都出现在同一层次上并且不带信息可以看作是外部结点或查找失败的结点层次相就是高度相同从根结点到每个叶子结点的路径长度相同B选项正确。
B-树中所有非终端结点包含的关键字数量是不确定的指向的子树个数也是不确定的所以C选项和D选项错误。

8、2019上对于给定的关键字序列47, 34, 13, 12, 52, 38, 33, 27, 5若用链地址法拉链法解决冲突来构造哈希表且哈希函数H(key)=key%11则 。

A.哈希地址为1的链表最长
B.哈希地址为6的链表最长
C.34和12在同一个链表中
D.13和33在同一个链表中

参考答案C
试题解析
链地址法拉链法在查找表的每一个记录中增加一个链域链域中存放下一个具有相同哈希函数值的记录储地址。即利用链域将发生冲突的记录链接在一个链表里。
本题对于给定的关键字序列47, 34, 13, 12, 52, 38, 33, 27, 5哈希函数为H(key)=key%11则其哈希值分3, 1, 2, 1, 8, 5, 0, 5, 5
可以看到哈希地址为5的冲突最多其对应的链表最长A选项和B选项错误。
34和12的哈希值都为1放在同一个链表中C选项正确。
13的哈希值为233的哈希值为0不在同一个链表中D选项错误。

9、2019上某有向图G的邻接表如下图所示可看出该图中存在弧V , V ,而不存在从顶点V 出发的弧。以下关于图G的叙述中错误的是 。

A.G中存在回路
B.G中每个顶点的入度都为1
C.G的邻接矩阵是对称的
D.不存在弧V3, V1

参考答案C
试题解析
根据邻接表这里存在4个有向弧分别为V →V V →V V →V V →V 。

分析可得图中存在 V →V V →V V →V 回路A选项正确。
V 入度为1 V 入度为1 V 入度为1 V 入度为1B选项正确。
转换为邻接矩阵M可以发现M[0,2]=1M[2,0]=0即 V 到 V 存在弧 V 到 V 不存在弧邻接矩阵并不对称。所以C选项错误。
没有 V →V 的有向弧D选项正确。
也可以直接画出对应的图和邻接矩阵如下

根据图示分析可以看到C选项不正确

10、2019上已知有序数组a的前10000个元素是随机整数现需查找某个整数是否在该数组中。以下方法中 的查找效率最高。

A.二分查找法
B.顺序查找法
C.逆序查找法
D.哈希查找法

参考答案A
试题解析
对于有序序列的查找二分法效率较高。

5、2018上设有n阶三对角矩阵A即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上现对该矩阵进行按行压缩存若其压储空间用数组B表示A的元素下标从0开始B的元素下标从1开始。已知A0,0存储在B1An-1n-1存3n-2那么非零元素Ai,j0≤ in0≤ jn│i-j│≤1存储在B 。

A.2i+j-1
B.2i+j
C.2i+j+1
D.3i-j+1

参考答案A
试题解析
对于有序序列的查找二分法效率较高。
代入A[0, 0]到ABCD四个选项中得到B[1]的只有C和D再代入A[n-1, n-1]得到B[3n-2]的只有C正确D选项到的是B[3n-1]

6、2018上用哈希表存储元素时需要进行冲突碰撞处理冲突是指 。

A.关键字被依次映射到地址编号连续的存储位置
B.关键字不同的元素被映射到相同的存储位置
C.关键字相同的元素被映射到不同的存储位置
D.关键字被映射到哈希表之外的位置

参考答案A
试题解析 A选项为一种解决冲突的办法。题干问的是冲突是什么自然是B选项的意思。

7、2018上对有n个结点、e条边且采用数组表示法即邻接矩阵存储的无向图进行深度优先遍历时间复杂度为 。

A.O(n ^2
B.O(e^2 )
C.O(n+e)
D.O(n*e)

参考答案A
试题解析
当用二维数组表示邻接矩阵图的存储结构时查找每个顶点的邻接点所需时间为 O(n ^2)其中n 为图中顶点数当以邻接表作图的存储结构时,e 为无向图中边的数或有向图中弧的数深度优先搜索遍历图的时间复杂度为O(n+e) 。