《数据结构复习要点说明.doc》由会员分享，可在线阅读，更多相关《数据结构复习要点说明.doc（14页珍藏版）》请在课桌文档上搜索。
1、. . A熟练掌握 B理解 C了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。C四类数据组织结构：集合、线性表、树形、图状结构 C数据的存储方式：顺序存储和链式存储。B2.算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B本章重点：分析算法时间复杂度例1. 下面关于算法说法错误的是 A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的D例2.以下那一个术语与数据的存储结构无关？ A栈 B. 哈希表 C. 线索树 D. 双向链表A例3.
2、求下段程序的时间复杂度：void mergesortint m;ifm=/2;mergesort;mergesort;merge;其中mergesort用于对数组an归并排序,调用方式为mergesort;,merge用于两个有序子序列的合并,是非递归函数,时间复杂度为。解：分析得到的时间复杂度的递归关系：为merge所需的时间,设为cnc为常量。因此令 ,有有第二章：线性表1.线性表的基本运算：. C2.线性表的顺序存储利用静态数组或动态存分配。相应的表示与操作 A3.线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。 A4.顺序存储与链式存储的比较：基于时间的考虑-分别适用于静态
3、的和动态的操作：比如静态查找和插入删除；基于空间的考虑-. B这也适用于后面用两种方式存储的其他数据结构。本章重点：很熟悉顺序表,单链表、双链表,循环链表的基本操作；并学会在各种链表上进行一些算法设计与基本操作类似的操作或组合,请仔细复习。例4假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。 题目分析因为两链表已按元素值递增次序排列,将其合并时,均从第一个结点起进行比较,将小的链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时,将链
4、表结点逆置。voidUnionla,lb分别是带头结点的两个单链表的头指针,链表中的元素值按递增序排列,本算法将两链表合并成一个按元素值递减次序排列的单链表。 pa=la-next; pb=lb-next;pa,pb分别是链表la和lb的工作指针la-next=null;la作结果链表的头指针,先将结果链表初始化为空。 while 当两链表未访问结束 ifdatadata q=pa-next;将pa 的后继结点暂存于q。pa-next=la-next;将pa结点链于结果表中,同时逆置。la-next=pa;pa=q;恢复pa为当前待比较结点。elseq=pb-next; 将pb 的后继结点暂存
5、于q。pb-next=la-next; 将pb结点链于结果表中,同时逆置。la-next=pb;pb=q; 恢复pb为当前待比较结点。while 将la表的剩余部分链入结果表,并逆置。 q=pa-next; pa-next=la-next; la-next=pa; pa=q; while q=pb-next; pb-next=la-next; la-next=pb; pb=q; 算法Union结束。注意：1此处q用作暂存后继结点,操作后pa或pb还回原指向位置；这与我们原来不改变pa或pb的指向,增加一个q=pa或pb作为摘取结点进行添加操作起到的作用一样。2 此处要完成逆序插入操作故用头插法
6、基于头指针la或lb,注意尾插法附设一个尾指针,基于该指针插入的可完成顺序插入。注意：逆序另一种方式也要掌握！练习：练习题2 编程167.判断带头结点双向循环链表L是否对称相等.8. 设计一个算法判断单链表带头结点是否是递增的注意比排序算法应该简单,链表排序也要会实现9. 设计一个算法判断有序表A是否是有序表B的子集即表A中的元素在B中。思考：如果递归程序怎么写？第三章：栈与队列1.两种特殊线性表：分别有后进先出、先进先出的特性。 B2.栈的顺序表示与实现利用静态数组或动态存分配 A 注意栈顶指针的初始位置不同,进出栈,栈空栈满的实现语句有差别！举例：若定义typedef struct SEl
7、emType *base; SElemType *top; int stacksize;/当前栈能使用的最大容量 SqStack; SqStack s;top的初始值指向栈底,即top=base；栈空条件：s. top =s. base 此时不能出栈栈满条件：s.top-s.base=s.stacksize进栈操作：*s.top+=e; 或*s.top=e; s.top+;退栈操作：e=*-s.top；或s.top-； e=*s.top若定义：typedef struct SElemType baseMAXSIZE; int top; SqStack; SqStack s;top的初始值为0时
8、: 栈空条件：s. top =0此时不能出栈栈满条件：s.top = MAXSIZE进栈操作：s.bases.top+=e; 退栈操作：e=s.base-s.toptop的初始值为-1时: 栈空条件：s. top = -1此时不能出栈栈满条件：s.top = MAXSIZE-1进栈操作：s.base+s.top=e; 退栈操作：e=s.bases.top-3.栈的链式表示与实现B 4.队列的顺序表示与实现循环队列 A设两个指针：Q.front 指向队列头元素；Q.rear 指向队列尾元素的下一个位置注意队中若Q.rear 指向队列尾元素,进出队,实现语句有差别！初始状态空队列：Q.front
9、= Q.rear=0队头指针进1: Q.front = % MAXSIZE队尾指针进1: Q.rear = % MAXSIZE;队列初始化： Q.front = Q.rear = 0;队空条件： Q.front = Q.rear;队满条件： % MAXSIZE = Q.front 队列长度：%MAXSIZE6.队列的链式表示与实现 B本章重点：顺序栈的初始条件、操作,循环队列的初始条件、操作本章难点：栈的设计与使用,队列的设计与使用主要结合后面树和图中的应用复习例5链栈与顺序栈比起来优势在于。没有预设容量的限制例6计算算术表达式的值时,可用两个栈作辅助工具。对于给出的一个表达式,从左向右扫描它
10、的字符,并将操作数放入栈S1中,运算符放入栈S2中,但每次扫描到运算符时,要把它同S2的栈顶运算符进行优先级比较,当扫描到的运算符的优先级不高于栈顶运算符的优先级时,取出栈S1的栈顶和次栈顶的两个元素,以及栈S2的栈顶运算符进行运算将结果放入栈S1中得到的结果依次用T1、T2等表示。为方便比较,假设栈S2的初始栈顶为运算符的优先级低于加、减、乘、除中任何一种运算。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。步骤栈S1栈S2输入的算术表达式按字符读入初始A-B*C/D+E/F1AA-B*C/D+E/F2A-B*C/D+E/F3AB-B*C/D+E/F4AB-*C/D
11、+E/F5ABC-*C/D+E/F6AT1注：T1=B*C-/D+E/F7AT1D-/D+E/F8AT2注：T2=T1/DT3 注：T3=A-T2-+E/F9T3E+E/F10T3E+/F11T3EF+/F12T3T4注：T4=E/FT5注：T5= T3+ T4+例7将两个栈存入数组V1.m应如何安排最好？这时栈空、栈满的条件是什么？,入栈和出栈的操作是什么？分析：为了增加存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的空间时,应将两栈的栈底分别设在存空间的两端,这样只有当两栈顶指针相邻即值之差的绝对值为1时才产生溢出。设栈S1和栈S2共享向量V1.m,初始时,栈S1的栈顶指针top0
12、=0,栈S2的栈顶指针top1=m+1,当top0=0为栈S1空,top1=m+1为栈S2空；当top0=0并且top1=m+1时为两栈全空。当top1-top0=1时为栈满。入栈核心操作 S1: V+top0=x1; S2: V-top1=x2出栈核心操作 S1: x1=Vtop0-; S2: x2=Vtop1+例8如果用一个循环数组base0.MAX-1表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear,而改置计数器count用以记录队列中结点的个数。1编写实现队列的三个基本运算：判空、入队、出队2队列中能容纳元素的最多个数是多少typedefstruct ElemTy
13、pe baseMAX;int front,count; /front是指向队头元素针,count是队列中元素个数。CQueue; /定义类型标识符。判空：int Empty /q是CQueue类型的变量 if return；elsereturn; /空队列入队: int EnQueueifprintf；exit; q.base%MAX=x; /x入队 q.count+; return; /队列中元素个数增加1,入队成功。出队: int DelQueueif printf；return;x=q.baseq.front;q.front=%MAX; /计算新的队头指针q.count-;return;
14、 队列中能容纳的元素的个数为MAX。第四章：串1.串的基本概念C2.串的顺序表示与实现两种存储方式A 特别的模式匹配算法之KMP算法 B本章重点：串的定长顺序存储和堆分配存储、掌握一些常规的串操作自己会用和会编写本章难点：串的模式匹配快速算法KMP例9. 串的定长顺序存储缺点在于存在情况。截断例10已知u=xyxyxyxxyxy；t=xxy；ASSIGNs,u；ASSIGNv,SUBSTRs,INDEXs,t,LENt+1；ASSIGNm,ww求REPLACE,m= _。 xyxyxywwy例1114设字符串S=aabaabaabaac,P=aabaac1给出S和P的next值和nextval
15、值； 2若S作主串,P作模式串,试给出利用BF算法和KMP算法的匹配过程。11p的next与nextval值分别为012123和002003。 2利用BF算法的匹配过程： 第一趟匹配： aabaabaabaac aabaac 第二趟匹配： aabaabaabaac aa 第三趟匹配： aabaabaabaac a 第四趟匹配： aabaabaabaac aabaac第五趟匹配： aabaabaabaac aa第六趟匹配： aabaabaabaac a第七趟匹配： aabaabaabaac 利用KMP算法的匹配过程： 第一趟匹配：aabaabaabaac aabaaci=6,j=6,nextva
16、l=3 第二趟匹配：aabaabaabaac baac 第三趟匹配：aabaabaabaac baac例12一般串定位函数Index, 设S的串长为n,T的串长为m,则最坏时间复杂度 ；而改进的Index_KMP 时间复杂度为。第五章：数组和广义表1.数组的存储结构：以行为主序、以列为主序的地址映像函数 B2矩阵的压缩存储：1特殊阵：包括对称阵、三角阵、带状阵利用其特性压缩存储到一维数组B2稀疏阵 利用的是三元组顺序表来表示 B 用十字链表表示C本次考试不做要求3.广义表定义与存储表示 B本次考试不做要求本章重点：地址映像函数的计算包括数组和特殊矩阵例13已知n阶下三角矩阵A即当ij时,有ai
17、j=0,按照压缩存储的思想,可以将其主对角线以下所有元素依次存放于一维数组B中,请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。答：n阶下三角矩阵元素Aij1=i,j=j。第1列有n个元素,第j列有n-j+1个元素,第1列到第j-1列是等腰梯形,元素数为n+/2,而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储,其元素aij在一维数组B中的存储位置k与i和j的关系为：k=n+n-+1/2+=/2+i第六章：二叉树与树1.二叉树的定义和性质： B 几个特殊的二叉树：满二叉树、完全二叉树、二叉排序树、平衡二叉树 B2.二叉树的顺序存储： C3.二
18、叉树的链式存储： 用二叉链表表示与实现 A4.二叉树的遍历：先中、后序遍历及应用,相应递归算法和非递归算法 A5.线索化二叉树利用二叉链表n+1空指针域来存放某遍历下指向该结点的直接前驱或直接后继,使得蕴含更多信息B6.二叉树的应用：算术表达式,霍夫曼树最优二叉树,判定树 B7.树的定义和存储表示：. B8.树和森林和二叉树的转换 B9.树与森林的遍历 B本章重点：很熟悉二叉树在二叉链表表示下的基本操作的递归算法和遍历的非递归算法,请仔细复习。本章难点：二叉树含排序树、平衡树的递归算法和非递归算法。线索化二叉树及相应操作,重在理解,不考编程！例14引入二叉线索树的目的是 A将非线性序列转化成某
19、种线性序列；加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一A例15二叉链表在线索化后,仍不能有效求解的问题是 。A前先序线索二叉树中求前先序后继 B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱 D后序线索二叉树中求后序后继 D例16在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为-1右孩子的平衡因子为0,则应作 型调整以使其平衡。平衡因子=左子树深度-右子树深度A.LL 单向右旋 B. LR 先左后右双向旋转C. RL 先右后左双向旋转 D. RR 单向左旋B例17一
20、棵非空的二叉树其先序序列和后序序列正好相反,画出这棵二叉树的形状。先序序列是根左右 后序序列是左右根,可见对任意结点,若至多只有左子女或至多只有右子女,均可使前序序列与后序序列相反,图示如下：例18：已知二叉树结点结构如下：用C语言表示 typedef struct BiNodeElemType data; struct BiNode *lchild,*rchild;int val; BiNode,*BiTree; 其中val域表示该结点的子含孩子结点的个数。开始时,val域值均为0,T为指向某二叉树根结点的指针。请写算法填写该二叉树中每个结点的val域。递归算法如下：int writeVal
21、 if root-val=0; else iflchild=NULL&root-rchild=NULL root-val=1; else root-val=writeVallchild+writeValrchild; return root-val; 例19编写一个算法,将指针S所指的结点插入到根结点指针为T的二叉排序树中,若已存在则不再插入返回0；否则返回1。递归的算法见教材int Insert_BST BiTree p, q; /p指向当前访问的结点 if T=S; else p=T; while q = p; /q指向p结点的双亲结点 if data.key data.key p = p
22、-lchild; else ifdata.key p-data.key p = p-rchild;else p=NULL; if data.key = q-data.key return 0; if data.key data.key q-lchild = S; else q-rchild = S; return 1;例20编写一个算法,计算平衡二叉树中所有结点的平衡因子解：计算一个结点bt的bf的值递归模型如下：f: bt-bf不存在当bt=NULLf: bt-bf=0 当 bt-lchild=NULL&bt-rchild=NULLf: bt-bf=bt的右子树的高度左子树的高度其它情况 可
23、选用先序的方式统计出各个结点的平衡因子如何求高度呢？递归模型如下：f: 不存在当bt=NULLf: 当 bt-lchild=NULL&bt-rchild=NULLf:bt的左子树和右子树的高度的最大值其它情况 int Height/求树的高度int max1,max2;if return 0;else iflchild=NULL&bt-rchild=NULL return 1;elsemax1=Heightlchild;max2=Heightrchild;return max1max2?max1+1:max2+1;void Countbf /求所有结点的bfififlchild=NULL&bt
24、-rchild=NULLbf-bf=0;elseCountbflchild;Countbfrchild;bt-bf= Heightrchild-Heightlchild;实质上可以将上面求bf和求高度合二为一。int Countbf1/求所有结点的bf,返回对应结点高度值int max1,max2;if return 0;iflchild=NULL&bt-rchild=NULLbf-bf=0;return1;elsemax1=Heightlchild;max2=Heightrchild;bt-bf= max2-max1;return max1max2?max1+1:max2+1;例21设给出一
25、段报文： CAST CAST SAT AT A TASA；字符集合是 C, A, S, T ,各个字符出现的频度是 W 2, 7, 4, 5 ；试设计赫夫曼编码,画出赫夫曼树。若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11；试说明赫夫曼编码比此方案的优越之处。解答见ppt练习1设计一个算法,删除该二叉树,释放所有结点2设计一算法判断二叉链表存储的二叉树是否结构对称左右子树结点结构对称相同3试写出复制一棵二叉树的算法。二叉树采用标准结构。4习题六编程 除打星号的部分 5. 设计一个算法,寻找二叉树中满足特定数值x的第一个结点 6. 设计一个算法,统计二叉树中满足特定
26、数值x结点的个数相应的变形：统计度为0,1,2的结点第七章 图1.图的定义、基本概念： B2.图的存储方式：邻接矩阵和邻接表 A3.图的遍历深度优先和广度优先 A4.图的连通性和生成树 B带权图的最小生成树及算法 B5.图的最短路径问题 B6.拓扑排序、AOE网中的关键路径 B本章重点：熟悉邻接矩阵和邻接表的表示方法,学会编写遍历算法深度优先和广度优先遍历算法以及一些遍历算法的应用。请仔细复习。本章难点：图的一些算法如最小生成树、最短路径、关键路径；这部分重在理解算法思想和设计过程例22将邻接矩阵g装换为邻接表Gvoid MatToListint i,j, N=g.n;/N表示顶点数ArcNo
27、de *p;G=mallocsizeof;fori=0;i/给邻接表中所有顶点的赋值并使其指针域置空G-verticesi.data=g.vexsi;G-verticesi.firstedge=NULL;fori=0;i/*对邻接阵扫描每一行的每一列*/for=0;j-/对第i个顶点进行建立链表由后向前添加ifp=mallocsizeof;/新建结点p-adjvex=j;p-info=g.edgesij;/存放边的权值p-next=G-verticesi.firstedge;/前插G-verticesi.firstedge=p;G-n=N; G-e=g.e;例23试利用深度优先遍历DFS判断该
28、图在邻接表存储下是否是连通的,若是连通的返回,若是不连通的返回图的连通分量个数,空图则返回。int vistedMAXNUM; /全局数组void DFS /*以Vi为出发点对邻接表图进行DFS */ArcNode *p;printfverticesi.data;/访问顶点Vivisitedi=1; /标记Vi已访问,标志为p= G-verticesi.firstarc; /取Vi边表的头指针 while /依次搜索Vi的邻接点Vj,if adjvex /若Vj尚未访问,则以Vj为出发点向纵深搜索DFS adjvex;p=p-next; /*判断无向图是否连通,若连通返回1*/int Conn
29、ectsint i,flag=1; /flag为标记是否连通for i=0;ivexnum;i+ visitedi=0 ; /标志向量visted初始化,标志为DFS;for i=0;ivexnum;i+ if /还有vi未访问过,修改标记flag量 flag=0;break;return flag;例24下面是求连通网的最小生成树的prim算法：集合VT,ET分别放顶点和边,初始为 1 ,下面步骤重复n-1次: a： 2 ；b： 3 ；最后： 4 。1AVT,ET为空 BVT为所有顶点,ET为空 CVT为网中任意一点,ET为空 DVT为空,ET为网中所有边2A. 选i属于VT,j不属于VT,
30、且i,j上的权最小 B选i属于VT,j不属于VT,且i,j上的权最大 C选i不属于VT,j不属于VT,且i,j上的权最小 D选i不属于VT,j不属于VT,且i,j上的权最大3A顶点i加入VT,i,j加入ET B. 顶点j加入VT,i,j加入ET C. 顶点j加入VT,i,j从ET中删去 D顶点i,j加入VT,i,j加入ET4AET 中为最小生成树 B不在ET中的边构成最小生成树 CET中有n-1条边时为生成树,否则无解 DET中无回路时,为生成树,否则无解C A B A例25P182 算法 7.12思考： 用邻接矩阵存储怎么实现？练习1.假设有向图以邻接表存储,计算Vi顶点的出度和入度。2.在
31、有向无环图中,试利用深度优先遍历DFS求出一个拓扑排序序列。提示：由某点出发进行深度优先遍历,退出DFS函数调用时记录此时顶点序号,最先退出DFS函数的顶点是拓扑序列中的最后一个顶点,依次下去.得到一个逆向拓扑有序序列；再将此顶点序号反向输出即可。3.设计一个深度优先搜索算法,以判断用邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vjij的路径。第八章 查找基本概念C静态查找表中常用的方法：顺序查找、折半查找、分块查找分别适用于一般、有序、分块有序的表相应算法和性能分析A 动态查找表：二叉排序树的建立、查找、删除；A 二叉平衡树哈希表：哈希函数的构造和冲突处理方法 本章重点：查找树的建立和查
32、找含静态折半查找、动态查找树、哈希函数和冲突方法本章难点：二叉排序树删除；平衡排序树的插入例26在有序表A1.12中,采用二分查找算法查等于A12的元素,所比较的元素下标依次为_。6,9,11,12例27设散列表为HT 0.12,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为： H0=key % 13; 注:%是求余数运算 Hi=Hi-1+REV%11+1 % 13; i=1,2,3,m-1其中,函数REVx表示颠倒10进制数x的各位,如REV37=73,REV7=7等。若插入的关键码序列为。试画出插入这8个关键码后的散列表；计算搜索成功的平均搜索长度ASL。1散列地
33、址0123456789101112关键字27532311920818比较次数311111122ASLsuss =11/8第九章 排序稳定/不稳定排序,排序和外排序 C插入排序方法：直接插入排序、折半插入排序、希尔插入排序 算法与性能分析 A交换排序方法：冒泡排序、快速排序 A选择排序方法：简单选择排序、堆排序 A二路归并排序、基数排序 B排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序On2On2O1稳定折半插入排序On2On2O1稳定二路插入排序On2On2On稳定本次考试不要求表插入排序On2On2O1稳定本次考试不要求起泡排序On2On2O1稳定直接选择排序On2On2O
34、1不稳定2,2,1希尔排序On1.3On1.3O1不稳定3,2,2,1快速排序Onlog2nOn2Olog2n不稳定2,2,1堆排序Onlog2nOnlog2nO1不稳定2,1,12-路归并排序Onlog2nOnlog2nOn稳定基数排序O d* O d* O 稳定本章重点：各种排序方法的实现、性能比较与选择例28.某排序方法的稳定性是指。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0n log n的排序方法 D以上都不对 B例29.对序列15,9,7,8,20,-1,4进行排序,进行一趟后数据的排列变为4,9,-1,8,20,7,15；则采用的是 排序。A. 选择 B. 快速 C. 希尔 D. 冒泡若上题的数据经一趟排序后的排列为9,15,7,8,20,-1,4,则采用的是 排序。A选择 B. 堆 C. 直接插入 D. 冒泡 C C例30.有一组数据15,9,7,8,20,-1,7,4 用快速排序的划分方法进行一趟划分后数据的排序为 按递增序。 A下面的B,C,D都不对。 B9,7,8,4,-1,7,15,20C20,15,8,9,7,-1,4,7 D. 9,4,7,8,7
