2022年数据结构与算法设计知识点.docx

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

1、精选学习资料 - - - - - - - - - 数据结构与算法设计学问点 试题类型：本课程为考试科目 （闭卷笔试） ,试题类型包括： 概念填空题（10 %）,是非判定题（10 %）,单项挑选题（ 40 %）,算法填空题（10%）,算法应用题（20 %,算法设计题（10 %）；第一章 绪论重点内容及要求：1、明白与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）；数据：全部能 被输入 到运算机中,且能被运算机 处理的符号 的 集合；是运算机操作的对象 的总称；是运算机处理的 信息的 某种特定 的符号 表示形式；数据元素： 是数据（集合）中的一个 “个体 ”,数据结

2、构中的 基本 单位,在运算机程序中通常作为一个整体来考虑和处理；数据项：是数据结构中争论的最小单位,多个数据项的组合数据元素可以是一个或关键码： 也叫关键字（ Key）,是数据元素中能起标识作用的数 据项；其中能起到 唯独标识作用 的关键码称为 主关键码 （简称 主码）；否就称为次关键码；通常,一个数据元素 个次码；只有一个 主码,但可以有多关系： 指一个数据集合中数据元素之间的某种相关性；数据结构： 带“ 结构 ” 的数据元素的集合；这里的结构指元素之 间存在的关系；名师归纳总结 数据类型： 是一个 值的集合 和定义在此集合上的一组操作 的总第 1 页,共 27 页- - - - - - -

3、精选学习资料 - - - - - - - - - 称；2、把握数据结构的基本概念、数据的规律结构（四种）和物理结构（数据元素 的表示与关系的表示、两类储备结构：次序储备结构和链式储备结构）；数据结构包括规律结构和物理结构两个层次；数据的规律结构： 是对数据元素之间存在的规律关系的一种 抽象的描述,可以用一个数据元素的集合和定义在此集合上的如 干关系来表示 规律结构有四种 ：线性结构、树形结构、图状结构、集合结构 数据的物理结构： 是其规律结构在运算机中的表示或实现,因此又称其为储备结构；储备结构： 次序储备结构和链式储备结构 次序储备结构： 利用数据元素在储备器中相对位置之间的某种 特定的关系

4、来表示数据元素之间的规律关系；链式储备结构： 除数据元素本身外, 采纳附加的 “指针” 表示数 据元素之间的规律关系；3、明白算法分析的基本方法,把握算法时间复杂度相关的概念；算法： 是为明白决某类问题而规定的一个有限长的 操作序列 或处理问题的策略一个算法必需满意以下五个重要特性：1有穷性2确定性3可行性 4有输入5有输出设运算法时,通常仍应考虑满意以下目标：1.正确性 ,2.可读性 , 3.健壮性 4.高效率与低储备量需求名师归纳总结 - - - - - - -第 2 页,共 27 页精选学习资料 - - - - - - - - - 如何估算 算法的时间复杂度？算法 = 掌握结构 + 原操

5、作（固有数据类型的操作）算法的执行时间= 原操作 i的执行次数 原操作i 的执行时间算法的执行时间与原操作执行次数之和成正比算法的 空间复杂度定义为 : Sn = Ogn表示随着问题规模 gn 的增长率相同；n 的增大 ,算法运行所需储备量的增长率与算法的储备量 包括: 1. 输入数据 所占空间 2. 程序本身 所占空间 3. 帮助变量 所占空间其次章 线性表重点内容及要求：1、把握线性表的 次序储备结构 ,明白次序表的 储备特点 （数据元素在内存中依次 次序储备）, 优点：可随机存取拜访；缺点：结点的插入 /删除操作不便利；线性表 ：是一种最简洁的数据结构,也是构造其它各类复杂数据结构的基础

