数据结构与算法.docx

《数据结构与算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法.docx（11页珍藏版）》请在第一文库网上搜索。

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

2、一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不行分割的、含有独立意义的最小数据单位。因此D选项不正确。二、算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法的特性：有穷性、确定性、可行性、输入和输出。【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。其次节线性表线性表是n (n0)个数据元素al, a2,，an组成的有限序列,n=0时称为空表。非空的线性表，有以下特征：L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。2 .有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-

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

4、。进栈（压入）退栈top（弹出）bottom【要点】栈的修改是按后进先出的原则进行。二、队列队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。当队列中没有元素时称为空队列。栈和队列一般有两种存储结构：挨次存储结构和链式存储结构。 o cr zq力- front【要点】队列的修改是依据先进先出的原则进行的。【例题单选题】（2007年X省信用社聘请考试真题）以下（）不是栈的基本运算？A.删除栈顶元素B.删除栈底元素C.推断栈是否为空D.将栈置为空栈正确答案B答案解析栈是一种特别的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的这一端称为栈顶，另一端称为

5、栈底。处于栈顶位置的数据元素称为栈顶元素。栈的修改是按后进先出的原则进行。栈的运算在栈顶进行。因此，删除栈底元素不属于栈的基本运算。第四节数组数组：把具有相同类型的若干变量按有序的形式组织起来的同类数据元素的集合。第五节树一、树(-)基本概念树是nlevellevellevelleveldepth = 3(1)有且仅有一个称为根的结点。(2)其余结点分为m (m20)个互不相交的非空集合Tl, T2,Tm,这些集合中的每一个都是一棵树，称为根的子树。森林是 (20)棵互不相交的树的集合。树中的一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。树中某个结点的子树的根称为该结

6、点的孩子或儿子。树中结点的最大层数称为树的高度或深度。(二)树和森林的遍历1.树的遍历A(a)树先序遍历：若树不空，则先访问根结点，然后依次先序遍历各棵子树。BCDE后序遍历：若树不空，则先依次后序遍历各棵子树，然后访问根结点。BDCE层次遍历：若树不空，则自上而下自左至右访问树中每个结点。ABCED2.森林的遍历前序遍历森林：若森林非空,则：访问森林中第一棵树的根结点。前序遍历第一棵树中根结点的各子树所构成的森林。前序遍历除第一棵树外其他树构成的森林。右图前序遍历序列为ABCDEFIGJHo后序遍历森林：若森林非空，则：后序遍历森林中第一棵树的根结点的各子树所构成的森林。访问第一棵树的根结点

7、。后序遍历除第一棵树外其他树构成的森林。右图后序遍历序列为BDCAIFJGIlEo二、二叉树(-)基本概念二叉树是n (n20)个结点的有限集，它可以是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的性质1 .二叉树的第i层上至多含有个结点(il) o2 .深度为k的二叉树上至多含有2-1个结点(kl) o3 .对任何一棵二叉树，若它含有n。个叶子结点、出个度为2的结点，则必存在关系式：n0=n2+l o深度为k (kl)且有2仁1个结点的二叉树称为满二叉树。假如在一棵深度为k (kl)的满二叉树上删去第k层上最右边的连续j(0Wj2Jl)

8、个结点，就得到一棵深度为k的完全二叉树。满二叉树也是完全二叉树。(-)二叉树的遍历1 .先根遍历若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作：(1)访问根结点。(2)先根遍历左子树。(3)先根遍历右子树。右图的遍历序列为：ABDGCEF2 .中根遍历若需遍历的二叉树为空,执行空操作；否则，依次执行下列操作：(1)中根遍历左子树。(2)访问根结点。(3)中根遍历右子树。右图的遍历序列为：DGBAECF3 .后根遍历若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作：(1)后根遍历左子树。(2)后根遍历右子树。(3)访问根结点。右图的遍历序列为：GDBEFCA【要点】树和二叉树的

9、概念和他们的各种遍历方法。第六节图一、图的基本概念在树形结构中，节点间具有分支层次关系，每一层上的节点只能和上一层中的至多一个节点相关，但可能和下一层的多个节点相关。在图状结构中，任意两个节点之间都可能相关。有序偶对用尖括号括起来；无序偶对用圆括号括起来。(,y)与(y,)被认为是同一条边，但,y与y,则是不同的两条弧。图的边或弧附带数值，这种数值叫权。【要点】一个具有n个顶点的无向完全图的边数为n (n-l) 2o 一个具有n个顶点的有向完全图的弧数为n (n-l) o二、图的存储结构图的两种存储结构：邻接矩阵表示法和邻接表表示法。图的遍历包括深度优先遍历和广度优先遍历两种方法。第七节查找一

