数据结构作业-1-1.ppt

第12 13作业BB 树以及图 10 8给出把值55与46插入下图的2 3树中的结果 第十二次作业 图 10 9给定一组记录 其关键码值是字母 记录按照下面的顺序插入 C S D T A M P B W N G U R K E H O L J给出插入这些记录后的2 3树 10 11给出把值55插入图10 17中B树的结果 10 12给出把值1 2 3 4 5 6 按照这个顺序 插入图10 16中B 树的结果 10 13给出把值18 19和20 按照这个顺序 插入图10 2 b 的B 树中删除的结果 10 15假定有一个B 树 它的内部节点 可以存储多达100个子女 叶节点可以存储多达15条记录 对于1 2 3 4 和5层B 树 能够存储的最大记录数和最小记录数是多少 那么 内部节点的孩子节点个数为 50 100 叶子节点的记录数为 1 15 当层数为1时 根节点充当叶子节点 最少记录数为0 最多记录数为15 当再来一个记录时 根节点要分裂为两层 变为内部节点 此时记录数16是层数为2时最少的情况 最多的即为根节点和叶子节点均存满 以此类推 分析 B 树中所有叶子节点在同一层 根节点最少有两棵子树 其余分支节点的子树个数为 m 2 到m 也就是题目中的阶数m为100 期中考试 算法设计题 利用栈 判断一个字符串s是否是回文 若是返回1 否则返回0 回文是指第一个字符与最后一个相同 第二个字符与倒数第二个相同 依此类推 如 abba 是回文 abab 不是回文 空串和长度为1的串都是回文 可以直接使用如下定义中的基本操作 栈的ADT定义如下 templateclassStack public voidclear boolpush constTitem boolpop T 中期代码 boolcheckString strings StackT strings1 for inti 0 i s length i T push s i while T isEmpty s1 T pop if s s1 returntrue elsereturnfalse 提示 若栈的入栈顺序与出栈顺序相同 则字符串s为回文 第十三次作业 图 1 采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的 A A 先序遍历B 中序遍历C 后序遍历D 层次遍历2 一个n个顶点的连通无向图 其边的个数至少为 A A n 1B nC n 1D nlogn 11 4ShowtheDFStreeforthegraphofFigure11 26 startingatVertex1 对于图11 26所示的图 给出其从顶点1开始的DFS树深度优先搜索树 答案 11 6ShowtheBFStreeforthegraphofFigure11 26 startingatVertex1 对于图11 26所示的图 给出其从顶点1开始的BFS树广度优先搜索树 答案 c 邻接矩阵需要 36 2 72bytes 邻接表需要 6 18 4 18 2 2 168bytes 因此选择邻接矩阵更好 d 邻接矩阵需要 36 2 72bytes 邻接表需要 6 18 4 18 2 1 150bytes 因此选择邻接矩阵更好 a b 11 3 a 画出图11 26所示图的相邻矩阵adjacencymatrix表示 b 画出这个图的邻接表adjacencylist表示 c 如果每个指针需要4个字节 每个顶点的标号占用两个字节 每条边的权需要两个字节 则该图采用哪种表示方法需要的空间更多 d 如果每个指针需要4个字节 每个顶点的标号需要一个字节 每条边的权需要两个字节 那么采用哪种表示方法需要的空间更多 算法设计题 计算一棵树的树叶结点的个数 树的存储采用LeftmostChild RightSibling存储方式 若你用C 实现 结点的类定义如下 classTreeNode public charval 结点的值TreeNode LeftChild 左孩子TreeNode RightSibling 右兄弟 若你用C实现 结点的结构定义如下 structTreeNode charval 结点的值structTreeNode LeftChild 左孩子structTreeNode RightSibling 右兄弟 中期代码 intleavesCount TreeNode root intcount 0 if root null return0 if root leftchild null return1 for TreeNode temp root LeftChild temp temp temp RightSibling count leavesCount temp returncount 11 8对于11 26中的图 给出从顶点4开始出发 使用Dijkstra最短路径算法产生的最短路径表 请向图11 19所示一样 每处理一个顶点时给出相应D值 第十四次作业 图 Dijkstra算法的流程为 初始状态下 源顶点为4 除了顶点4 其余各个顶点的最短路径长度初值均为无穷大 处理完顶点4后 其相邻顶点的最短路径长度被更新为到4的直接距离 再选定当前离4最近的顶点作为下一个顶点 再更新余下顶点的值 依次类推 结果如下所示 11 17对于11 26中的图 给出从顶点3开始使用Prim的MST 最小支撑树 包含所有顶点以及一部分边的树 保证连通且所有权重最小 算法时各个边的访问顺序 并且给出最终的MST Prim的MST的流程为 从图中任意一个顶点N开始 题目中是指定顶点3即N为3 初始化MST为N 选出与N相关联的边中权值最小的一条边 其起始顶点则为N M 则将 N M 加入MST 再选择与顶点N M相关联的边中权值最小的一条边 连接的新顶点为S 将S以及新边加入MST中 依次类推 结果如下所示 最终的MST为 以下为图的补充作业 一 单项选择题1 下面 B 可以判断出一个有向图中是否有环 回路 A 求关键路径B 拓扑排序C 求最短路径D 前面都不正确二 综合题1 设有带权无向图G如下图所示 讲解 试给出 1 从V1开始的深度优先遍历 2 从V1开始的广度优先遍历 3 从V1开始执行的普里姆 Prim 算法过程中所选边的序列 答案 1 深度优先类似二叉树的根左右遍历 遍历结果为V1 V2 V4 V8 V5 V3 V6 V7 2 广度优先类似二叉树的层次遍历 遍历结果为V1 V2 V3 V4 V5 V6 V7 V8 3 所选边的序列为 V1 V3 V3 V6 V3 V7 V1 V2 V2 V5 V2 V4 V5 V8 2 给出如下图所示的所有拓扑有序序列 答案 A C B D E不唯一3 对于有n个顶点的无向图 采用邻接矩阵表示 如何判断以下问题 图中有多少条边 任意两个顶点i和j之间是否有边相连 任意一个顶点的度是多少 答案 1 无线图的邻接矩阵一定是对称的 那么矩阵的主对角线以上部分中有多少元素就代表图中的边树 设m为矩阵中非零元素的个数无向图的边数 m 2 2 对于无