6、；一个数据元素的 链式 两种储备表示方法；线性表必有 ：有序（次序）集 ；它有 次序和名师归纳总结 1集合中必存在唯独的一个“ 第一元素 ”第 3 页,共 27 页- - - - - - -精选学习资料 - - - - - - - - - 2集合中必存在唯独的一个“ 最终元素 ”3除最终元素在外,均有 唯独的后继；4除第一元素之外,均有 唯独的前驱定义如下：typedef int ElemType; typedef struct ElemType*elem; /储备数据元素的一维数组；int length; /线性表当前长度；int listsize; /当前安排数组容量；SqList; Vo

7、id InitSqListSqList A,int maxsize/初始化线性表 A.elem = ElemType*mallocLIST_INIT_SIZE*sizeofElemType; if.A.elem exit0; A.length = 0; A.listsize = LIST_INIT_SIZE; return ; 2、明白线性表的 链式储备结构,重点把握 带头结点的单链表的基本操作（结点 的插入与删除运算） ,明白单向循环链表和双向链表储备表示方法；单链表：用一组地址任意的储备单元存放线性表中的数据元素；以元素 数据元素的映象 + 指针 指示后继元素储备位置 = 结点表示数据元素

8、或数据元素的映象 单链表是一种次序存取的结构,求以此为储备表示的线性表长度,可设置一个计数器3、明白 有序线性表的特点（次序有序表、有序链表）；名师归纳总结 有序线性表： 线性表中的数据元素相互之间可以比较 ,并且数据第 4 页,共 27 页- - - - - - -精选学习资料 - - - - - - - - - 元素在线性表中 依值非递减或非递增有序排列,即 aiai-1 或 aiai-1i = 2,3, , n,就称该线性表为 有序表 Ordered List4、学会 对线性表设计相关的算法进行相应的处理；第三章 排序重点内容及要求：1、把握对次序表数据记录进行排序的基本思路和常规操作

9、法的稳固性问题；2、把握简洁 挑选排序、直接插入排序、冒泡排序算法 间复杂度；（比较、 移动）,明白排序算,明白各种排序算法的特点准时排序：将一组 “ 无序 ”的记录序列按某一关键字调整为“ 有序” 的记 录序列；如整个排序过程 不需要拜访外存 便能完成,就称此类排序问题为 内部排序 ；反之就为外部排序；挑选排序：从记录的无序子序列中 “挑选”关键字最小或最大的记录,并将它加入到有序子序列中,长度 基本代码如下以此方法增加记录的有序子序列的fori=0;in-1;i+/*外循环掌握趟数,n 个数选 n-1 趟*/ k=i;/* 假设当前趟的第一个数为最值 , 记在 k 中 */ forj=i+

10、1;jn;j+/* 从下一个数到最终一个数之间找最值 */ ifakaj/* 如其后有比最值更大的 */ k=j;/* 就将其下标记在 k 中*/ ifk.=i/* 如 k 不为最初的 i 值,说明在其后找到比其更大的数 */ t=ak;ak=ai;ai=t;/*就交换最值和当前序列的第一个数*/ 插入排序：插入排序是将一个数据插入到已经排好序的有序数据名师归纳总结 - - - - - - -第 5 页,共 27 页精选学习资料 - - - - - - - - - 中,从而得到一个新的、个数加一的有序数据；代码如下： void InsertSort SqList &L / for i=2; i

11、=L.length; +i if L.ri.key L.ri-1.key 对次序表 L 作插入排序 L.r0 = L.ri; / 复制为哨兵 for j=i-1; L.r0.key 1 / i1 lastExchangeIndex = 1; for j = 1; j i; j+ 说明上一趟曾进行过记录的交换 if L.rj+1.key L.rj.key W=L.rj；L.rj =L.rj+1； L.rj+1 = W； / 互换记录 lastExchangeIndex = j; i = lastExchangeIndex; / 一趟排序中无序序列中最终一个记录的位置 3、明白什么是 堆？名师归纳

