数据结构作业12-13-14

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个子女，叶节点可以存储多达15

2、条记录，对于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 topValue(T&);bool isEmpty();bool isFull(); 层数层数最少记录数最少记录数最大记录数最大记录数101521615*100316*5015*(100*100)416*(50*50)15*(100*100*100)516*(50*

4、50*50)15*(100*100*100*100)中期代码：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 count11.8对于11.26中的图，给出从顶点4开始出发，使用Dijkstra最短路径算法产生的最短路径表，请向图11.19所示一样，每处理一个顶点时给出相应D值。第十四次作业-图

5、Dijkstra算法的流程为： 初始状态下，源顶点为4，除了顶点4，其余各个顶点的最短路径长度初值均为无穷大； 处理完顶点4后，其相邻顶点的最短路径长度被更新为到4的直接距离； 再选定当前离4最近的顶点作为下一个顶点，再更新余下顶点的值； 依次类推；结果如下所示：11.17对于11.26中的图，给出从顶点3开始使用Prim的MST(最小支撑树：包含所有顶点以及一部分边的树，保证连通且所有权重最小)算法时各个边的访问顺序，并且给出最终的MST。Prim的MST的流程为： 从图中任意一个顶点N开始，题目中是指定顶点3即N为3，初始化MST为N，选出与N相关联的边中权值最小的一条边，其起始顶点则为N

6、，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

7、,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)对于无向图，在矩阵