数据结构复习习题.ppt

复习课 期末考试题型及分数分布程序填空题重点习题讲解考试复习提纲考试注意事项 填空题 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算法 2 采用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 上图的最短路径和长度为 六 假设通讯电文中只用到A B C D E F六个字母 它们在电文中出现的相对频率分别为 8 3 16 10 5 20 试为它们设计Huffman编码 P221 Huffman编码A 001B 0000C 10D 01E 0001F 11 第一种情况 第二种情况 Huffman编码A 001B 0000C 11D 10E 0001F 01 七 设散列表长度为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树散列表检第十章内排序排序的基本概念插入排序 直接插入排序二分法插入排序 选择排序交换排序 冒泡排序快速排序 归并排序的基本思想 五 考试注意事项 复习资料邮箱 用户名 guet sjjg2012 密码 sjjg2012