数据结构作业12-13-14.ppt

1、第12-13作业 B B+树以及图,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个子女，叶节点可以

2、存储多达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; 回文是指第一

3、 个字符与最后一个相同，第二个字符与倒数第二个相同，依此类推。 如：“abba”是回文，“abab”不是回文。空串和长度为1的串都是回文。 可以直接使用如下定义中的基本操作。 栈的ADT定义如下： template class Stack public: void clear(); bool push(const T item); bool pop(T,中期代码： bool checkString(string s) Stack T; string s1=; for(int i=0;is.length();i+) T.push(si); while(!T.isEmpty() s1=T.pop(

4、); if(s=s1) return true; else return false; ,提示：若栈的入栈顺序与出栈顺序相同，则字符串s为回文,第十三次作业-图,1采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（A）。 A）先序遍历B）中序遍历C）后序遍历D）层次遍历 2一个n个顶点的连通无向图，其边的个数至少为（A）。 A）n-1B）nC）n+1D）nlogn,11.4 Show the DFS tree for the graph of Figure 11.26,starting at Vertex 1. 对于图11.26所示的图，给出其从顶点1开始的DFS树深度优先搜索

5、树。 答案： 11.6 Show the BFS tree for the graph of Figure 11.26,starting at Vertex 1. 对于图11.26所示的图，给出其从顶点1开始的BFS树广度优先搜索树。 答案：,（c）邻接矩阵需要：36*2=72 bytes；邻接表需要：（6+18）*4+18*（2+2）=168 bytes。因此选择邻接矩阵更好。 （d）邻接矩阵需要：36*2=72 bytes；邻接表需要：（6+18）*4+18*（2+1）=150 bytes。因此选择邻接矩阵更好。,（a）,（b）,11.3（a）画出图11.26所示图的相邻矩阵adjacen

6、cy matrix 表示; （b）画出这个图的邻接表adjacency list表示; （c）如果每个指针需要4个字节，每个顶点的标号占用两个字节，每条边的权需要两个字节，则该图采用哪种表示方法需要的空间更多？ （d）如果每个指针需要4个字节,每个顶点的标号需要一个字节，每条边的权需要两个字节，那么采用哪种表示方法需要的空间更多？,算法设计题： 计算一棵树的树叶结点的个数。树的存储采用Leftmost Child/Right Sibling存储方式。 若你用C+实现，结点的类定义如下： class TreeNode public: char val; /结点的值 TreeNode* LeftC

7、hild; /左孩子 TreeNode* RightSibling; /右兄弟 若你用C实现，结点的结构定义如下： struct TreeNode char val; /结点的值 struct TreeNode* LeftChild; /左孩子 struct TreeNode* RightSibling; /右兄弟 ,中期代码： int leavesCount(TreeNode *root) int count=0; if(root=null)return 0; if(root-leftchild=null)return 1; for(TreeNode *temp=root-LeftChild

8、;temp;temp=temp-RightSibling) count+=leavesCount(temp); return count ,11.8对于11.26中的图，给出从顶点4开始出发，使用Dijkstra最短路径算法产生的最短路径表，请向图11.19所示一样，每处理一个顶点时给出相应D值。,第十四次作业-图,Dijkstra算法的流程为： 初始状态下，源顶点为4，除了顶点4，其余各个顶点的最短路径长度初值均为无穷大； 处理完顶点4后，其相邻顶点的最短路径长度被更新为到4的直接距离； 再选定当前离4最近的顶点作为下一个顶点，再更新余下顶点的值； 依次类推；结果如下所示：,11.17对于1

9、1.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）可以判断出一个有向图中是否有

10、环（回路）？ 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)无线图的邻接矩阵一定是对称的，那么矩阵的主对角线以上部分中有