12、总结 堆是满意以下性质的数列r1, r2, ,rn：第 6 页,共 27 页- - - - - - -精选学习资料 - - - - - - - - - rri r 2 i小顶堆 r 2 i1r 大顶堆 i r 2 ir i r 2 i1i第四章 栈和队列重点内容及要求：1、把握栈和队列的结构特点及基本操作（入栈、出栈 /入队、出队） ；栈（后进先出）,队列（先进先出）构造空栈：void InitStack_Sq SqStack & S / 构造一个空栈 S S.elem = new SElemTypemaxsize; S.top =-1; S.stacksize = maxsize; S.in

13、crementsize=incresize; 栈：（入栈）void Push_SqSqStack & S, SElemType e if S.top = S.stacksize-1 incrementStacksize S; / 假如次序栈的空间已满,应为栈扩容 S.elem+S. top = e; / 在栈顶插入数据元素 栈：（入栈）boolPop_Sq SqStack & S, SElemType & e / 如栈不空,就删除 S 的栈顶元素,/ 用 e 返回其值,并返回 TRUE；/ 否就返回 FALSE；if S.top = -1 return FALSE; e = S.elemS.t

14、op- -; return TRUE; 名师归纳总结 - - - - - - -第 7 页,共 27 页精选学习资料 - - - - - - - - - 2、对于次序栈,熟识栈空和栈满的条件；对于 链栈 ,把握其栈空的条件；#include using namespace std; #define INITSIZE 100 #define RESIZE 20 typedef struct int *base; int *top; int stacksize; Sqstack; int InitstackSqstack S S.base=int *mallocINITSIZE*sizeofint

15、; if.S.base return false; S.top=S.base; S.stacksize=INITSIZE; return true; int ClearstackSqstack &S freeS.base; S.base=int *mallocINITSIZE*sizeofint; S.top=S.base; return true; int StackemptySqstack S ifS.base=S.top return true; else return false; int PushSqstack &S,int e ifS.top-S.base=S.stacksize

16、S.base=int *reallocS.base,RESIZE+INITSIZE*sizeofint; if.S.base return false; S.top=S.base+S.stacksize; S.stacksize+=RESIZE; *S.top+=e; return true; int PopSqstack &S,int &e ifS.base=S.top return false; e=*-S.top; return true; int main 名师归纳总结 - - - - - - -第 8 页,共 27 页精选学习资料 - - - - - - - - - Sqstack

17、S; int t,e; InitstackS; cint; / 需要输入元素的个数 whilet- cine; PushS,e; / 进栈 whileS.top.=S.base PopS,e; coutetop; whilep q=p; p=p-next; freeq; S-count=0; return OK; 3、把握栈的典型应用背包问题求解的基本方法；背包问题假设有 n 件体积分别为 w1,w2, wn 的物品和一个能装载体积为T 的背包 .能否从 n 件物品中挑选如干件恰好装满背包 , 即 wi1+wi2+ +wik = T ,就背包问题有解；否就无解 . 名师归纳总结 - - - -

18、 - - -第 9 页,共 27 页精选学习资料 - - - - - - - - - 以 W 1,8,4,3,5,2, T=10 为例1,4,3,2 , 1,4,5 , 8,2和3,5, 2是其解；算法如下void knapsackint w, int T, int n / T 在算法中是剩余的容积,初值为背包的体积 InitStackS; k=0; do while T0 & k=0 / 第 k 件物品可以进栈 PushS, k; T=wk; k+; if T=0 StackTraverseS; / 输出一个解Pop S, k; T+ =wk; / 退出栈顶物品k+; while .Stac

19、kEmptyS | kfront=q-rear-NULL; / 初始化 int QueueEmptyLiQueue *q ifq-rear=NULLreturn 1; 名师归纳总结 - - - - - - -第 10 页,共 27 页精选学习资料 - - - - - - - - - else return 0; / 判空 void enQueue LiQueue *&q,ElemType e QNode *s;s=QNode *mallocsizeofQNode; s-data=e; s-next=NULL; ifq-rear=NULL q-front=q-rear=s; else q-rea

