数据结构专升本补习ppt课件

数据结构专升本补习,主讲：王晓斌,目录,复习提纲各章基本要求习题选解考题解析,第一部分,复习提纲,第一章绪论,一.基本概念和术语1.数据2.数据元素3.数据对象4.数据结构及其形式化描述DS（，）5.四种基本数据结构6.数据类型,第一章绪论,二.算法描述三.算法的基本特性及“好”算法的特征四.简单时间复杂度的分析,第二章线性表,一.线性表的逻辑结构及基本操作二.顺序存储结构及其特点CONSTmaxlen=线性表可能达到的最大长度；TYPEsqlisttp=RECORDelem:ARRAYmaxlenOFelemtp；last:0maxlenEND;,第二章线性表,三.单链表及其特点TYPEpointer=nodetype;nodetype=RECORDdata:elemtp;next:pointerEND;linkisttp=pointer;,第二章线性表,四.循环链表、双向链表及其特点五.一元多项式的单链表表示六.难点1.顺序存储结构编写算法时注意事项2.单链表的建立3.单链表中前驱结点的记录4.双向链表中插入结点时的语序,第三章栈和队列,一.栈的特点及基本操作二.栈的应用（读写递归算法时注意事项）三.队列的特点及基本操作四.循环队列：队空、队满的判定,第五章数组和广义表,一.数组及其操作二.数组元素的存放方式及存储地址的计算三.广义表的定义、性质及操作,第六章树和二叉树,一.基本概念二.二叉树的性质三.二叉树的存储结构四.二叉树的遍历五.树、森林和二叉树之间的转换六.哈夫曼树的构造,第七章图,一.图的基本术语二.图的存储结构：邻接矩阵、邻接表三.一定存储结构下图的遍历四.图的典型应用1.最小生成树2.拓扑排序3.关键路径4.最短路径,第九章查找,一.基本术语二.顺序表查找：顺序、折半、分块三.二叉排序树及其构造四.Hash表的构造,第十章内部排序,一.基本概念1.排序2.排序方法的稳定性二.排序方法的基本思想三.会模拟排序过程四.能够读懂排序算法,第二部分,各章基本内容,第三部分,习题选解,第一章习题,设n为正整数，试确定下列程序段中各语句的频度。1.(1)count:=0;1(2)FORi:=1TOnDOn+1(3)FORj:=1TOiDO(i+1)(4)FORk:=1TOjDO(j+1)(5)count:=count+1;j,n,i=1,j=1,i,n,i=1,n,i,i=1,j=1,第一章习题,2.(1)FORi:=2TOnDOn(2)FORj:=2TOi-1DOn(n-1)/2(3)x:=x+1;(n-2)(n-1)/2,第二章习题,.写算法,将单循环链表逆转。PROCex2_3(ls:linkisttp);p:=ls.next;ls.next:=ls;WHILEplsDOq:=p.next;p.next:=ls.next;ls.next:=p;p:=qENDP;ex2_3,4.试写出在单链表中搜索x的算法。若x存在表中，则输出它在表中的序号；否则将x插在表尾。PROCexam1(la:linkisttp;x:elemtp):integer;pre:=la;p:=la.next;j:=1;WHILE(pNILCANDp.datax)DO【pre:=p;p:=p.next;j:=j+1】；IF(pNIL)THENRETURN(j)ELSE【new(s);s.data:=x;s.next:=NIL;pre.next:=s;RETURN(0)】ENDP；,第二章习题,5.两个集合用线性表表示，采用单链表作为存储结构，且其中元素递增有序，编写求两个集合交集的算法。PROCexam2(la,lb:linkisttp;VARlc:linkisttp);new(lc);pc:=lc;pa:=la.next;pb:=lb.next;WHILE(paNILANDpbNIL)DOIFpa.data=pb.dataTHEN【new(s);s.data:=pa.data;pc.next:=s;pc:=s;pa:=pa.next;pb:=pb.next】ELSEIFpa.datapb.dataTHENpa:=pa.nextELSEpb:=pb.next;pc.next:=NILENDP;,第二章习题,第三章习题,第三章习题,试写一个判断表达式中圆括号是否配对出现的算法。假设表达式存于数组a1.n中,且a是字符数组FUNCex3_2(a:ARRAY1.nOFchar;n:integer):boolean;INISTACK(S);PUSH(S,#);FORi:=1TOnDOIFai=(THENPUSH(S,ai);IFai=)THENx:=POP(S);IFx(THENRETURN(false);x:=POP(S);IFEMPTY(S)ANDx=#THENRETURN(true)ELSERETURN(false)ENDF;ex3_2,第三章习题,假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素（不设头指针），试编写相应的置空队列、入队列和出队列的算法。(1)置空队列PROCclear(VARrear:linkisttp);p:=rear.next;p.next:=p;rear:=pENDP;,第三章习题,(2)入队列操作PROCadd(VARrear:linkisttp;x:elemtp);new(s);s.data:=x;s.next:=rear.next;rear.next:=s;rear:=sENDP;,第三章习题,(3)出队列函数FUNCdel(VARrear:linkisttp):elemtp;IFrear.next=rearTHENRETURN(NULL);h:=rear.next;x:=h.next.data;q:=h.next;h.next:=q.next;IFh.next=hTHENrear:=h;dispose(q);RETURN(x)ENDF;,4.假设sequ0.m-1存放循环队列的元素,同时设rear和quelen分别指示循环队列中队尾元素的位置和包含的元素个数。试给出此循环队列的队空和队满条件，并编写相应的入队和出队算法。假定形式描述循环队列为TYPEsqRECORDsequ:ARRAY0.m-1OFelemtp;rear,quelen:integerEND;,第三章习题,(1)队满条件：q.quelen=m队空条件：q.quelen=0(2)入队算法PROCadd_sq(VARq:sq;x:elemtp);IFq.quelen=mTHENERROR(overflow);q.rear:=(q.rear+1)MODm;q.sequq.rear:=x;q.quelen:=q.quelen+1ENDP;,(3)出队算法FUNCadd_sq(VARq:sq):elemtp;IFq.quelen=0THEN【ERROR(队列为空);RETURN(NULL)】；front:=(q.rear-q.quelen+m)MODm;j:=(front+1)MODm;y:=q.sequj;q.quelen:=q.quelen-1;RETURN(y)ENDF;,第五章习题,1设有数组B，按行主顺序存放在1000开始的连续空间中，若元素长度为2，试计算，和B，元素的起始地址，并请回答至少给B数组分配多少个存储单元?解：(1)B，的存储位置LOC-1,3,4=1000+(-1-(-1)*(5-0+1)*(4-(-2)+1)+(3-0)*(4-(-2)+1)+(4-(-2)*2=1054，的存储位置LOC0,0,0=1000+(0-(-1)*(5-0+1)*(4-(-2)+1)+(0-0)*(4-(-2)+1)+(0-(-2)*2=1088（）分配给数组B的单元数至少为（）*（）*（）*420,4.一棵n个结点的完全二叉树采用顺序存储结构，试写一非递归算法实现对该树的前序遍历。类型描述：CONSTmaxsize=;TYPEsqbitree=ARRAY1.maxsizeOFelemtp;,PROCexam4(bt:sqbitree;n:integer);j:=1;INISTACK(S);WHILEj=nORNOTEMPTY(S)DOIFj=nTHEN【visite(btj);PUSH(S,j);j:=2*j】ELSE【j:=POP(S);j:=2*j+1】ENDP;,.,第七章习题,1.对如下有向图：,试写出：（1）邻接矩阵（2）邻接表（3）以顶点1出发按深度和广度优先搜索遍历图的顶点序列,.,0110000001010100000000110,.,1,2,3,4,5,2,3,5,2,4,3,4,DFS：12534BFS：12354,.,2.对如下无向图：,试写出：（1）邻接矩阵（2）邻接表（3）以顶点1出发按深度和广度优先搜索遍历图的顶点序列,第七章习题,.,0110010111110010100101110,.,1,2,3,4,5,2,3,1,1,2,2,3,DFS：12354BFS：12345,3,4,5,5,2,5,4,.,第七章习题,3.对如下无向图，分别用Prim和Kruskal算法求最小生成树,6,.,6,4,2,8,3,6,（1）Prim方法,6,.,6,4,2,8,3,6,（2）Kruskal方法,6,.,第七章习题,4.对如下AOE网，求出各事件的ve,vl和各活动的l和e。并指出关键路径。,.,a4=3,a2=6,a3=7,a1=8,a5=10,a6=10,a7=9,a8=13,a12=2,a9=6,a11=8,a10=19,.,第七章习题,5.对下图，写出拓扑有序序列及入度域变化过程,.,a1,a2,a3,a3,a4,a4,a5,a6,a3,a5,a5,a6,a3,a6,a2,a4,a5,a6,第九章习题,1、在算法binsrch中，若做下述一个修改，能否正确工作：（1）将“low：=mid+1”改为“low：=mid”；（2）将“high：=mid-1”改为“high：=mid”；试分别用修改后的算法，在有序表069，087，094，127，148，199，254，271，301，355中查找k=199和k=084并得出结论。,设k=199第一次：low=1，high=10，mid=5第二次：low5，high10，mid7第三次：low5，high7，mid6成功！,设k=084第一次：low=1，high=10，mid=5第二次：low1，high5，mid3第三次：low1，high3，mid2第四次：low1，high2，mid1第五次：low1，high2，mid1死循环！,第九章习题,2、现有R1R2R3R4R5R6共6个记录依次存入哈希表A，表A共有6个存储单元，地址为05。某哈希函数结果为：H（k1）=H（k2）=2H（k3）=H（k4）=0H（k5）=H（k6）=5用线性探测再散列解决冲突。试写出各记录存入时,表A的状态。,R1,012345,R3,R1,R2,R6,R5,R4,R1,R2,R3,R1,R2,R3,R1,R2,R4,R3,R1,R2,R5,R4,第十章习题,1。判断以下序列是否为堆。如果不是，则把它调整为堆。（1）100，86，48，73，35，39，42，57，66，21（2）12，70，33，65，24，56，48，92，86，33,.,（1）100，86，48，73，35，39，42，57，66，21,100864873353942576621,是堆,.,（2）12，70，33，65，24，56，48，92，86，33,12703365245648928633,不是堆,.,调整后：12，24，33，65，33，56，48，92，86，70,12243365335648928670,第十章习题,2。以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序