数据结构与算法.docx

《数据结构与算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法 第一节数据结构及算法概述一、数据结构O OOOOO集合结构树型结构(b)线性结构(d)图形结构图.!1!类基本结构的示意图【要点】.数据元素是数据的基本单位。1 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。2 . 4类基本的规律结构:集合、线性结构、树形结构和网状结构。3 . 4种数据存储方式：挨次、链式、索引和散列。【例题单项选择题】(2022年X省信用社聘请考试真题)以下说法不正确的选项是()OA.数据元素是数据的基本单位B.数据项是数据中不行分割的最小标志单位C.数据可由假设干个数据元素构成D.数据项可由假设干个数据元素构成正确答案D答案解析数据元素是数据

2、的基本单位，在计算机程序中通常被作为一个整体进 行考虑和处理。一个数据元素可由假设干个数据项组成。数据项是不行分割的、含有独立 意义的最小数据单位。因此D选项不正确。二、算法在待排序的n个纪录中任取一个纪录（例如就取第1个纪录），以该纪录的键 值为标准，将全部纪录分为两组（一般都是无序的），使得第1组中各纪录的键值均小 于或等于该键值，第2组中各纪录的键值均大于该键值。然后把该纪录排在这两组的中 间（这也是该纪录最终的位置）。此称为一趟快速排序（或一次划分），对所分成的两 组再分别重复上述方法，直到全部纪录都排在适当位置为止。【要点】冒泡排序和快速排序方法。【例题单项选择题】（2022年X省信

3、用社聘请考试真题）用某种排序方法对序 列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序,纪录序列的变化状况如下：那么采纳的排序方法是（）。A.直接选择排序B.冒泡排序C.快速排序D.二路归并排序正确答案C答案解析直接选择排序第一趟就应中选出一个最小的在第一个位置；冒泡排序 法是两两比拟，25与84比拟，25要小，位置不变；快速排序法使比基准数（第一趟是 25）小的数在基准数左边，比基准数大的数在基准数右边；二路归并排序是分组比拟， 第一趟应当是“2584”、“2147”、“1527”、“6835”、“20”这几组进行排序。 （三）选择排序每一趟从待排序的纪录中

4、选出关键字最小的纪录，挨次放在已排好序的子文件 的最终，直到全部纪录排序完毕。常用的选择排序方法有直接选择排序和堆排序。1 .直接选择排序先在全部的纪录中选出键值最小的纪录，把它与第1个纪录交换；然后在其余 的纪录中再选出键值最小的纪录与第2个纪录交换；依此类推，直至全部纪录排序完成。2 .堆排序对一组待排序纪录的键值，先将它们按堆定义排成一个堆，这称为建堆。这就 找到最小的键值。然后将最小键值取出，用剩下的键值再建堆，便得到次最小的键值。如此反复进行，直到得到最大键值，从而将全部键值排好序为止。（四）归并排序将这些有序的子序列进行合并，从而得到有序的序列。合并是一种常见运算， 其方法是：比拟

5、各子序列的第一个纪录的键值，最小的一个就是排序后序列的第一个纪 录的键值。取出这个纪录，连续比拟各子序列现在的第一个纪录的键值，便可找出排序 后的其次纪录。如此连续下去，最终可以得到排序结果。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法的特性：有穷性、确定性、可行性、输入和输出。【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。其次节线性表线性表是n (n20)个数据元素al, a2,，an组成的有限序列，n=0时称为 空表。非空的线性表，有以下特征：1 .有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。2

6、 .有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋3 .其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a.1和一个直接 后继&I+10线性表的链式存储包括单链表、循环链表和双链表。head首结点尾结点三BT+NULLa1【留意】与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个 方向上的指针。第三节栈和队列一、栈栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一端进行。不含任何数据元素的栈称为空栈。栈的基本运算：构造一个空栈InitStack （S）、判栈空StackEmpty （S）、判栈满 StackFull (S)、进栈 Pu

