数据结构与算法设计知识点.doc

.数据结构与算法设计知识点试题类型：本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。第一章 绪论重点内容及要求：1、 了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元素之间的关系等）。数据： 所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，数据结构中的基本单位，在计算机程序中通常作为一个整体来考虑和处理。数据项：是数据结构中讨论的最小单位，数据元素可以是一个或多个数据项的组合关键码：也叫关键字（Key），是数据元素中能起标识作用的数据项。其中能起到唯一标识作用的关键码称为主关键码（简称主码）；否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多个次码。关系：指一个数据集合中数据元素之间的某种相关性。数据结构：带“结构”的数据元素的集合。这里的结构指元素之间存在的关系。数据类型：是一个值的集合和定义在此集合上的一组操作的总称。2、 掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。数据结构包括逻辑结构和物理结构两个层次。数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。存储结构：顺序存储结构和链式存储结构顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系；链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。3、 了解算法分析的基本方法，掌握算法时间复杂度相关的概念。算法：是为了解决某类问题而规定的一个有限长的操作序列或处理问题的策略一个算法必须满足以下五个重要特性：1有穷性 2确定性 3可行性4有输入 5有输出设计算法时，通常还应考虑满足以下目标： 1.正确性，2.可读性， 3.健壮性 4.高效率与低存储量需求如何估算 算法的时间复杂度？算法 = 控制结构 + 原操作 （固有数据类型的操作）算法的执行时间 = 原操作(i)的执行次数原操作(i)的执行时间算法的执行时间与 原操作执行次数之和成正比 算法的空间复杂度定义为:S(n) = O(g(n)表示随着问题规模 n 的增大,算法运行所需存储量的增长率与 g(n) 的增长率相同。算法的存储量包括:1. 输入数据所占空间2. 程序本身所占空间3. 辅助变量所占空间第二章 线性表重点内容及要求：1、 掌握线性表的顺序存储结构，了解顺序表的存储特点（数据元素在内存中依次顺序存储），优点：可随机存取访问；缺点：结点的插入/删除操作不方便。线性表：是一种最简单的数据结构，也是构造其它各类复杂数据结构的基础。一个数据元素的有序（次序）集。它有顺序和链式两种存储表示方法。 线性表必有：1集合中必存在唯一的一个“第一元素”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、了解有序线性表的特点（顺序有序表、有序链表）。有序线性表：线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 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;/*则交换最值和当前序列的第一个数*/插入排序：插入排序是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。代码如下：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：(小顶堆) (大顶堆) 第四章 栈和队列重点内容及要求：1、掌握栈和队列的结构特点及基本操作（入栈、出栈/入队、出队）。栈（后进先出），队列（先进先出）构造空栈：void InitStack_Sq (SqStack &S) / 构造一个空栈S S.elem = new SElemTypemaxsize; S.top =-1; S.stacksize = maxsize; S.incrementsize=incresize; 栈：（入栈）void Push_Sq(SqStack &S, SElemType e) if (S.top = S.stacksize-1) incrementStacksize (S); / 如果顺序栈的空间已满，应为栈扩容 S.elem+S. top = e; / 在栈顶插入数据元素栈：（入栈）bool Pop_Sq (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回TRUE； / 否则返回FALSE。 if (S.top = -1) return FALSE; e = S.elemS.top- -; return TRUE;2、对于顺序栈，熟悉栈空和栈满的条件；对于链栈，掌握其栈空的条件。#include using namespace std;#define INITSIZE 100#define RESIZE 20typedef 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() 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,则背包问题有解； 否则无解. 以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;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;elseq-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;elseq-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;elseq-front=q-front-next;e=t-data;break;free(t);return 1; /取队头5、对于采用顺序存储结构的循环队列，掌握队列为空、队列满的条件，及队列的基本操作。循环队列判断空满有两种方法： 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 = a0a1aian-1 （n0）其中，ai属于字符集， n为串的长度，当n=0 时串为空串存储特点串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”2、掌握数组的定义和存储结构，熟悉二维数组中数据元素按行存储的基本方法，会计算元素的存储地址。数组的定义和存储结构数组是线性表的一种扩充，一维数组即为线性表，二维数组定义为“其数组元素为一维数组”的线性表3、了解矩阵压缩存储的目的、原理及基本思路和方法。矩阵压缩存储的目的1) 零值元素占了很大空间;2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。原理及基本思路和方法1) 尽可能少存或不存零值元素；2) 尽可能减少没有实际意义的运算；3) 操作方便。 即： 能尽可能快地找到与下标值(i, j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。4、了解随机稀疏矩阵的压缩存储方法（三元组顺序表、十字链表）。三元组顺序表十字链表第六章 二叉树重点内容及要求：1、掌握二叉树的定义、特点及相关概念。结点的层次:假设根结点的层次为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 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。3、掌握二叉树的二叉链表存储结构。4、了解二叉树遍历的基本方法（先根次序、中根次序及后根次序遍历二叉树）。5、了解堆排序的基本方法、了解二叉排序树的基本特点以及如何构造一棵哈夫曼树。树和森林树和森林的存储结构 第七章 图重点内容及要求：1、了解图的基本概念和相关术语。图是较树结构更复杂的非线性结构图Graph是由一个顶点集 V 和一个弧集 E构成的数据结构，记作Graph = (V , E )。 其中，图的顶点为数据结构中的数据元素，弧的集合E是定义在顶点集合V上的一个关系。有序对 表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。 谓词 P(v,w) 定义了弧 的意义或信息由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图2、了解图的存储结构特点（邻接矩阵、邻接表存储结构）。邻接矩阵： 邻接表存储 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, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。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. 求两个顶点之间的一条路径长度最短的路径；3. 求迷宫的最短路径。4、了解连通网的最小生成树和单源最短路径算法。连通网的最小生成树构造网的一棵最小生成树, 即:在 e 条带权的边中选取 n-1 条边(不构成回路), 使“权值之和”为最小用（普里姆算法）或（克鲁斯卡尔算法）解决；普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。 克鲁斯卡尔算法的基本思想：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使 SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 单源最短路径算法求从某个源点到其余各点的最短路径从源点到顶点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); / 从后往前查找 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, KeyTyp