数据结构总复习和作业ppt课件.ppt

《数据结构总复习和作业ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构总复习和作业ppt课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值考试时间：第10周周日(5月月10日日)九、十节考试教室安排：考试方式：闭卷笔试考试成绩卷面(80)平时作业(20)考试题型(参考）：1、判断对错、选择、填空2、综合应用3、算法设计数据数据结构答疑安排：构答疑安排：大黑楼大黑楼A802或或A718周三周三(5月月6日日)下午下午1:305:00资金是运动的价值，资金的价值是随时间变化而变化的，是时间

2、的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第一章 绪言2基本概念和术语（掌握）F数据结构，数据，数据元素，数据项F逻辑结构与存储结构2算法分析（掌握）F算法定义F算法特性：F算法评价：时间复杂度与空间复杂度（了解）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第二章 线性表2逻辑结构（掌握）2存储结构（掌握）F顺序存储结构F链式存储结构单链表双向链表循环链表双向循环链表静态链表（了解）2基本操作（掌握）F插入F删除F查找2应用-一元多项式相加（掌握）时间复杂度资金是运动的价值，资金的价值

3、是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第三章 栈和队列-操作受限的线性表2栈F特点（掌握）：FILO(LIFO)F存储结构（掌握）：顺序栈与链栈F基本操作（掌握）：入栈与出栈F应用（掌握）：回文、括号匹配、表达式求值3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2队列F特点（掌握）：FIFO（LILO）F存储结构（掌握）：顺序队列链队列F循环队列（掌握）F基本操作（掌握）入队出队F应用（了解）：迷宫，优先队列等队空、队满条件资金是运动的价值，资金的价值是随

4、时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第四章 数组2线性结构2存储结构F顺序存储结构（掌握）：次序约定 （算法实现不要求）F压缩存储（掌握）对称矩阵对角矩阵三角矩阵稀疏矩阵2算法：求转置矩阵（了解）三元组表行逻辑链接的顺序表带行指针向量的单链表十字链表资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第五章 树2逻辑结构：按分支关系定义的层次结构2定义（掌握）：F深度、度、叶子等F满二叉树、完全二叉树2二叉树性质（掌握）：52存储结构F树（掌握）双亲表示法孩子表示

5、法（孩子链表与多重链表）孩子兄弟表示法（二叉链表）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值F二叉树（掌握）顺序存储结构二叉链表三叉链表F树、森林与二叉树转换（掌握）F遍历按层次、先序、中序、后序遍历递归（掌握）与非递归算法（了解）遍历算法应用（掌握）由先序序列建立二叉链表统计叶子结点求二叉树深度已知先序和中序序列，构造二叉树资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2应用FHuffman树（掌握）定义，WPL构造方法有n个叶子结点

6、的Huffman树共有2n-1个结点应用Huffman编码与译码最佳判定树资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第六章 图2定义（掌握）：图、有向图、度、连通、完备图等2存储结构F邻接矩阵（掌握）F邻接表与逆邻接表（掌握）F十字链表（了解）F邻接多重表（了解）2遍历：深度优先与广度优先（掌握遍历策略及算法）深度优先生成树、广度度优先生成树构成特点(与顶点度关系)资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2应用（掌握求解过程，不

7、要求写算法掌握求解过程，不要求写算法）F最小生成树（Prim与Kruscal）F拓扑排序F最短路径（Dijkstra）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第七章 查找2静态查找表F顺序查找（掌握）F折半查找（掌握）F分块查找（了解）2动态查找表（了解）F二叉排序树定义构造方法生成、插入、删除与查找中序遍历二叉排序树可得到结点有序序列比较、ASL资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2哈希查找（掌握）F定义、基本思想FHa

8、sh函数构造方法F处理冲突方法F哈希表构造F哈希查找过程与ASL资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值&第八章 排序2掌握排序的 基本概念和性能分析方法，排序策略 2插入排序F直接插入排序（掌握）F折半插入排序（掌握）F希尔排序（了解）2交换排序F冒泡排序（掌握）F快速排序（了解）2选择排序F简单选择排序（掌握）F堆排序（掌握，不考算法）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2归并排序：2-路归并排序（了解）2基数排序：链式

9、基数排序（了解）F排序方法思想F每趟排序结果F排序方法性能分析评价本章了解的排序方法不要求掌握算法资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值作业作业1.线性表线性表从键盘读入从键盘读入n个整数（升序），请编写算法实现：个整数（升序），请编写算法实现：CreateList()：建立带表头结点的单链表；：建立带表头结点的单链表；PrintList()：显示单链表：显示单链表(形如形如:H-10-20-30-40);InsertList()：在有序单链表中插入元素：在有序单链表中插入元素x；ReverseList()：

10、单链表就地逆置；：单链表就地逆置；DelList()：在有序单链表中删除所有值大于：在有序单链表中删除所有值大于mink且小且小于于maxk的元素。的元素。选作：使用文本菜单完成功能选择及执行。选作：使用文本菜单完成功能选择及执行。思考题：思考题：你能将上述算法改为双向循环链表吗？你能将上述算法改为双向循环链表吗？作业作业1 1资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 3 1 2 4 5 qptempq 单链表就地逆置资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的

11、这部分资金就是原有资金的时间价值L 1 3 2 4 5 ptempqq 单链表就地逆置资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 2 1 3 4 5 tempqptempq 单链表就地逆置资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 5 2 1 4 3 qptempq 单链表就地逆置资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 4 5 2 3 1 v

12、oidListReverse_L(LinkList&L)LinkListp,q,u;p=L-next;if(p=NULL|p-next=NULL)/空空链表或只有一个表或只有一个结点点return;q=L-next-next;/q指向第二个指向第二个结点点p-next=NULL;while(q)u=q-next;q-next=L-next;L-next=q;q=u;单链表就地逆置资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 3 1 2 4 5 qppretempq 单链表就地排序资金是运动的价值，资金的价值是随时

13、间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 1 3 2 4 5 ppretempqq 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 1 2 3 4 5 tempqqppre 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 1 2 3 4 5 tempqqppre 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值

14、，其增值的这部分资金就是原有资金的时间价值L 1 2 3 4 5 tempqqppre 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 1 2 3 4 5 qppre 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值L 1 2 3 5 4 单链表就地排序资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值LinkListSortList(Li

15、nkListL)/链表就地排序链表就地排序LNode*p,*pre,*q,*temp;p=L-next;if(p=NULL)returnL;/空表空表,不用排序，返回不用排序，返回q=p-next;p-next=NULL;while(q!=NULL)pre=L;p=L-next;while(p!=NULL)/查找插入位置查找插入位置if(q-datap-data)pre=p;p=p-next;elsebreak;temp=q-next;/插入插入pre-next=q;q-next=p;q=temp;returnL;资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增

16、值，其增值的这部分资金就是原有资金的时间价值作业作业2 2若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc 元素元素a、b、c、d、e、f依次通依次通过栈，若出若出栈顺序是序是c、b、d、f、e、a，则栈S的容量至少是（的容量至少是（）3表达式后表达式后缀形式，前形式，前缀形式形式ab*cde/-f*+a*b+(c-d/e)*f循循环

17、队列列队满和和队空的判空的判别条件。条件。Q.front=Q.rearQ.front=(Q.rear+1)%M资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值设A为n阶对称矩阵，采用压缩存储存放于一维数组Fn(n+1)/2中（从F0开始存放），请分别给出存放上三角阵时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩阵元素aij的地址计算公式。存放下三角阵时，任一矩阵元素aij（1in,1ji）的地址计算公式为：存放上三角阵时，任一矩阵元素aij（1in,ijn）的地址计算公式为：a11 0 0.0 a21 a22

18、 0.0 an1 an2 an3.ann .0作业作业2 2 a11 a12 a13.a1n 0 a22 a23.a2n 0 0 0.ann an-1n-1an-1n资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值5 6 6 1 1 4 2 1 5 2 3 3 2 6 8 4 4 7 5 1 2 三元组表i j v0 1 2 3 4 5 6写出矩阵三元组表，十字链表作业作业2 2114512447233268215十字链表资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分

19、资金就是原有资金的时间价值请分别画出具有请分别画出具有3个结点的树和个结点的树和3个结点的二叉树的所有不同形态。个结点的二叉树的所有不同形态。作业作业3 3 已知二叉树的先序遍历序列是已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列，中序遍历序列是是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和，请构造二叉树，并写出其层次遍历序列和后序遍历序列。后序遍历序列。EACBDIJHFGK层次：E A F B H D G I C K J后序-C D B A G J K I H F E资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的

20、这部分资金就是原有资金的时间价值森林转换成一棵二叉树森林转换成一棵二叉树作业作业3 3BACDFGEHIJKL二叉树还原成森林二叉树还原成森林ACHBFDMEGNJIKL资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值设二叉树的设二叉树的后序遍历序列为：后序遍历序列为：DCFEBHJKIGA，中序，中序序列为：序列为：CDBEFAHGJIK，请构造这棵二叉树。，请构造这棵二叉树。作业作业3 3二叉树的中序遍历序列为：二叉树的中序遍历序列为：DBHEIAFJKCG，层次遍历，层次遍历序列为：序列为：ABCDEFGHIJK

21、，请画出该二叉树，请画出该二叉树资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值作业作业3 3假设用于通信的电文由假设用于通信的电文由7个字母组成个字母组成A,B,C,D,E,F,G，字母在，字母在电文中出现的频率分别为电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这。试为这7个字母设计哈夫曼编码，并计算其带权个字母设计哈夫曼编码，并计算其带权路径长度路径长度WPL 10.390.610.180.210.090.090.290.320.120.170.030.06AEG

22、BDFWPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101B:001C:100D:0001E:11F:0000G:01资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值算法设计题算法设计题二叉树采用二叉链表存储，试设计算法实现：二叉树采用二叉链表存储，试设计算法实现：CreateBT(BiTree&T)：从键盘输入二叉树的先序遍历序列字符串（以：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；代表空结点），建立其二叉链表；如输

23、入：如输入：AB#D#CE#F#则建立如下图所示二叉树的二叉链表则建立如下图所示二叉树的二叉链表ExchangeBT(BiTreeT):设计递归算法实现二叉树中所有结点的左右孩设计递归算法实现二叉树中所有结点的左右孩子交换；子交换；CountLeaf(BiTreeT,TElemTypex,int&count):统计以值为统计以值为x的结点为的结点为根的子树中叶子结点的数目；根的子树中叶子结点的数目；DispBiTree(BiTreeT,intlevel):按树状打印二叉树按树状打印二叉树。作业作业3 3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的

24、这部分资金就是原有资金的时间价值/输入先序序列，入先序序列，创建二叉建二叉树的二叉的二叉链表表voidCreateBT(BiTree&T)charch;scanf(%c,&ch);if(ch=#)T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);T-data=ch;CreateBT(T-lchild);CreateBT(T-rchild);BCFAED/交交换二叉二叉树中中结点的左右孩子点的左右孩子voidExchangeBT(BiTreeT)BiTreetemp;if(T)temp=T-lchild;T-lchild=T-rchild;T-rchil

25、d=temp;ExchangeBT(T-lchild);ExchangeBT(T-rchild);资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值BiTreeSearchTree(BiTreeT,charX)BiTreebt;if(T)if(T-data=X)returnT;bt=SearchTree(T-lchild,X);if(bt=NULL)bt=SearchTree(T-rchild,X);returnbt;returnNULL;voidLeafCount(BiTreeT,int&count)if(T)if(T

26、-lchild=NULL)&(T-rchild=NULL)count+;LeafCount2(T-lchild,count);LeafCount2(T-rchild,count);BCFAED资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值/按按树状打印状打印输出二叉出二叉树的元素的元素,level表示表示结点的点的层次次voidDispBiTree(BiTreeT,intlevel)inti;if(T)DispBiTree(T-rchild,level+1);for(i=0;idata);DispBiTree(T-l

27、child,level+1);BCFAED打印得到：#C#F#EA#D#B资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值已知带权有向图如下,要求：画出图邻接矩阵；给出图的一个拓扑有序序列；求从顶点a出发到其余个顶点的最短路径abcdehfg2169322430587210 2 6 9 0 30 1 0 5 0 2 8 0 7 3 0 24 0 21 0拓扑有序序列：a,b,d,f,e,c,g,h作业作业4 4资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有

28、资金的时间价值无向图邻接表存储结构如图所示：画出该无向图；写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。作业作业4 413247586DFSDFS：1 1，3 3，4 4，7 7，8 8，6 6，5 5，2 2 BFSBFS：1 1，3 3，2 2，4 4，7 7，6 6，5 5，8 8 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值对下下标为19的有序表的有序表进行二分法行二分法查找，找，(1)画出折半画出折半查找的判定找的判定树；(2)计算其算其ASL;(3)比比较4次

29、次查找成功的找成功的结点共有点共有个。个。527136849ASL=(1+2*2+3*4+4*2)/9=25/92作业作业5 5资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值设有关键字序列设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58散列表长为散列表长为12，散列函数为，散列函数为h(key)=key%11，用线性探测再散列处，用线性探测再散列处理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败的平均查找长度的平均查

30、找长度ASL=(1*6+2+3*2+5+6+9)/12=34/12作业作业5 536053610107309412662533472272401131261131187155589资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值设有关键字序列设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58散列表长为散列表长为12，散列函数为，散列函数为h(key)=key%11，用二次探测再散列处，用二次探测再散列处理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败理冲突，请画出散列表，在等概

31、率情况下，求查找成功和查找失败的平均查找长度的平均查找长度ASL=(1*6+2+3*3+4+5)/12=26/12作业作业5 536053610107309412662533472272401131251131187154583资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值ASL=(1*7+2*3+3*2)/12=19/12663301234567891011122247945812257240875作业作业5 5设有关键字序列设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58散列表长

32、为散列表长为12，散列函数为，散列函数为h(key)=key%11，用线性探测再散列处，用线性探测再散列处理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败理冲突，请画出散列表，在等概率情况下，求查找成功和查找失败的平均查找长度的平均查找长度3605361010730资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值已知待排序序列为50，86，72，41，45，93，57，46，请写出按下列排序方法进行升序排序时的第一趟排序结果：第一趟直接插入排序：5050，8686，7272，4141，4545，9393，57

33、57，4646第一趟冒泡排序：5050，7272，4141，4545，8686，5757，4646，9393第一趟简单选择排序：4141，8686，7272，5050，4545，9393，5757，4646堆排序初建堆序列：9393，8686，7272，4646，4545，5050，5757，4141(大顶堆）作业作业5 5第一趟直接插入排序：8686，5050，7272，4141，4545，9393，5757，4646第一趟冒泡排序：8686，7272，5050，4545，9393，5757，4646，4141第一趟简单选择排序：9393，8686，7272，4141，4545，5050，5757，4646堆排序初建堆序列：41，45，57，46，50，93，72，86(小顶堆）降序降序