20、r-next=s;q-rear=s; /入队 int deQueue LiQueue *&q,ElemType &e QNode *t;ifq-rear=NULL return0; t=q-front;ifq-front=q-rear q-front=q-rear=NULL; else q-front=q-front-next; e=t-data; freet; return 1; /出队 int deQueue LiQueue *&q,ElemType &e QNode *t;ifq-rear=NULL return0; t=q-front;ifq-front=q-rear q-front=

21、q-rear=NULL; else q-front=q-front-next; e=t-data; break; freet; return 1; /取队头5、对于采纳次序储备结构的循环队列,掌 操作 ；循环队列判定空满有两种方法：握队列为空、队列满的条件,及队列的基本名师归纳总结 - - - - - - -第 11 页,共 27 页精选学习资料 - - - - - - - - - 1.另设一个标志位以区分队列空满；2.少用一个元素空间,当队头指针在队尾指针下一位时,队列为满,当队头指针与队尾指针相同是队列为空；在循环队列下,仍定义 front=rear 时为队空,而判定队满就用两种方法,一是

22、用“ 牺牲一个单元” ,即 rear+1=front（精确记是（ rear+1 ） %m=front ,m是队列容量）时为队满；另一种解法是“ 设标记” 方法,如设标记 tag ,tag 等于 0 情形下,如删除时导致 front=rear 为队空；tag=1 情形下,如因插入导致 front=rear 就为队满；第五章 串和数组重点内容及要求：1、把握 字符串类型的定义及储备表示方法；一般情形之下用 char 定义,串（String ）,或称字符串是由零个或多个字符组成的有限序列；记作：S = a0a1 ai an-1（n0）其中, ai 属于字符集,n 为串的长度,当 n=0 时串为空串储

23、备特点串的实际长度可在这个予定义长度的范畴内随便设定,超过予定义长度的串值就被舍去,称之为“截断” 按这种串的表示方法实现的串的运算时,其基本操作为“字符序列的复制 ”2、把握 数组的定义和储备结构,熟识二维数组中数据元素按行储备的基本方法,会计算元 素的储备地址 ；数组的定义和储备结构数组是线性表的一种扩充, 一维数组即为线性表, 二维数组定义为“其数组元素为一维数组 ”的线性表名师归纳总结 - - - - - - -第 12 页,共 27 页精选学习资料 - - - - - - - - - 3、明白 矩阵压缩储备的目的、原理及基本思路和方法；矩阵压缩储备的目的1 零值元素占了很大空间 ;

24、2 运算中进行了许多和零值的运算,遇除法,仍需判别除数是否为零；原理及基本思路和方法1 尽可能少存或不存零值元素；2 尽可能削减没有实际意义的运算；3 操作便利；即：能尽可能快地找到与下标值 找到同一行或同一列的非零值元；i, j对应的元素,能尽可能快地名师归纳总结 - - - - - - -第 13 页,共 27 页精选学习资料 - - - - - - - - - 4、了 解随机稀疏矩阵的压缩储备方法（三元组次序表、十字链表）；三元组次序表十字链表第六章 二叉树重点内容及要求：名师归纳总结 1、把握 二叉树的定义、特点及相关概念；第 14 页,共 27 页- - - - - - -精选学习资

25、料 - - - - - - - - - 结点的层次 :假设根结点的层次为 的层次为 l+11,第 l 层的结点的子树根结点树的深度： 树中叶子结点所在的最大层次 二叉树的定义二叉树是n（n0）个元素的有限集,它或为空树,或是由一个 根结点 加上两棵分别称为 左子树 和右子树的、互不交的二叉树组成；2、明白 二叉树的性质和储备结构特点,把握二叉树的次序储备结构主要用于完全二叉 树；二叉树的性质：名师归纳总结 1.在二叉树的第i 层上至多有 2i-1 个结点i1 ；第 15 页,共 27 页2. 深度为 k 的二叉树上至多含2k-1 个结点（ k1）；3.对任何一棵二叉树, 如它含有 n0 个叶子

