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

数据结构与算法设计知识点试题类型：本课程为考试科目 （闭卷笔试） ， 试题类型包括： 概念填空题（10 %） ， 是非判断题（10 %） ，单项选择题（ 40 %） ，算法填空题（10%） ，算法应用题（20 %)，算法设计题（10 %） 。第一章 绪论重点内容及要求：1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元素之间的关系等） 。数据：所有能被输入 到计算机中，且能被计算机处理的符号 的集合。是计算机操作的对象 的总称。是计算机处理的 信息的 某种特定的符号 表示形式。数据元素： 是数据（集合）中的一个 “ 个体” ，数据结构中的 基本单位，在计算机程序中通常作为一个整体来考虑和处理。数据项：是数据结构中讨论的最小单位，数据元素可以是一个或多个数据项的组合关键码： 也叫关键字（ Key） ，是数据元素中能起标识作用的数据项。其中能起到 唯一标识作用 的关键码称为 主关键码 （简称主码） ；否则称为次关键码。通常，一个数据元素只有一个 主码，但可以有多个次码。关系： 指一个数据集合中数据元素之间的某种相关性。数据结构： 带“结构 ” 的数据元素的集合。这里的结构指元素之间存在的关系。数据类型： 是一个 值的集合 和定义在此集合上的一组操作 的总精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 27 页称。2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。数据结构包括逻辑结构和物理结构两个层次。数据的逻辑结构： 是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示逻辑结构有四种 ：线性结构、树形结构、图状结构、集合结构数据的物理结构： 是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。存储结构： 顺序存储结构和链式存储结构顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系；链式存储结构： 除数据元素本身外， 采用附加的 “ 指针” 表示数据元素之间的逻辑关系。3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。算法： 是为了解决某类问题而规定的一个有限长的操作序列或处理问题的策略一个算法必须满足以下五个重要特性：1有穷性2确定性3可行性 4有输入5有输出设计算法时，通常还应考虑满足以下目标：1.正确性 ，2.可读性 ， 3.健壮性4.高效率与低存储量需求精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 27 页如何估算算法的时间复杂度？算法 = 控制结构+ 原操作（固有数据类型的操作）算法的执行时间= 原操作 (i)的执行次数原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比算法的 空间复杂度定义为 :S(n) = O(g(n)表示随着问题规模n 的增大 ,算法运行所需存储量的增长率与g(n) 的增长率相同。算法的存储量 包括: 1. 输入数据 所占空间2. 程序本身 所占空间3. 辅助变量 所占空间第二章线性表重点内容及要求：1、掌握线性表的顺序存储结构 ，了解顺序表的存储特点 （数据元素在内存中依次顺序存储）， 优点：可随机存取访问；缺点：结点的插入/删除操作不方便。线性表：是一种最简单的数据结构，也是构造其它各类复杂数据结构的基础。一个数据元素的有序（次序）集 。它有 顺序和链式两种存储表示方法。线性表必有 ：1集合中必存在唯一的一个“ 第一元素 ”精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 27 页2集合中必存在唯一的一个“ 最后元素 ”3除最后元素在外，均有唯一的后继；4除第一元素之外，均有唯一的前驱定义如下：typedef int ElemType; typedef struct ElemType*elem; /存储数据元素的一维数组；int length; /线性表当前长度；int listsize; /当前分配数组容量；SqList; Void InitSqList(SqList A,int maxsize)/初始化线性表 A.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!A.elem) exit(0); A.length = 0; A.listsize = LIST_INIT_SIZE; return ; 2、了解线性表的链式存储结构，重点掌握 带头结点的单链表的基本操作（结点的插入与删除运算） ，了解单向循环链表和双向链表存储表示方法。单链表：用一组地址任意的存储单元存放线性表中的数据元素。以元素 (数据元素的映象) + 指针 (指示后继元素存储位置) = 结点(表示数据元素或数据元素的映象 ) 单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器3、了解 有序线性表的特点（顺序有序表、有序链表）。有序线性表： 线性表中的数据元素相互之间可以比较，并且数据精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 27 页元素在线性表中 依值非递减或非递增有序排列，即 aiai-1或 aiai-1(i = 2,3, n)，则称该线性表为 有序表 (Ordered List)4、学会 对线性表设计相关的算法进行相应的处理。第三章 排序重点内容及要求：1、掌握对顺序表数据记录进行排序的基本思路和常规操作（比较、 移动） ，了解排序算法的稳定性问题。2、掌握简单 选择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点及时间复杂度。排序： 将一组 “ 无序” 的记录序列按某一关键字调整为“ 有序” 的记录序列。若整个排序过程 不需要访问外存 便能完成，则称此类排序问题为内部排序 ；反之则为外部排序。选择排序：从记录的无序子序列中 “ 选择” 关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度基本代码如下for(i=0;in-1;i+)/*外循环控制趟数，n 个数选 n-1 趟*/ k=i;/*假设当前趟的第一个数为最值, 记在 k 中 */ for(j=i+1;jn;j+)/*从下一个数到最后一个数之间找最值*/ if(akaj)/*若其后有比最值更大的*/ k=j;/*则将其下标记在k 中*/ if(k!=i)/*若 k 不为最初的i 值，说明在其后找到比其更大的数*/ t=ak;ak=ai;ai=t;/*则交换最值和当前序列的第一个数*/ 插入排序：插入排序是将一个数据插入到已经排好序的有序数据精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 27 页中，从而得到一个新的、个数加一的有序数据。代码如下：void InsertSort ( SqList &L) / 对顺序表L 作插入排序for ( i=2; i=L.length; +i ) if ( L.ri.key L.ri-1.key ) 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、了解什么是 堆？堆是满足下列性质的数列r1, r2, ，rn：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 27 页(小顶堆) (大顶堆 ) 第四章栈和队列重点内容及要求：1、掌握栈和队列的结构特点及基本操作（入栈、出栈 /入队、出队） 。栈（后进先出），队列（先进先出）构造空栈：voidInitStack_Sq (SqStack &S) / 构造一个空栈 S S.elem = new SElemTypemaxsize;S.top =-1; S.stacksize = maxsize; S.incrementsize=incresize; 栈： （入栈）voidPush_Sq (SqStack &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.top - -; return TRUE; 122iiiirrrr122iiiirrrr精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 27 页2、对于顺序栈，熟悉栈空和栈满的条件；对于 链栈 ，掌握其栈空的条件。#include using namespace std; #define INITSIZE 100 #define RESIZE 20 typedef struct int *base; int *top; int stacksize; Sqstack; int Initstack(Sqstack S) S.base=(int *)malloc(INITSIZE*sizeof(int); if(!S.base) return false; S.top=S.base; S.stacksize=INITSIZE; return true; int Clearstack(Sqstack &S) free(S.base); S.base=(int *)malloc(INITSIZE*sizeof(int); S.top=S.base; return true; int Stackempty(Sqstack S) if(S.base=S.top) return true; else return false; int Push(Sqstack &S,int e) if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(RESIZE+INITSIZE)*sizeof(int); if(!S.base) return false; S.top=S.base+S.stacksize; S.stacksize+=RESIZE; *S.top+=e; return true; int Pop(Sqstack &S,int &e) if(S.base=S.top) return false; e=*-S.top; return true; int main() 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 27 页 Sqstack S; int t,e; Initstack(S); cint; / 需要输入元素的个数while(t-) cine; Push(S,e); / 进栈while(S.top!=S.base) Pop(S,e); coutetop; while(p) q=p; p=p-next; free(q); S-count=0; return OK; 3、掌握栈的典型应用背包问题求解的基本方法。背包问题假设有 n 件体积分别为 w1,w2,wn 的物品和一个能装载体积为T 的背包.能否从 n 件物品中选择若干件恰好装满背包, 即 wi1+wi2+wik = T ,则背包问题有解；否则无解 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 27 页以 W(1,8,4,3,5,2), T=10 为例(1,4,3,2 ), (1,4,5 ), (8,2)和(3,5, 2)是其解。算法如下void knapsack(int w, int T, int n) / T 在算法中是剩余的容积，初值为背包的体积InitStack(S); k=0; do while (T0 & k=0) / 第 k 件物品可以进栈Push(S, k); T =wk; k+; if (T=0) StackTraverse(S); / 输出一个解Pop (S, k); T+ =wk; / 退出栈顶物品k+; while (!StackEmpty(S) | kfront=q-rear-NULL; / 初始化int QueueEmpty(LiQueue *q) if(q-rear=NULL)return 1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 27 页else return 0; / 判空void enQueue( LiQueue *&q,ElemType e) QNode *s;s=(QNode *)malloc(sizeof(QNode); s-data=e; s-next=NULL; if(q-rear=NULL) q-front=q-rear=s; else q-rear-next=s;q-rear=s; /入队int deQueue( LiQueue *&q,ElemType &e) QNode *t;if(q-rear=NULL) return0; t=q-front;if(q-front=q-rear) q-front=q-rear=NULL; else q-front=q-front-next; e=t-data; free(t); return 1; /出队int deQueue( LiQueue *&q,ElemType &e) QNode *t;if(q-rear=NULL) return0; t=q-front;if(q-front=q-rear) q-front=q-rear=NULL; else q-front=q-front-next; e=t-data; break; free(t); return 1; /取队头5、对于采用顺序存储结构的循环队列，掌握队列为空、队列满的条件，及队列的基本操作 。循环队列判断空满有两种方法：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 27 页1.另设一个标志位以区分队列空满；2.少用一个元素空间，当队头指针在队尾指针下一位时，队列为满，当队头指针与队尾指针相同是队列为空。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即 rear+1=front（准确记是（ rear+1 ）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag ，tag 等于 0 情况下，若删除时导致front=rear为队空；tag=1 情况下，若因插入导致front=rear则为队满。第五章串和数组重点内容及要求：1、掌握 字符串类型的定义及存储表示方法。一般情况之下用char定义，串（String ） ，或称字符串是由零个或多个字符组成的有限序列。记作：S = a0a1ai an -1（n0）其中， ai 属于字符集，n 为串的长度，当n=0 时串为空串存储特点串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“ 截断” 按这种串的表示方法实现的串的运算时，其基本操作为“ 字符序列的复制”2、掌握 数组的定义和存储结构，熟悉二维数组中数据元素按行存储的基本方法，会计算元 素的存储地址。数组的定义和存储结构数组是线性表的一种扩充， 一维数组即为线性表， 二维数组定义为“ 其数组元素为一维数组 ” 的线性表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 27 页3、了解 矩阵压缩存储的目的、原理及基本思路和方法。矩阵压缩存储的目的1) 零值元素占了很大空间 ; 2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。原理及基本思路和方法1) 尽可能少存或不存零值元素；2) 尽可能减少没有实际意义的运算；3) 操作方便。即：能尽可能快地找到与下标值(i, j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 27 页4、了 解随机稀疏矩阵的压缩存储方法（三元组顺序表、十字链表）。三元组顺序表十字链表第六章二叉树重点内容及要求：1、掌握 二叉树的定义、特点及相关概念。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 27 页结点的层次 :假设根结点的层次为1,第 l 层的结点的子树根结点的层次为 l+1树的深度： 树中叶子结点所在的最大层次二叉树的定义二叉树是n（n0）个元素的有限集，它或为空树，或是由一个 根结点 加上两棵分别称为 左子树和右子树的、互不交的二叉树组成。2、了解 二叉树的性质和存储结构特点，掌握二叉树的顺序存储结构主要用于完全二叉树。二叉树的性质：1.在二叉树的第i 层上至多有 2i-1 个结点(i1) 。2. 深度为 k 的二叉树上至多含2k-1 个结点（ k1） 。3.对任何一棵二叉树， 若它含有 n0 个叶子结点、n2 个度为2的结点，则必存在关系式：n0 = n2+1。4. 具有 n 个结点的完全二叉树的深度为log2n +1 。若对含n 个结点的完全二叉树从上到下且从左至右进行1 至n 的编号，则对完全二叉树中任意一个编号为i 的结点：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 27 页(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其 双亲结点；(2) 若 2in，则该结点无左孩子，否则，编号为2i 的结点为其 左孩子 结点；(3) 若 2i+1n，则该结点无右孩子结点，否则，编号为 2i+1 的结点为其 右孩子 结点。3、掌握 二叉树的二叉链表存储结构。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 27 页4、了解 二叉树遍历的基本方法（先根次序、中根次序及后根次序遍历二叉树）。5、了解 堆排序的基本方法、了解二叉排序树的基本特点以及如何构造一棵哈夫曼树。树和森林精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 27 页树和森林的存储结构精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 27 页第七章图重点内容及要求：1、了解 图的基本概念和相关术语。图是较树结构更复杂的非线性结构图 Graph 是由一个顶点集V 和一个弧集E 构成的数据结构，记作Graph = (V , E ) 。其中，图的顶点为数据结构中的数据元素，弧的集合E 是定义在顶点集合V 上的一个关系。有序对表示从v 到 w 的一条弧，并称v 为弧头， w 为弧尾。谓词P(v,w) 定义了弧的意义或信息由于 “ 弧 ” 是有方向的，因此称由顶点集和弧集构成的图为有向图2、了解 图的存储结构特点（邻接矩阵、邻接表存储结构）。邻接矩阵：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 27 页邻接表存储3、了解 图的遍历方法（深度优先搜索DFS 和广度优先搜索BFS） 。深度优先搜索 DFS 连通图的深度优先搜索遍历从图中某个顶点V0 出发，访问此顶点，然后依次从V0 的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0 有路径相通的顶点都被访问到。void DFS(Graph G, int v) / 从顶点 v 出发，深度优先搜索遍历连通图G visitedv = TRUE; VisitFunc(v); for (w=FirstAdjVex(G , v); w!=0; w=NextAdjVex(G ,v,w) ) if (!visitedw) DFS(G, w); / 对 v 的尚未访问的邻接顶点w / 递归调用DFS / DFS 非连通图的深度优先搜索遍历首先将图中每个顶点的访问标志设为FALSE, 之后搜索图中每个顶点，如果未被访问， 则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 27 页void DFSTraverse(Graph G ) / 对图G 作深度优先遍历for (v=0; vG .vexnum; +v) visitedv = FALSE; / 访问标志数组初始化for (v=0; vG .vexnum; +v) if (!visitedv) DFS(G , v); / 对尚未访问的顶点调用DFS 广度优先搜索 BFS 从图中的某个顶点V0 出发，并在访问此顶点之后依次访问V0的所有 未被访问 过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点 ，直至图中所有和 V0 有路径相通的顶点都被访问到。void BFSTraverse(Graph G, int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 / BFSTraverse 以深度优先搜索DFS 和广度优先搜索BFS 的算法为框架 , 可以派生出很多有实用价值的应用。1. 求一条从顶点i 到顶点 s 的简单路径；2. 求两个顶点之间的一条路径长度最短的路径；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 27 页3. 求迷宫的最短路径。4、了解 连通网的最小生成树和单源最短路径算法。连通网的最小生成树构造网的一棵最小生成树, 即:在 e 条带权的边中选取n-1 条边(不构成回路 ), 使“ 权值之和 ” 为最小用（普里姆算法）或（克鲁斯卡尔算法）解决；普里姆算法的基本思想:取图中任意一个顶点v 作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1 个顶点为止。克鲁斯卡尔算法的基本思想：考虑问题的出发点 : 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法 : 先构造一个只含n 个顶点的子图SG， 然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在SG 上加上这条边，如此重复，直至加上n-1 条边为止。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 27 页单源最短路径算法求从某个源点到其余各点的最短路径从源点到顶点 v 的最短路径是所有最短路径中长度最短者。第八章查找表重点内容及要求：1、掌握 线性表的查找算法（顺序查找、折半查找、分块查找）。查找表： 静态查找表、动态查找表静态查找表：顺序查找、折半查找、分块查找动态查找表：二叉查找树、二叉平衡树、链树（数字查找树）顺序查找： 以顺序表或线性链表表示静态查找表实现的算法 ：int Search_Seq (SSTable ST, KeyType kval) / 在顺序表ST中顺序查找其关键字等于kval 的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 ST.elem0.key = kval; / 设置 哨兵 for (i=ST.length; ST.elemi.key != kval; -i); / 从后往前查找精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 27 页 return i; / 找不到时， i为 0 其中“ for (i=ST.length; ST.elemi.key != kval; -i);”还可以写成“for (i=0; iST.length; i+) if(ST.elemi.key = kval) Cout”输出结果：” ST.elemi.key endl; Return (i=0); ”折半查找（二分查找） ：若以有序表表示静态查找表，则查找过程可以按 “ 折半” 进行。实现的算法 ：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 ID.elemhigh.key) return 0; / 给定值 kval 大于查找表中所有关键字 while ( low =high & !found ) / 折半查找索引表，确定记录查找区间 mid = (low+high)/2; if ( kval ID.elemmid.key ) low = mid +1; else found = TRUE; low = mid; /while s = ID.elemlow.stadr; / 经索引表查找后，下一步的查找范围定位在第low块 if ( low data.key) return TRUE; / 查找成功 else if ( kval data.key) f = p ; p = p-lchild; / 在左子树中继续查找 else f = p; p = p-rchild; / 在右子树中继续查找 / while return FALSE; / 查找不成功 / SearchBST4、了哈希表的相关概念和基本原理（哈希表的定义、哈希函数的构造、处理冲突的方法、哈希表查找）。查找的过程 为给定值 依次和关键字集合中各个关键字 进行比较查找的效率 取决于和给定值 进行比较 的关键字 个数。因此在一般情况下， 需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key) 作为关键字为key 的记录在表中的位置，通常称这个函数f(key) 为哈希函数。哈希表的定义：根据设定的 哈希函数H(key) 和所选中的 处理冲突的方法 ， 将一精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 27 页组关键字 映象到 一个有限的、地址连续的地址集(区间) 上，并以关键字在地址集中的 “ 象” 作为相应记录在表中的 存储位置 ，如此构造所得的查找表称之为 “ 哈希表” 。哈希函数的构造方法：如果没有关键字，必须进行数字化处理处理冲突的方法：“ 处理冲突 ” 的实际含义是：为产生冲突的地址寻找下一个 哈希地址。1. 开放定址法；2. 链地址法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 27 页