数据结构复习习题课.pptx

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

1、填空题（填空题（2020分，分，每空每空2 2分）分）选择题（选择题（1010题题 ，每题，每题2 2分分 ，共，共2020分）分）程序填空题（程序填空题（2 2题，每空题，每空2.52.5分，共分，共2020分）分）论述分析题（论述分析题（3 3题，共题，共4040分）分）一、期末考试题型及分数分布：考试时间：第十周考试时间：第十周 星期三星期三 14:30-16:3014:30-16:30第1页/共19页二、程序填空题算法算法3.4 3.4 算法算法3.5 3.5 算法算法3.9 3.9 算法算法3.103.10算法算法3.15 3.15 算法算法3.203.20算法算法9.2 9.2 算

2、法算法9.4 9.4 第2页/共19页（一）、求下图的邻接矩阵和邻接表（一）、求下图的邻接矩阵和邻接表（P155P155）1 1、邻接矩阵、邻接矩阵2 2、邻接表、邻接表三、重点习题讲解第3页/共19页（二）、已知一棵二叉树如图所示，试求：（二）、已知一棵二叉树如图所示，试求：（1 1）该二叉树前序、中序和后序遍该二叉树前序、中序和后序遍历的结果；历的结果；前序：前序：abdgecfhabdgecfh；中序：；中序：dgbcafhcdgbcafhc；后序：；后序：gdebhfcagdebhfca（2 2）该二叉树是否是满二叉树？是该二叉树是否是满二叉树？是否是完全二叉树？否是完全二叉树？该二叉

3、树不是满二叉树，也不该二叉树不是满二叉树，也不是完全二叉树。是完全二叉树。（3 3）将它转换成对应的树或森林将它转换成对应的树或森林（4 4）这棵二叉树的深度为多少？这棵二叉树的深度为多少？该二叉树的深度为该二叉树的深度为4 4图第4页/共19页（三（三)、已知一棵二叉树的中序遍历的结果为、已知一棵二叉树的中序遍历的结果为ABCEFGHD ABCEFGHD，后序遍历的结果为，后序遍历的结果为ABFHGEDCABFHGEDC，试画出此二叉树。试画出此二叉树。第5页/共19页(四四)、对如图所示的连通图，分别用对如图所示的连通图，分别用Prim Prim 和和KruskalKruskal算法构造其

4、最小生成树。算法构造其最小生成树。第6页/共19页（1 1）primprim算法算法第7页/共19页（2 2）采用）采用Kruskal Kruskal 算法求解最小生成树时首先要对边进行由小到大算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：（进行排序，本题对边进行排序的结果是：（D,FD,F）1 1、（、（C,FC,F）2 2、（A,FA,F）3 3、（、（A,CA,C）4 4、（、（F,GF,G）4 4、（、（D,ED,E）4 4、（、（D,BD,B）4 4、（C,DC,D）5 5、（、（E,GE,G）5 5、（、（A,DA,D）6 6、（、（D,GD,G）6

5、 6、（、（A,BA,B）7 7。第8页/共19页（五）、对于如图所示的有向网，用（五）、对于如图所示的有向网，用Dijkstra Dijkstra 方法方法求从顶点求从顶点A A 到图中其他顶点的最短路径，并写出执到图中其他顶点的最短路径，并写出执行算法过程中距离向量行算法过程中距离向量d d 与路径向量与路径向量p p 的状态变化的状态变化情况。情况。（P176P176）ABDCFE24152881810134第9页/共19页013450254321上图的最短路径和长度为上图的最短路径和长度为上图的最短路径和长度为上图的最短路径和长度为：第10页/共19页（六）、假设通讯电文中只用到（六）

6、、假设通讯电文中只用到A A，B B，C C，D D，E E，F F 六个字母，它们在电文中出现的相对频率分别六个字母，它们在电文中出现的相对频率分别为：为：8 8，3 3，1616，1010，5 5，2020，试为它们设计，试为它们设计Huffman Huffman 编码。（编码。（P221P221）Huffman Huffman 编码编码A A：001001B B：00000000C C：1010D D：0101E E：00010001F F：1111第一种情况第一种情况第一种情况第一种情况第11页/共19页第二种情况：第二种情况：第二种情况：第二种情况：Huffman Huffman 编