7、sh (S, x)、退栈 Pop (S)、取栈顶元素 StackTop (S)。进栈 （压入）退栈 （弹出）topbottom【要点】栈的修改是按后进先出的原那么进行。二、队列 队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。当队列中没有元素时称为空队列。栈和队列一般有两种存储结构：挨次存储结构和链式存储结构。q。 gi azrearrearfront【要点】队列的修改是依据先进先出的原那么进行的。【例题单项选择题】（2007年X省信用社聘请考试真题）以下（）不是栈的基本运算?A.删除栈顶元素B.删除栈底元素C.推断栈是否为空D.将栈置为空栈正确答案B答案解析栈是一种特别的线

8、性表，这种线性表上的插入和删除运算限定在表的 某一端进行。允许进行插入和删除的这一端称为栈顶，另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。栈的修改是按后进先出的原那么进行。栈的运算在栈顶进行。 因此，删除栈底元素不属于栈的基本运算。第四节数组数组：把具有相同类型的假设干变量按有序的形式组织起来的同类数据元素的集合。第1五节树一、树(一)基本概念root苞(b)rootQlevel 0C) HD)level 1idepth=3)甲(1)一level 2 M) eve I 3树是n (n0)个结点的有穷集合，满意以下条件：(1)有且仅有一个称为根的结点。(2)其余结点分为m (m2。)个互

9、不相交的非空集合Tl, T2,Tm,这些集合 中的每一个都是一棵树，称为根的子树。森林是m (mO)棵互不相交的树的集合。树中的一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的 最大度数。树中某个结点的子树的根称为该结点的孩子或儿子。树中结点的最大层数称为树的高度或深度。(二)树和森林的遍历1.树的遍历A(a)树先序遍历：假设树不空，那么先访问根结点，然后依次先序遍历各棵子树。 后序遍历：假设树不空，那么先依次后序遍历各棵子树，然后访问根结点。 层次遍历：假设树不空，那么自上而下自左至右访问树中每个结点。ABCED 2.森林的遍历ABCDEBDCEA前序遍历森林：假设森林非空,那

10、么：访问森林中第一棵树的根结点。前序遍历第一棵树中根结点的各子树所构成的森林。前序遍历除第一棵树外其他树构成的森林。右图前序遍历序列为ABCDEFIGJHo后序遍历森林：假设森林非空，那么：后序遍历森林中第一棵树的根结点的各子树所构成的森林。访问第一棵树的根结点。后序遍历除第一棵树外其他树构成的森林。右图后序遍历序列为BDCAIFJGHEo二、二叉树（一）基本概念二叉树是n （nNO）个结点的有限集，它可以是空集（n=0）,或者由一个根 结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的性质.二叉树的第i层上至多含有个结点（i2l）。1 .深度为k的二叉树上至多含有21

11、1个结点（k2l）。2 .对任何一棵二叉树，假设它含有n。个叶子结点、切个度为2的结点，那么必存在 关系式：n0=n2+lo深度为k （kNl）且有2卜-1个结点的二叉树称为满二叉树。假如在一棵深度为k （k2l）的满二叉树上删去第k层上最右边的连续j（0j2k-l）个结点，就得到一棵深度为k的完全二叉树。满二叉树也是完全二叉树。（二）二叉树的遍历.先根遍历假设需遍历的二叉树为空，执行空操作；否那么，依次执行以下操作：(1)访问根结点。(2)先根遍历左子树。(3)先根遍历右子树。右图的遍历序列为：ABDGCEF.中根遍历假设需遍历的二叉树为空,执行空操作；否那么，依次执行以下操作：(1)中根遍

