《数据结构专升本补习.ppt》由会员分享，可在线阅读，更多相关《数据结构专升本补习.ppt（63页珍藏版）》请在三一办公上搜索。
1、数据结构专升本补习,主讲：王晓斌,目 录,复习提纲各章基本要求习题选解考题解析,第一部分,复习提纲,第一章 绪 论,一.基本概念和术语 1.数据 2.数据元素 3.数据对象 4.数据结构及其形式化描述 DS（，）5.四种基本数据结构 6.数据类型,第一章 绪 论,二.算法描述三.算法的基本特性及“好”算法的特征四.简单时间复杂度的分析,第二章 线性表,一.线性表的逻辑结构及基本操作二.顺序存储结构及其特点CONST maxlen=线性表可能达到的最大长度；TYPE sqlisttp=RECORD elem:ARRAYmaxlen OF elemtp；last:0maxlen END;,第二章
2、线性表,三.单链表及其特点TYPE pointer=nodetype;nodetype=RECORD data:elemtp;next:pointer END;linkisttp=pointer;,第二章 线性表,四.循环链表、双向链表及其特点五.一元多项式的单链表表示六.难点 1.顺序存储结构编写算法时注意事项 2.单链表的建立 3.单链表中前驱结点的记录 4.双向链表中插入结点时的语序,第三章 栈和队列,一.栈的特点及基本操作二.栈的应用（读写递归算法时注意事项）三.队列的特点及基本操作四.循环队列：队空、队满的判定,第五章 数组和广义表,一.数组及其操作二.数组元素的存放方式及存储地址的
3、计算三.广义表的定义、性质及操作,第六章 树和二叉树,一.基本概念二.二叉树的性质三.二叉树的存储结构四.二叉树的遍历五.树、森林和二叉树之间的转换六.哈夫曼树的构造,第七章 图,一.图的基本术语二.图的存储结构：邻接矩阵、邻接表三.一定存储结构下图的遍历四.图的典型应用 1.最小生成树 2.拓扑排序 3.关键路径 4.最短路径,第九章 查找,一.基本术语二.顺序表查找：顺序、折半、分块三.二叉排序树及其构造四.Hash表的构造,第十章 内部排序,一.基本概念 1.排序 2.排序方法的稳定性二.排序方法的基本思想三.会模拟排序过程四.能够读懂排序算法,第二部分,各章基本内容,第三部分,习题选解
4、,第一章 习题,设n为正整数，试确定下列程序段中各语句的频度。1.(1)count:=0;1(2)FOR i:=1 TO n DO n+1(3)FOR j:=1 TO i DO(i+1)(4)FOR k:=1 TO j DO(j+1)(5)count:=count+1;j,n,i=1,j=1,i,n,i=1,n,i,i=1,j=1,第一章 习题,2.(1)FOR i:=2 TO n DO n(2)FOR j:=2 TO i-1 DO n(n-1)/2(3)x:=x+1;(n-2)(n-1)/2,第二章 习题,.写算法,将单循环链表逆转。PROC ex2_3(ls:linkisttp);p:=l
5、s.next;ls.next:=ls;WHILE pls DO q:=p.next;p.next:=ls.next;ls.next:=p;p:=q ENDP;ex2_3,4.试写出在单链表中搜索x的算法。若x存在表中，则输出它在表中的序号；否则将x插在表尾。PROC exam1(la:linkisttp;x:elemtp):integer;pre:=la;p:=la.next;j:=1;WHILE(pNIL CAND p.datax)DO【pre:=p;p:=p.next;j:=j+1】；IF(pNIL)THEN RETURN(j)ELSE【new(s);s.data:=x;s.next:=N
6、IL;pre.next:=s;RETURN(0)】ENDP；,第二章 习题,5.两个集合用线性表表示，采用单链表作为存储结构，且其中元素递增有序，编写求两个集合交集的算法。PROC exam2(la,lb:linkisttp;VAR lc:linkisttp);new(lc);pc:=lc;pa:=la.next;pb:=lb.next;WHILE(paNIL AND pbNIL)DO IF pa.data=pb.data THEN【new(s);s.data:=pa.data;pc.next:=s;pc:=s;pa:=pa.next;pb:=pb.next】ELSE IF pa.datapb
7、.data THEN pa:=pa.next ELSE pb:=pb.next;pc.next:=NILENDP;,第二章 习题,第三章 习题,第三章 习题,试写一个判断表达式中圆括号是否配对出现的算法。假设表达式存于数组a1.n中,且a是字符数组FUNC ex3_2(a:ARRAY1.n OF char;n:integer):boolean;INISTACK(S);PUSH(S,#);FOR i:=1 TO n DO IF ai=(THEN PUSH(S,ai);IF ai=)THEN x:=POP(S);IF x(THEN RETURN(false);x:=POP(S);IF EMPTY(
8、S)AND x=#THEN RETURN(true)ELSE RETURN(false)ENDF;ex3_2,第三章 习题,假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素（不设头指针），试编写相应的置空队列、入队列和出队列的算法。(1)置空队列PROC clear(VAR rear:linkisttp);p:=rear.next;p.next:=p;rear:=pENDP;,第三章 习题,(2)入队列操作PROC add(VAR rear:linkisttp;x:elemtp);new(s);s.data:=x;s.next:=rear.next;rear.next:=s;re
9、ar:=sENDP;,第三章 习题,(3)出队列函数FUNC del(VAR rear:linkisttp):elemtp;IF rear.next=rear THEN RETURN(NULL);h:=rear.next;x:=h.next.data;q:=h.next;h.next:=q.next;IF h.next=h THEN rear:=h;dispose(q);RETURN(x)ENDF;,4.假设sequ0.m-1存放循环队列的元素,同时设rear和quelen分别指示循环队列中队尾元素的位置和包含的元素个数。试给出此循环队列的队空和队满条件，并编写相应的入队和出队算法。假定形式描
10、述循环队列为TYPE sqRECORD sequ:ARRAY0.m-1 OF elemtp;rear,quelen:integer END;,第三章 习题,(1)队满条件：q.quelen=m 队空条件：q.quelen=0(2)入队算法PROC add_sq(VAR q:sq;x:elemtp);IF q.quelen=m THEN ERROR(overflow);q.rear:=(q.rear+1)MOD m;q.sequq.rear:=x;q.quelen:=q.quelen+1ENDP;,(3)出队算法FUNC add_sq(VAR q:sq):elemtp;IF q.quelen=0
11、 THEN【ERROR(队列为空);RETURN(NULL)】；front:=(q.rear-q.quelen+m)MOD m;j:=(front+1)MOD m;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，的存储位置
12、 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个结点的完全二叉树采用顺序存储结构，试写一非递归算法实现对该树的前序遍历。类型描述：CONST maxsize=;TYPE sqbitree=ARRAY1.maxsize OF elemtp;,PROC exam4(bt:sqbitree;n:integer);j:=1;INISTACK(S);WHILE j=n OR NOT EMPTY(S)DO IF j=n THEN【visite
13、(btj);PUSH(S,j);j:=2*j】ELSE【j:=POP(S);j:=2*j+1】ENDP;,第七章习题,1.对如下有向图：,试写出：（1）邻接矩阵（2）邻接表（3）以顶点1出发按深度 和广度优 先搜 索遍历 图的顶点序列,0 1 1 0 00 0 0 0 10 1 0 1 00 0 0 0 00 0 1 1 0,1,2,3,4,5,2,3,5,2,4,3,4,DFS：12534BFS：12354,2.对如下无向图：,试写出：（1）邻接矩阵（2）邻接表（3）以顶点1出发按深度 和广度 优 先搜 索遍历 图的顶点序列,第七章习题,0 1 1 0 01 0 1 1 11 1 0 0 1
14、0 1 0 0 10 1 1 1 0,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.对下图，写出拓扑有序序列
15、及入度域变化过程,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，high
16、7，mid6成功！,设k=084 第一次：low=1，high=10，mid=5 第二次：low1，high5，mid3 第三次：low1，high3，mid2 第四次：low1，high2，mid1 第五次：low1，high2，mid1死循环！,第九章习题,2、现有R1 R2 R3 R4 R5 R6共6个记录依次存入哈希表A，表A共有6个存储单元，地址为05。某哈希函数结果为：H（k1）=H（k2）=2 H（k3）=H（k4）=0 H（k5）=H（k6）=5用线性探测再散列解决冲突。试写出各记录存入时,表A的状态。,R1,012345,R3,R1,R2,R6,R5,R4,R1,R2,R3,
17、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,100 86 48 73 35 39 4257 66 21,是堆,（2）12，70，33，65，24，56，48，92，86，33,12 70 33 65 24 56 4892 86 33,不是堆,调整后：12，24，33，65，33，56，48，92，86，70,12
18、 24 33 65 33 56 4892 86 70,第十章习题,2。以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序排列，试编写此算法。,为了处理方便，假设单链表具有头结点，p是搜索指针，q记录正在处理的结点。PROC chap10-2(la:linkisttp);IF la.nextNIL THEN【q:=la.next.next;la.next.next:=NIL;WHILE qNIL DO【pre:=la;p:=la.next;x:=q.data;WHILE pNIL CAND xp.data DO【pre:=p;p:=p.next】;t:=q.next;pre.next:=q;q.next:=p;q:=t】ENDP;,第四部分,考题解析,
