《数据结构复习习题》由会员分享，可在线阅读，更多相关《数据结构复习习题（19页珍藏版）》请在金锄头文库上搜索。
1、复习课复习课期末考试题型及分数分布期末考试题型及分数分布程序填空题程序填空题重点习题讲解重点习题讲解考试复习提纲考试复习提纲考试注意事项考试注意事项数据结构复习习题填空题（填空题（2020分，分， 每空每空2 2分）分）选择题（选择题（1010题题 ，每题，每题2 2分分 ，共，共2020分）分）程序填空题（程序填空题（2 2题，每空题，每空2.52.5分，共分，共2020分）分）论述分析题（论述分析题（3 3题，共题，共4040分）分）一、期末考试题型及分数分布：一、期末考试题型及分数分布：考试时间：第十周考试时间：第十周 星期三星期三 14:30-14:30-16:3016:30数据结构复
2、习习题二、程序填空题二、程序填空题算法算法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 算法算法9.4 9.4 数据结构复习习题（一）、求下图的邻接矩阵和邻接表（一）、求下图的邻接矩阵和邻接表（P155P155）1 1、邻接矩阵、邻接矩阵2 2、邻接表、邻接表三、重点习题讲解数据结构复习习题（二）、已知一棵二叉树如图所示，试求：（二）、已知一棵二叉树如图所示，试求：（1 1）该二叉树前序、中序和后序遍该二叉树前序、中序和后序遍历的结果；历的结果； 前序：前序：abdgecfha
3、bdgecfh；中序：；中序：dgbcafhcdgbcafhc；后序：；后序：gdebhfcagdebhfca（2 2）该二叉树是否是满二叉树？是该二叉树是否是满二叉树？是否是完全二叉树？否是完全二叉树？ 该二叉树不是满二叉树，也不该二叉树不是满二叉树，也不是完全二叉树。是完全二叉树。（3 3）将它转换成对应的树或森林将它转换成对应的树或森林（4 4）这棵二叉树的深度为多少？这棵二叉树的深度为多少？ 该二叉树的深度为该二叉树的深度为4 4图数据结构复习习题（三（三) )、已知一棵二叉树的中序遍历的结果为、已知一棵二叉树的中序遍历的结果为ABCEFGHD ABCEFGHD ，后序遍历的结果为，后
4、序遍历的结果为ABFHGEDCABFHGEDC，试画，试画出此二叉树。出此二叉树。数据结构复习习题( (四四) )、 对如图所示的连通图，分别用对如图所示的连通图，分别用Prim Prim 和和KruskalKruskal算法构造其最小生成树。算法构造其最小生成树。数据结构复习习题（1 1）primprim算法算法数据结构复习习题（2 2）采用）采用）采用）采用Kruskal Kruskal 算法求解最小生成树时首先要对边进行由小到大算法求解最小生成树时首先要对边进行由小到大算法求解最小生成树时首先要对边进行由小到大算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：
5、（进行排序，本题对边进行排序的结果是：（进行排序，本题对边进行排序的结果是：（进行排序，本题对边进行排序的结果是：（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 6、（、（、（、（A,BA,B）7 7 。数据结构复习习题（五）、对于如图所示的有向网，用（五）、对于如图所示的有向网，用Dijk
6、stra Dijkstra 方方法求从顶点法求从顶点A A 到图中其他顶点的最短路径，并写出到图中其他顶点的最短路径，并写出执行算法过程中距离向量执行算法过程中距离向量d d 与路径向量与路径向量p p 的状态变的状态变化情况。化情况。 （P176P176）ABDCFE24152881810134数据结构复习习题013450254321上图的最短路径和长度为上图的最短路径和长度为上图的最短路径和长度为上图的最短路径和长度为：数据结构复习习题（六）、假设通讯电文中只用到（六）、假设通讯电文中只用到A A，B B，C C，D D，E E，F F 六个字母，它们在电文中出现的相对频率分别为：六个字母
7、，它们在电文中出现的相对频率分别为：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第一种情况第一种情况第一种情况第一种情况数据结构复习习题第二种情况：第二种情况：第二种情况：第二种情况：Huffman Huffman 编码编码A A：001001B B：00000000C C：1111D D：1010E E：00010001F F：0101数
8、据结构复习习题（七）、设散列表长度为（七）、设散列表长度为1111，散列函数，散列函数H(x)=x % 11H(x)=x % 11，给定的关键字序列为：，给定的关键字序列为：1 1，1313，1212，3434，3838，3333，2727，2222。试画出用。试画出用线性探测法解决冲突时所构造的散列表，线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这并求出在等概率的情况下，这 种方法查找种方法查找成功时的平均查找长度。成功时的平均查找长度。查找成功时的平均查找长度计算方法：查找成功时的平均查找长度计算方法：查找成功时的平均查找长度计算方法：查找成功时的平均查找长度计算方法： 查
9、找成功时比较的总次数查找成功时比较的总次数查找成功时比较的总次数查找成功时比较的总次数/ / / /关键字的个关键字的个关键字的个关键字的个数数数数数据结构复习习题线性探测法构造的散列表如下：线性探测法构造的散列表如下：查找成功时的平均查找长度为:(1+1+3+4+1+1+2+8)/8=21/8数据结构复习习题四、考试复习提纲四、考试复习提纲第一章第一章 概论概论 数据结构的基本概念与术语（逻辑结构、存数据结构的基本概念与术语（逻辑结构、存储结构、运算集合）算法的基本特征、算法的储结构、运算集合）算法的基本特征、算法的空间复杂度和时间复杂度空间复杂度和时间复杂度第二章线性表及其顺序存储第二章线
10、性表及其顺序存储 栈和队列的基本特征及应用栈和队列的基本特征及应用第三章第三章 线性表及其链式存储线性表及其链式存储 链式存储链式存储 单链表单链表 双链表双链表 循环链表基本循环链表基本操作操作数据结构复习习题第六章第六章第六章第六章 树型结构树型结构树型结构树型结构树的基本概念树的基本概念树的基本概念树的基本概念 树的遍历（前序树的遍历（前序树的遍历（前序树的遍历（前序 后序后序后序后序 层次）层次）层次）层次） 了解树了解树了解树了解树的的的的 存储结构（双亲表示法存储结构（双亲表示法存储结构（双亲表示法存储结构（双亲表示法 孩子表示法孩子表示法孩子表示法孩子表示法 孩子兄弟表孩子兄弟表
11、孩子兄弟表孩子兄弟表示法）示法）示法）示法）第七章二叉树第七章二叉树第七章二叉树第七章二叉树 二叉树的基本概念二叉树的基本概念二叉树的基本概念二叉树的基本概念 二叉树的遍历（前序二叉树的遍历（前序二叉树的遍历（前序二叉树的遍历（前序 中序中序中序中序 后序）后序）后序）后序） 树、森林和二叉树的转换树、森林和二叉树的转换树、森林和二叉树的转换树、森林和二叉树的转换第八章图第八章图第八章图第八章图 图的基本运算图的基本运算图的基本运算图的基本运算 图的邻接矩阵和邻接表图的邻接矩阵和邻接表图的邻接矩阵和邻接表图的邻接矩阵和邻接表 最小生成树算法（普利姆和克鲁斯卡尔）最小生成树算法（普利姆和克鲁斯卡
12、尔）最小生成树算法（普利姆和克鲁斯卡尔）最小生成树算法（普利姆和克鲁斯卡尔） 最短路径最短路径最短路径最短路径-单源最短（单源最短（单源最短（单源最短（DijkstraDijkstraDijkstraDijkstra）数据结构复习习题第九章第九章 检索检索 顺序检索顺序检索 二分检索二分检索 分块检索分块检索 huffmanhuffman树树 散列表检散列表检第十章内排序第十章内排序 排序的基本概念排序的基本概念 插入排序（直接插入排序插入排序（直接插入排序 二分法插入排序）二分法插入排序） 选择选择 排序排序 交换排序（冒泡排序交换排序（冒泡排序 快速排序）快速排序） 归并排序的基本思想归并排序的基本思想数据结构复习习题五、考试注意事项五、考试注意事项复习资料邮箱复习资料邮箱用户名：用户名：密码：密码：sjjg2012sjjg2012数据结构复习习题