7、码编码A A：001001B B：00000000C C：1111D D：1010E E：00010001F F：0101第12页/共19页（七）、设散列表长度为（七）、设散列表长度为1111，散列函数，散列函数H(x)=x%11H(x)=x%11，给定的关键字序列为：，给定的关键字序列为：1 1，1313，1212，3434，3838，3333，2727，2222。试画。试画出用线性探测法解决冲突时所构造的散出用线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这列表，并求出在等概率的情况下，这 种种方法查找成功时的平均查找长度。方法查找成功时的平均查找长度。查找成功时的平均查找长

8、度计算方法：查找成功时的平均查找长度计算方法：查找成功时的平均查找长度计算方法：查找成功时的平均查找长度计算方法：查找成功时比较的总次数查找成功时比较的总次数查找成功时比较的总次数查找成功时比较的总次数/关键字的个数关键字的个数关键字的个数关键字的个数第13页/共19页线性探测法构造的散列表如下：线性探测法构造的散列表如下：查找成功时的平均查找长度为:(1+1+3+4+1+1+2+8)/8=21/8第14页/共19页四、考试复习提纲四、考试复习提纲第一章第一章 概论概论 数据结构的基本概念与术语（逻辑结构、存储数据结构的基本概念与术语（逻辑结构、存储结构、运算集合）算法的基本特征、算法的空结构

9、、运算集合）算法的基本特征、算法的空间复杂度和时间复杂度间复杂度和时间复杂度第二章线性表及其顺序存储第二章线性表及其顺序存储 栈和队列的基本特征及应用栈和队列的基本特征及应用第三章第三章 线性表及其链式存储线性表及其链式存储 链式存储链式存储 单链表单链表 双链表双链表 循环链表基本操作循环链表基本操作第15页/共19页第六章第六章第六章第六章 树型结构树型结构树型结构树型结构树的基本概念树的基本概念树的基本概念树的基本概念 树的遍历（前序树的遍历（前序树的遍历（前序树的遍历（前序 后序后序后序后序 层次）层次）层次）层次）了解树的了解树的了解树的了解树的 存储结构（双亲表示法存储结构（双亲表

10、示法存储结构（双亲表示法存储结构（双亲表示法 孩子表示法孩子表示法孩子表示法孩子表示法 孩子兄弟表示法）孩子兄弟表示法）孩子兄弟表示法）孩子兄弟表示法）第七章二叉树第七章二叉树第七章二叉树第七章二叉树 二叉树的基本概念二叉树的基本概念二叉树的基本概念二叉树的基本概念 二叉树的遍历（前序二叉树的遍历（前序二叉树的遍历（前序二叉树的遍历（前序 中序中序中序中序 后序）后序）后序）后序）树、森林和二叉树的转换树、森林和二叉树的转换树、森林和二叉树的转换树、森林和二叉树的转换第八章图第八章图第八章图第八章图 图的基本运算图的基本运算图的基本运算图的基本运算 图的邻接矩阵和邻接表图的邻接矩阵和邻接表图的

11、邻接矩阵和邻接表图的邻接矩阵和邻接表 最小生成树算法（普利姆和克鲁斯卡尔）最小生成树算法（普利姆和克鲁斯卡尔）最小生成树算法（普利姆和克鲁斯卡尔）最小生成树算法（普利姆和克鲁斯卡尔）最短路径最短路径最短路径最短路径-单源最短（单源最短（单源最短（单源最短（DijkstraDijkstraDijkstraDijkstra）第16页/共19页第九章第九章 检索检索 顺序检索顺序检索 二分检索二分检索 分块检索分块检索 huffmanhuffman树树 散散列表检列表检第十章内排序第十章内排序 排序的基本概念排序的基本概念 插入排序（直接插入排序插入排序（直接插入排序 二分法插入排序）二分法插入排序）选择选择 排序排序 交换排序（冒泡排序交换排序（冒泡排序 快速排序）快速排序）归并排序的基本思想归并排序的基本思想第17页/共19页五、考试注意事项五、考试注意事项复习资料邮箱复习资料邮箱用户名：用户名：密码：密码：sjjg2012sjjg2012第18页/共19页感谢您的观看！第19页/共19页