26、结点、n2 个度为2的结点,就必存在关系式：n0 = n2+1；4. 具有 n 个结点的完全二叉树的深度为log2n +1 ；如对含n 个结点的完全二叉树从上到下且从左至右进行1 至n 的编号,就对完全二叉树中任意一个编号为i 的结点：- - - - - - -精选学习资料 - - - - - - - - - 1 如 i=1,就该结点是二叉树的根,无双亲,否就,编号为i/2的结点为其 双亲 结点；2 如 2in,就该结点无左孩子,否就,编号为2i 的结点为其 左孩子 结点；3 如 2i+1n,就该结点无右孩子结点,否就,编号为 2i+1 的结点为其 右孩子 结点；3、把握 二叉树的二叉链表储备

27、结构；名师归纳总结 - - - - - - -第 16 页,共 27 页精选学习资料 - - - - - - - - - 4、明白 二叉树遍历的基本方法（先根次序、中根次序及后根次序遍历二叉树）；5、明白 堆排序的基本方法、明白二叉排序树的基本特点以及如何构造一棵哈夫曼树；树和森林名师归纳总结 - - - - - - -第 17 页,共 27 页精选学习资料 - - - - - - - - - 树和森林的储备结构名师归纳总结 - - - - - - -第 18 页,共 27 页精选学习资料 - - - - - - - - - 第七章 图重点内容及要求：1、明白 图的基本概念和相关术语；图是较树

28、结构更复杂的非线性结构图 Graph 是由一个顶点集 V 和一个弧集 E 构成的数据结构,记作 Graph = V , E ；其中,图的顶点为数据结构中的数据元素,弧的集合 E 是定义在顶点集合 V 上的一个关系；有序对 表示从 v 到 w 的一条弧,并称 v 为弧头, w 为弧尾；谓词 Pv,w 定义了弧 的意义或信息由于 “ 弧 ”是有方向的,因此称由顶点集和弧集构成的图为有向图2、明白 图的储备结构特点（邻接矩阵、邻接表储备结构）；邻接矩阵：名师归纳总结 - - - - - - -第 19 页,共 27 页精选学习资料 - - - - - - - - - 邻接表储备3、明白 图的遍历方法

29、（深度优先搜寻DFS 和广度优先搜寻BFS）；深度优先搜寻 DFS 连通图的深度优先搜寻遍历从图中某个顶点 V0 动身,拜访此顶点,然后依次从 V0 的各个未被拜访的邻接点动身深度优先搜寻遍历图,直至图中全部和 V0 有路径相通的顶点都被拜访到；void DFSGraph G , int v / 从顶点 v 动身,深度优先搜寻遍历连通图 G visitedv = TRUE; VisitFuncv; for w=FirstAdjVexG , v; w.=0; w=NextAdjVexG ,v,w if .visitedw DFSG, w; / 对 v 的尚未拜访的邻接顶点 w / 递归调用 DF

30、S / DFS 非连通图的深度优先搜寻遍历第一将图中每个顶点的拜访标志设为FALSE, 之后搜寻图中每个顶点,假如未被拜访, 就以该顶点为起始点,进行深度优先搜寻遍历,否就连续检查下一顶点；名师归纳总结 - - - - - - -第 20 页,共 27 页精选学习资料 - - - - - - - - - void DFSTraverseGraph G / 对图 G 作深度优先遍历for v=0; vG .vexnum; +v visitedv = FALSE; / 拜访标志数组初始化for v=0; vG .vexnum; +v if .visitedv DFSG , v; / 对尚未拜访的顶

31、点调用 DFS 广度优先搜寻 BFS 从图中的某个顶点V0 动身,并在拜访此顶点之后依次拜访V0的全部 未被拜访 过的邻接点,之后按这些顶点被拜访的先后次序依次拜访它们的邻接点 ,直至图中全部和 V0 有路径相通的顶点都被拜访到；void BFSTraverseGraph G , int v for v=0; vG.vexnum; +v visitedv = FALSE; /初始化拜访标志InitQueueQ; / 置空的帮助队列 Q for v=0; vG.vexnum; +v if .visitedv / v 尚未拜访 / BFSTraverse 以深度优先搜寻DFS 和广度优先搜寻BFS

