《数据结构作业.pptx》由会员分享，可在线阅读，更多相关《数据结构作业.pptx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、10.8 给出把值55与46插入下图的2-3树中的结果。第十二次作业-图第1页/共20页10.9给定一组记录，其关键码值是字母，记录按照下面的顺序插入：C,S,D,T,A,M,P,B,W,N,G,U,R,K,E,H,O,L,J给出插入这些记录后的2-3树。第2页/共20页10.11给出把值55插入图10.17中B树的结果。第3页/共20页10.12给出把值1,2,3,4,5,6(按照这个顺序)插入图10.16中B+树的结果。第4页/共20页10.13给出把值18,19和20(按照这个顺序)插入图10.2(b)的B+树中删除的结果。第5页/共20页10.15假定有一个B+树，它的内部节点，可以存
2、储多达100个子女，叶节点可以存储多达15条记录，对于1,2,3,4,和5层B+树，能够存储的最大记录数和最小记录数是多少？那么：内部节点的孩子节点个数为：50,100 叶子节点的记录数为1,15当层数为1时，根节点充当叶子节点，最少记录数为0，最多记录数为15；当再来一个记录时，根节点要分裂为两层，变为内部节点，此时记录数16是层数为2时最少的情况，最多的即为根节点和叶子节点均存满;以此类推分析：B+树中所有叶子节点在同一层，根节点最少有两棵子树，其余分支节点的子树个数为m/2到m;也就是题目中的阶数m为100;第6页/共20页期中考试：算法设计题：利用栈，判断一个字符串s是否是回文，若是返
3、回1,否则返回0;回文是指第一 个字符与最后一个相同，第二个字符与倒数第二个相同，依此类推。如：“abba”是回文，“abab”不是回文。空串和长度为1的串都是回文。可以直接使用如下定义中的基本操作。栈的ADT定义如下：template class Stack public:void clear();bool push(const T item);bool pop(T&);bool topValue(T&);bool isEmpty();bool isFull();层数层数最少记录数最少记录数最大记录数最大记录数101521615*100316*5015*(100*100)416*(50*50
4、)15*(100*100*100)516*(50*50*50)15*(100*100*100*100)第7页/共20页中期代码：bool checkString(string s)Stack T;string s1=;for(int i=0;ileftchild=null)return 1;for(TreeNode*temp=root-LeftChild;temp;temp=temp-RightSibling)count+=leavesCount(temp);return count第12页/共20页11.8对于11.26中的图，给出从顶点4开始出发，使用Dijkstra最短路径算法产生的最短
5、路径表，请向图11.19所示一样，每处理一个顶点时给出相应D值。第十四次作业-图Dijkstra算法的流程为：初始状态下，源顶点为4，除了顶点4，其余各个顶点的最短路径长度初值均为无穷大；处理完顶点4后，其相邻顶点的最短路径长度被更新为到4的直接距离；再选定当前离4最近的顶点作为下一个顶点，再更新余下顶点的值；依次类推；结果如下所示：第13页/共20页第14页/共20页11.17对于11.26中的图，给出从顶点3开始使用Prim的MST(最小支撑树：包含所有顶点以及一部分边的树，保证连通且所有权重最小)算法时各个边的访问顺序，并且给出最终的MST。Prim的MST的流程为：从图中任意一个顶点N
6、开始，题目中是指定顶点3即N为3，初始化MST为N，选出与N相关联的边中权值最小的一条边，其起始顶点则为N，M，则将(N,M)加入MST；再选择与顶点N,M相关联的边中权值最小的一条边，连接的新顶点为S,将S以及新边加入MST中；依次类推；结果如下所示：第15页/共20页最终的MST为：（，）（，）（，）（，）（，）以下为图的补充作业第16页/共20页一、单项选择题1下面（B）可以判断出一个有向图中是否有环（回路）？A）求关键路径B）拓扑排序C）求最短路径D）前面都不正确二、综合题1设有带权无向图G如下图所示：(讲解)试给出：（1）从V1开始的深度优先遍历；（2）从V1开始的广度优先遍历；（3
7、）从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)第17页/共20页2给出如下图所示的所有拓扑有序序列。答案：A-C-B-D-E不唯一 3.对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？答案：(1)无线图的邻接矩阵一定是对称的，那么矩阵的主对角线以上部分中有多少元素就代表图中的边树。设m为矩阵中非零元素的个数 无向图的边数=m/2(2)对于无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。第18页/共20页5.以右图为例，按Dijkstra算法计算得到的从顶点(A)到其它各个顶点的最短路径和最短路径长度。(讲解)第19页/共20页谢谢您的观看！第20页/共20页