《数据结构专升本补习课件》由会员分享，可在线阅读，更多相关《数据结构专升本补习课件（63页珍藏版）》请在金锄头文库上搜索。
1、数据结构专升本补习主讲：王晓斌数据结构专升本补习目 录n复习提纲n各章基本要求n习题选解n考题解析数据结构专升本补习第一部分复习提纲数据结构专升本补习第一章 绪 论一. 基本概念和术语 1. 数据 2. 数据元素 3. 数据对象 4. 数据结构及其形式化描述 DS（，） 5. 四种基本数据结构 6. 数据类型数据结构专升本补习第一章 绪 论二. 算法描述三. 算法的基本特性及“好”算法的特征四. 简单时间复杂度的分析数据结构专升本补习第二章 线性表一. 线性表的逻辑结构及基本操作二. 顺序存储结构及其特点CONST maxlen=线性表可能达到的最大长度；TYPE sqlisttp=RECOR
2、D elem:ARRAYmaxlen OF elemtp； last:0maxlen END;数据结构专升本补习第二章 线性表三. 单链表及其特点TYPE pointer=nodetype; nodetype=RECORD data:elemtp; next:pointer END; linkisttp=pointer;数据结构专升本补习第二章 线性表四. 循环链表、双向链表及其特点五. 一元多项式的单链表表示六. 难点 1. 顺序存储结构编写算法时注意事项 2. 单链表的建立 3. 单链表中前驱结点的记录 4. 双向链表中插入结点时的语序数据结构专升本补习第三章 栈和队列一. 栈的特点及基本
3、操作二. 栈的应用（读写递归算法时注意事项）三. 队列的特点及基本操作四. 循环队列：队空、队满的判定数据结构专升本补习第五章 数组和广义表一. 数组及其操作二. 数组元素的存放方式及存储地址的计算三. 广义表的定义、性质及操作数据结构专升本补习第六章 树和二叉树一. 基本概念二. 二叉树的性质三. 二叉树的存储结构四. 二叉树的遍历五. 树、森林和二叉树之间的转换六. 哈夫曼树的构造数据结构专升本补习第七章 图一. 图的基本术语二. 图的存储结构：邻接矩阵、邻接表三. 一定存储结构下图的遍历四. 图的典型应用 1. 最小生成树 2. 拓扑排序 3. 关键路径 4. 最短路径数据结构专升本补习
4、第九章 查找一. 基本术语二. 顺序表查找：顺序、折半、分块三. 二叉排序树及其构造四. Hash表的构造数据结构专升本补习第十章 内部排序一. 基本概念 1. 排序 2. 排序方法的稳定性二. 排序方法的基本思想三. 会模拟排序过程四. 能够读懂排序算法数据结构专升本补习第二部分各章基本内容数据结构专升本补习第三部分习题选解数据结构专升本补习第一章第一章 习题习题设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 (
5、j+1) (5) count:=count+1; jni=1j=1ini=1nii=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:=ls.next; ls.next:=ls; WHILE pls DO q:=p.next; p.next:=ls.ne
6、xt; ls.next:=p; p:=q ENDP; 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；第二章第二章 习题习题数据结构专升
7、本补习5. 两个集合用线性表表示，采用单链表作为存储结构，且其中元素递增有序，编写求两个集合交集的算法。PROC exam2(la,lb:linkisttp;VAR lc: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
8、.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(S)
9、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.
10、next:=rear.next; rear.next:=s; rear:=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分
11、别指示循环队列中队尾元素的位置和包含的元素个数。试给出此循环队列的队空和队满条件，并编写相应的入队和出队算法。假定形式描述循环队列为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:=
12、x; q.quelen:=q.quelen+1ENDP;数据结构专升本补习(3)出队算法FUNC add_sq(VAR q:sq):elemtp; IF q.quelen=0 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，元素的起始地址，并请回
13、答至少给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个结点的完全二叉树采用顺序存储结构，试写一非递归算法实现对该树的前序遍历。类型描述
14、：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(btj); PUSH(S,j); j:=2*j 】 ELSE 【 j:=POP(S); j:=2*j+1 】ENDP;数据结构专升本补习第七章习题第七章习题1. 1. 对如下有向图：对如下有向图：对如下有向图：对如下有向图：试写出：（试写出：（试写出：（试写出：（
15、1 1）邻接矩阵）邻接矩阵）邻接矩阵）邻接矩阵 （2 2）邻接表）邻接表）邻接表）邻接表 （3 3）以顶点）以顶点）以顶点）以顶点1 1出发按出发按出发按出发按深度深度深度深度 和广度优和广度优和广度优和广度优 先搜先搜先搜先搜 索遍历索遍历索遍历索遍历 图图图图的顶点序列的顶点序列的顶点序列的顶点序列数据结构专升本补习0110000001010100000000110数据结构专升本补习123452352434DFS：12534BFS：12354数据结构专升本补习2. 2. 对如下无向图：对如下无向图：对如下无向图：对如下无向图：试写出：试写出：试写出：试写出： （1 1）邻接矩阵）邻接矩阵）
16、邻接矩阵）邻接矩阵 （2 2）邻接表）邻接表）邻接表）邻接表 （3 3）以顶点）以顶点）以顶点）以顶点1 1出发按深度出发按深度出发按深度出发按深度 和广度和广度和广度和广度 优优优优 先搜先搜先搜先搜 索遍历索遍历索遍历索遍历 图的顶点序列图的顶点序列图的顶点序列图的顶点序列第七章习题第七章习题数据结构专升本补习0110010111110010100101110数据结构专升本补习123452311223DFS：12354BFS：123453455254数据结构专升本补习第七章习题3. 对如下无向图，分别用Prim和Kruskal算法求最小生成树6 621217 74 411112 21919
17、101010108 83 36 6数据结构专升本补习642836（1）Prim方法6 621217 74 411112 21919101010108 83 36 6数据结构专升本补习642836（2）Kruskal方法6 621217 74 411112 21919101010108 83 36 6数据结构专升本补习第七章习题4. 对如下AOE网，求出各事件的ve, vl和各活动的l和e。并指出关键路径。a a4 4=3=3a a2 2=6=6a a3 3=7=7a a1 1=8=8a a5 5=10=10a a6 6=10=10a a7 7=9=9a a8 8=13=13a a1212=2=
18、2a a9 9=6=6a a1111=8=8a a1010=19=19数据结构专升本补习a a4 4=3=3a a2 2=6=6a a3 3=7=7a a1 1=8=8a a5 5=10=10a a6 6=10=10a a7 7=9=9a a8 8=13=13a a1212=2=2a a9 9=6=6a a1111=8=8a a1010=19=19计算结果为：计算结果为：计算结果为：计算结果为：顶点顶点顶点顶点 Ve Vl Ve Vl 活动活动活动活动 弧弧弧弧 持续持续持续持续T e l l-e T e l l-e 关键活动关键活动关键活动关键活动 V1 0 0 a1 8 0 5 5 V1
19、0 0 a1 8 0 5 5 V2 8 13 a2 6 0 0 0 a2 V2 8 13 a2 6 0 0 0 a2 V3 6 6 a3 7 0 9 9 V3 6 6 a3 7 0 9 9 V4 16 16 a4 3 8 13 5 V4 16 16 a4 3 8 13 5 V5 7 16 a5 10 6 6 0 a5 V5 7 16 a5 10 6 6 0 a5 V6 20 29 a6 10 6 17 11 V6 20 29 a6 10 6 17 11 V7 16 27 a7 9 7 18 11 V7 16 27 a7 9 7 18 11 V8 35 35 a8 13 7 16 9 V8 35
20、 35 a8 13 7 16 9 a9 6 20 29 9 a9 6 20 29 9 a10 19 16 16 0 a10 a10 19 16 16 0 a10 a11 8 16 27 11 a11 8 16 27 11 a12 2 16 27 11 a12 2 16 27 11 Max + Min - Max + Min -数据结构专升本补习第七章习题5. 对下图，写出拓扑有序序列及入度域变化过程a aa1 11a aa2 22a aa4 44a aa3 33a aa5 55a aa6 66数据结构专升本补习a aa1 11a aa2 22a aa4 44a aa3 33a aa5 55a
21、aa6 66a1a2a3a3a4a4a5a6a3a5a5a6a3a6a2a4a5a6数据结构专升本补习第九章习题第九章习题1 1、在算法、在算法、在算法、在算法binsrch binsrch 中，若做下述一个修改，能否正确工作：中，若做下述一个修改，能否正确工作：中，若做下述一个修改，能否正确工作：中，若做下述一个修改，能否正确工作：（1 1）将）将）将）将“low“low：=mid+1”=mid+1”改为改为改为改为“low“low：=mid”=mid”；（2 2）将）将）将）将“high“high：=mid-1”=mid-1”改为改为改为改为“high“high：=mid”=mid”；试分
22、别用修改后的算法，在有序表试分别用修改后的算法，在有序表试分别用修改后的算法，在有序表试分别用修改后的算法，在有序表069069，087087，094094，127127，148148，199199，254254，271271，301301，355355中查找中查找中查找中查找k=199k=199和和和和k=084k=084并得出结论。并得出结论。并得出结论。并得出结论。数据结构专升本补习 设设设设k=199k=199 第一次：第一次：第一次：第一次：low=1low=1，high=10high=10，mid=5mid=5 第二次：第二次：第二次：第二次：lowlow5 5，highhigh1
23、010，midmid7 7 第三次：第三次：第三次：第三次：lowlow5 5，highhigh7 7，midmid6 6成功！成功！ 设设设设k=084k=084 第一次：第一次：第一次：第一次：low=1low=1，high=10high=10，mid=5mid=5 第二次：第二次：第二次：第二次：lowlow1 1，highhigh5 5，midmid3 3 第三次：第三次：第三次：第三次：lowlow1 1，highhigh3 3，midmid2 2 第四次：第四次：第四次：第四次：lowlow1 1，highhigh2 2，midmid1 1 第五次：第五次：第五次：第五次：lowl
24、ow1 1，highhigh2 2，midmid1 1死死循环！循环！069069，087087，094094，127127，148148，199199，254254，271271，301301，35535512345678910数据结构专升本补习第九章习题第九章习题2 2、现有、现有、现有、现有R R1 1 R R2 2 R R3 3 R R4 4 R R5 5 R R6 6共共共共6 6个记录依次存入哈希表个记录依次存入哈希表个记录依次存入哈希表个记录依次存入哈希表A A，表，表，表，表A A共共共共有有有有6 6个存储单元，地址为个存储单元，地址为个存储单元，地址为个存储单元，地址为05
25、05。某哈希函数结果为：。某哈希函数结果为：。某哈希函数结果为：。某哈希函数结果为： H H（k k1 1）=H=H（k k2 2）=2 =2 H H（k k3 3）=H=H（k k4 4）=0 =0 H H（k k5 5）=H=H（k k6 6）=5=5用线性探测再散列解决冲突。试写出各记录存入时用线性探测再散列解决冲突。试写出各记录存入时用线性探测再散列解决冲突。试写出各记录存入时用线性探测再散列解决冲突。试写出各记录存入时, , 表表表表A A的状态。的状态。的状态。的状态。数据结构专升本补习R1012345R3R1R2R6R5R4R1R2R3R1R2R3R1R2R4R3R1R2R5R4
26、数据结构专升本补习第十章习题第十章习题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，21100864873353942576621是堆数据结构专升本补习（2）12，70，33，65，24，56，48，92，86，3312703365245648928633不是堆数据结构专升本补习调整后：12，24，33，65，33，56，48，92，86，701224336533564892867
27、0数据结构专升本补习第十章习题第十章习题2。以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序排列，试编写此算法。数据结构专升本补习为了处理方便，假设单链表具有头结点，p是搜索指针，q记录正在处理的结点。PROCchap10-2(la:linkisttp);IFla.nextNILTHEN【q:=la.next.next;la.next.next:=NIL;WHILEqNILDO【pre:=la;p:=la.next;x:=q.data;WHILEpNILCANDxp.dataDO【pre:=p;p:=p.next】;t:=q.next;pre.next:=q;q.next:=p;q:=t】ENDP;数据结构专升本补习第四部分考题解析数据结构专升本补习