12、历左子树。(2)访问根结点。(3)中根遍历右子树。右图的遍历序列为：DGBAECF.后根遍历假设需遍历的二叉树为空，执行空操作；否那么，依次执行以下操作：(1)后根遍历左子树。(2)后根遍历右子树。(3)访问根结点。右图的遍历序列为：GDBEFCA【要点】树和二叉树的概念和他们的各种遍历方法。第六节图一、图的基本概念在树形结构中，节点间具有分支层次关系，每一层上的节点只能和上一层中的 至多一个节点相关，但可能和下一层的多个节点相关。在图状结构中，任意两个节点之间都可能相关。有序偶对用尖括号括起来；无序偶对用圆括号括起来。(x,y)与(y,x)被认 为是同一条边，但x, y与y, x那么是不同的

13、两条弧。图的边或弧附带数值，这种数值叫权。【要点】一个具有n个顶点的无向完全图的边数为n (n-1) /2。一个具有n个顶点的 有向完全图的弧数为n (n-1) o二、图的存储结构图的两种存储结构：邻接矩阵表示法和邻接表表示法。图的遍历包括深度优先遍历和广度优先遍历两种方法。第七节查找一、查找的基本概念查找表是由同一类型的数据元素(或纪录)构成的集合。分为两类：静态查找 表和动态查找表。二、线性表的查找挨次查找：从表的一端开头，挨次扫描线性表，依次将扫描到的结点关键字和 给定值K相比拟。假设当前扫描到的结点关键字与K相等，那么查找胜利；假设扫描结束后， 仍未找到关键字等于K的结点，那么查找失败

14、。二分查找：要求线性表是有序表，每次将查找区间中间位置上的数据元素的键 值与给定值K比拟，假设不等那么缩小查找区间，并在新的区间内重复上述过程，直到查找 胜利或查找区间长度为0 (查找不胜利)为止。【要点】二分查找法要求线性表是有序表，把握其查找方法。【例题单项选择题】(2022年义省信用社聘请考试真题)在挨次表(3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30)中，用二分法查找关键码值11所需的关键码比拟 次数为()。A. 2 B. 3 C. 4 D. 5正确答案D答案解析依据二分法查找方法，各数值比拟次数如下(用圆圈里的数来表示： 3(3), 6(2), 8，

15、10，12，15(3), 16, 18(2), 21(4), 25(3), 30)，对于 H 来说, 是杳找不胜利，所以应当比拟5次。第八节排序一、排序概述排序，就是使文件中的纪录按关键字递增(或递减)次序排列起来。按是否访问外存，可将排序方法分为内部排序和外部排序。对于内部排序，依据设置有序序列的方式的不同，又可以划分为插入排序、交 换排序、选择排序、归并排序和其他排序方法。二、常用排序方法简介(-)插入排序每步将一个待排序的纪录按其关键字的大小插到前面已经排序的序列中的适 当位置，直到全部纪录插入完毕为止。1 .直接插入排序依次将每个纪录插入到一个有序序列中去。2 .希尔排序先取一个小于n

16、的整数dl作为第一个增量，把文件的全部纪录分成dl个组。 全部距离为dl的倍数的纪录放在同一个组中。先在各组内进行直接插入排序；然后， 取其次个增量d2dl重复上述的分组和排序，直至所取的增量dt=l(dtdt-l-d2dl),即全部纪录放在同一组中进行直接插入排序为止。(二)交换排序两两比拟待排序纪录的关键字，觉察两个纪录的次序相反时即进行交换，直到 没有反序的纪录为止。1 .冒泡排序8610nn对于1n个纪录，先将第n个和第nT个纪录的键值进行比拟，如rn. keyr n-l .key,那么将两个纪录交换。然后比拟第nT个和第n-2个纪录的关键字。依此类 推，直到第2个纪录和第1个纪录进行比拟交换，这称为一趟冒泡。这一趟最明显的效 果是：将键值最小的纪录传到了第1位。然后对2n个纪录进行同样操作，那么具有次 小键值的纪录被安置在第2位上。重复以上过程，每次的移动都向最终排序的目标前进, 直至没有纪录需要交换为止。2 .快速排序