32、 的算法为框架 , 可以派生出许多有有用价值的应用；1. 求一条从顶点i 到顶点 s 的简洁路径；2. 求两个顶点之间的一条路径长度最短的路径；名师归纳总结 - - - - - - -第 21 页,共 27 页精选学习资料 - - - - - - - - - 3. 求迷宫的最短路径；4、明白 连通网的最小生成树和单源最短路径算法；连通网的最小生成树构造网的一棵最小生成树, 即:在 e 条带权的边中选取n-1 条边不构成回路 , 使“权值之和 ”为最小用（普里姆算法）或（克鲁斯卡尔算法）解决；普里姆算法的基本思想 :取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w；在添加的

33、顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在全部连通顶点 v 和 w 之间的边中取值最小；之后连续往生成树上添加顶点,直至生成树上含有n-1 个顶点为止；克鲁斯卡尔算法的基本思想：考虑问题的动身点 : 为使生成树上边的权值之和达到最小,就应使生成树中每一条边的权值尽可能地小；名师归纳总结 详细做法 : 先构造一个只含n 个顶点的子图SG,然后从权值最第 22 页,共 27 页小的边开头,如它的添加不使SG 中产生回路,就在SG 上加上这条边,如此重复,直至加上n-1 条边为止；- - - - - - -精选学习资料 - - - - - - - - - 单源最短路径算

34、法 求从某个源点到其余各点的最短路径 从源点到顶点 v 的最短路径是全部最短路径中长度最短者；第八章 查找表重点内容及要求：1、把握 线性表的查找算法（次序查找、折半查找、分块查找）；查找表： 静态查找表、动态查找表 静态查找表：次序查找、折半查找、分块查找 动态查找表：二叉查找树、二叉平稳树、链树（数字查找树）次序查找： 以次序表或线性链表表示静态查找表 实现的算法 ：int Search_Seq SSTable ST, KeyType kval 名师归纳总结 / 在次序表 ST 中次序查找其关键字等于kval 的数据元素；如找到,就函数值第 23 页,共 27 页为该元素在表中的位置,否就

35、为0；设置 哨兵 ST.elem0.key = kval; / for i=ST.length; ST.elemi.key .= kval; -i; / 从后往前查找- - - - - - -精选学习资料 - - - - - - - - - return i; / 找不到时, i 为 0 其中“for i=ST.length; ST.elemi.key .= kval; -i;” 仍可以写成“ for i=0; iST.length; i+ ifST.elemi.key = kval Cout” 输出结果：” ST.elemi.key endl; Return i=0; ”折半查找（二分查找）

36、 ：如以有序表表示静态查找表,就查找过程可以按 “折半” 进行；实现的算法 ：int Search_Bin SSTable ST, KeyType kval / 在有序表 ST中折半查找其关键字等于 kval 的数据元素；如找到,就函数值 / 为该元素在表中的位置,否就为 0； low = 1; high = ST.length; / 置区间初值 while low = high mid = low + high / 2; if （kval = ST.elemmid.key return mid; / 找到待查元素 else if kval ST.elemmid.key high = mid - 1; / 内进行查找连续在前半区间 else low = mid + 1; / 连续在后半区间内进行查找 /while 元素 return 0; / 次序表中不存在待查 / Search_Bin 分块查找（索引次序查找）：性能介于 次序查找 和折半查找 之间,对关键字 分块有序 的查找表进行查找操作 索引次序表的查找过程：（1）由索引确定记录所在区间；（1）由索引确定记录所在区间；名师归纳总结 - - - - - - -第 24 页,共 27 页精选学习资料 - - - - - - - - - 详细算