数据结构复习习题.pptxVIP

复习课期末考试题型及分数分布程序填空题重点习题讲解考试复习提纲考试注意事项

填空题（20分，每空2分）选择题（10题，每题2分，共20分）程序填空题（2题，每空2.5分，共20分）论述分析题（3题，共40分）期末考试题型及分数分布：考试时间：第十周星期三14:30-16:30

二、程序填空题算法3.4算法3.5算法3.9算法3.10算法3.15算法3.20算法9.2算法9.4

三、重点习题讲解（一）、求下图的邻接矩阵和邻接表（P155）1、邻接矩阵2、邻接表

（二）、已知一棵二叉树如图所示，试求：（1）该二叉树前序、中序和后序遍历的结果；前序：abdgecfh；中序：dgbcafhc；后序：gdebhfca（2）该二叉树是否是满二叉树？是否是完全二叉树？该二叉树不是满二叉树，也不是完全二叉树。（3）将它转换成对应的树或森林（4）这棵二叉树的深度为多少？该二叉树的深度为4图

已知一棵二叉树的中序遍历的结果为ABCEFGHD，后序遍历的结果为ABFHGEDC，试画出此二叉树。

对如图所示的连通图，分别用Prim和Kruskal算法构造其最小生成树。

（1）prim算法

采用Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）5、（E,G）5、（A,D）6、（D,G）6、（A,B）7。

（五）、对于如图所示的有向网，用Dijkstra方法求从顶点A到图中其他顶点的最短路径，并写出执行算法过程中距离向量d与路径向量p的状态变化情况。（P176）ABDCFE24152881810134

013450254321上图的最短路径和长度为：

（六）、假设通讯电文中只用到A，B，C，D，E，F六个字母，它们在电文中出现的相对频率分别为：8，3，16，10，5，20，试为它们设计Huffman编码。（P221）Huffman编码A：001B：0000C：10D：01E：0001F：11第一种情况

第二种情况：01020304050607Huffman编码00100001101100001

设散列表长度为11，散列函数H(x)=x%11，给定的关键字序列为：1，13，12，34，38，33，27，22。试画出用线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这种方法查找成功时的平均查找长度。查找成功时的平均查找长度计算方法：查找成功时比较的总次数/关键字的个数

线性探测法构造的散列表如下：查找成功时的平均查找长度为:(1+1+3+4+1+1+2+8)/8=21/8

第二章线性表及其顺序存储栈和队列的基本特征及应用第三章线性表及其链式存储链式存储单链表双链表循环链表基本操作数据结构的基本概念与术语（逻辑结构、存储结构、运算集合）算法的基本特征、算法的空间复杂度和时间复杂度第一章概论四、考试复习提纲

第六章树型结构树的基本概念树的遍历（前序后序层次）了解树的存储结构（双亲表示法孩子表示法孩子兄弟表示法）第七章二叉树二叉树的基本概念二叉树的遍历（前序中序后序）树、森林和二叉树的转换第八章图图的基本运算图的邻接矩阵和邻接表最小生成树算法（普利姆和克鲁斯卡尔）最短路径--单源最短（Dijkstra）

第九章检索顺序检索二分检索分块检索huffman树散列表检第十章内排序排序的基本概念插入排序（直接插入排序二分法插入排序）选择排序交换排序（冒泡排序快速排序）归并排序的基本思想

01用户名：02密码：sjjg2012复习资料邮箱五、考试注意事项