10、、查找的基本概念查找表是由同一类型的数据元素(或纪录)构成的集合。分为两类：静态查找表和动态查找表。二、线性表的查找挨次查找：从表的一端开头，挨次扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找胜利；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。二分查找：要求线性表是有序表，每次将查找区间中间位置上的数据元素的键值与给定值K比较，若不等则缩小查找区间，并在新的区间内重复上述过程，直到查找胜利或查找区间长度为0(查找不胜利)为止。【要点】二分查找法要求线性表是有序表，把握其查找方法。【例题单选题】(2022年X省信用社聘请考试真题)在挨次表(

11、3, 6, 8,10, 12, 15, 16, 18, 21, 25, 30)中，用二分法查找关键码值11所需的关键码比较次数为()。A. 2 B. 3 C. 4 D. 5正确答案D答案解析依据二分法查找方法，各数值比较次数如下(用圆圈里的数来表示：3(3), 6，8，10, 120, 15(3), 16(4), 18(2), 21, 25(3), 30),对于 11 来说,是查找不胜利，所以应当比较5次。第八节排序一、排序概述排序，就是使文件中的纪录按关键字递增(或递减)次序排列起来。按是否访问外存，可将排序方法分为内部排序和外部排序。对于内部排序，依据设置有序序列的方式的不同，又可以划分为

12、插入排序、交换排序、选择排序、归并排序和其他排序方法。二、常用排序方法简介（一）插入排序每步将一个待排序的纪录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部纪录插入完毕为止。L直接插入排序依次将每个纪录插入到一个有序序列中去。2.希尔排序先取一个小于n的整数dl作为第一个增量，把文件的全部纪录分成dl个组。全部距离为dl的倍数的纪录放在同一个组中。先在各组内进行直接插入排序；然后，取其次个增量d2dl重复上述的分组和排序，直至所取的增量dt=l（dtdt-ld2dl）,即全部纪录放在同一组中进行直接插入排序为止。（二）交换排序两两比较待排序纪录的关键字，发觉两个纪录的次序相反时即

13、进行交换，直到没有反序的纪录为止。1 .冒泡排序2 8 I3 6 |1口3对于ln个纪录，先将第n个和第nT个纪录的键值进行比较，如rn. keyrn-l . key,则将两个纪录交换。然后比较第n-1个和第n-2个纪录的关键字。依此类推，直到第2个纪录和第1个纪录进行比较交换，这称为一趟冒泡。这一趟最明显的效果是：将键值最小的纪录传到了第1位。然后对2n个纪录进行同样操作，则具有次小键值的纪录被安置在第2位上。重复以上过程，每次的移动都向最终排序的目标前进,直至没有纪录需要交换为止。4 .快速排序在待排序的n个纪录中任取一个纪录（例如就取第1个纪录），以该纪录的键值为标准，将全部纪录分为两组

14、（一般都是无序的），使得第1组中各纪录的键值均小于或等于该键值，第2组中各纪录的键值均大于该键值。然后把该纪录排在这两组的中间（这也是该纪录最终的位置）。此称为一趟快速排序（或一次划分），对所分成的两组再分别重复上述方法，直到全部纪录都排在适当位置为止。【要点】冒泡排序和快速排序方法。【例题单选题】（2022年X省信用社聘请考试真题）用某种排序方法对序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序，纪录序列的变化状况如下：则采纳的排序方法是（）。A.直接选择排序B.冒泡排序C.快速排序D.二路归并排序正确答案C答案解析直接选择排序第一趟就应当选出一个最小的在第一个位置；冒泡排序法是两两比较，25与84比较，25要小，位置不变；快速排序法使比基准数（第一趟是25）小的数在基准数左边，比基准数大的数在基准数右边；二路归并排序是分组比较，第一趟应当是“2584”、“2147”、“1527”、“6835”、“20”这几组进行排序。（三）选择排序每一趟从待排序的纪录中选出关键字最小的纪录