数据结构复习题集(下).ppt

数据结构复习题集（下）,第十一次作业-查找,9.6假定值A到H存储在一个自组织线性表中，开始按照升序存放，对于9.2小节建议的三种自组织启发式规则，按照下面顺序访问线性表，给出结果线性表和需要的比较总数：自组织线性表根据实际的记录访问模式在线性表中修改记录顺利。使用自启发规则决定如何重新排列线性表。,1若在线性表中采用折半查找法查找元素，该线性表应该（C）。A）元素按值有序B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构D）元素按值有序，且采用链式存储结构2在下列查找方法中，平均查找速度是快的是（B）。A）顺序查找B）折半查找C）分块查找D）二叉排序树查找3在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与(B）量级相当。A）顺序查找B）折半查找C）分块查找D）前面都不正确,1.保持一个线性表按照访问频率排序的最显然的方式是为每条记录保存一个访问计数。一直按照这个顺序维护记录，称为计数方法(Count),2.如果找到一个记录就将其放在线性表的最前面，而把后面的记录后退一个位置。,3.把找到的记录与它在线性表中的前一条记录交换位置，称为转置(transpose),9.13假定把关键码K散列到有n个槽(从0到n-1编号)的散列表中。对于下面的每一个函数h(K)，这个函数作为散列函数可以接受吗?(即对于插入和检索，散列程序能否正常工作)？如果可以的话，它是一个好的散列函数吗？函数Random(n)返回一个0到n-1之间的随机整数(包括这两个数在内)。(a)h(k)=k/n,其中k和n都是整数；(b)h(k)=1；(c)h(k)=(k+Random(n)mod n；(d)h(k)=k mod n，其中n是一个素数；,答案：(a)不可以。若k大于n平方,那么k/n的值就会超出n,超出范围。(b)可以。但是所有的数据都散列到相同的槽位中(c)不可以。因为采用随机数，那么插进去之后，检索不到，因为不知道此元素是使用了什么数据进行插入的(d)可以,9.16 使用闭散列，利用双散列的方法解决冲突，把下面的关键码插入到一个有13个槽的散列表中(槽从0到12编号)。使用的散列函数H1和H2在下面定义。给出插入8个关键码值后的散列表。一定要说明如何使用H1和H2进行散列。函数Rew(k)颠倒10进制数k各个位的数字，例如Rew(37)=73,Rew(7)=7。H1(k)=k mod 13.H2(k)=(Rew(k+1)mod 11).,答案：双散列：di=i*Hash2(key)，当通过第一个散列函数得到的地址发生冲突之后，则利用第二个散列函数计算该关键字的地址增量，在双散列中，最多经过m次探测就会遍历表中所有的位置，会到H0的位置。H1：2,8,5,7,6,5,1,1H2：3,9,1,1,2,3,1,5,插入过程：2-2 成功8-8 成功31-5 成功20-7 成功19-6 成功18-5 冲突；使用H1()+H2()=5+3=8 冲突 使用H1+H2+H2=5+3+3=11 成功53-1 成功27-1 冲突；使用H1()+H2()=1+5=6 冲突,使用H1+H2()+H2()=1+5+5=11 冲突 使用H1()+H2()+H2()+H2()=(1+5+5+5)%13=3 成功,1已知关键字序列23，13，5，28，14，25，试构造二叉排序树。,2.已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：H(key)=key MOD 13，哈希地址空间为012，请构造用链地址法处理冲突的哈希表，并求平均查找长度。,3.已知哈希表地址空间是0.8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列100,20,21,35,3,78,99,45数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。,平均查找长度L=(4*1+2+4+5+7)/8=2.75,4已知关键字序列12,26,38,89,56，试构造平衡二叉树。,10.8 给出把值55与46插入下图的2-3树中的结果。,图-插入删除,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;,11.4 Show the DFS tree for the graph of Figure 11.26,starting at Vertex 1.对于图11.26所示的图，给出其从顶点1开始的DFS树深度优先搜索树。答案：11.6 Show the BFS tree for the graph of Figure 11.26,starting at Vertex 1.对于图11.26所示的图，给出其从顶点1开始的BFS树广度优先搜索树。答案：,1采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（A）。A）先序遍历B）中序遍历C）后序遍历D）层次遍历2一个n个顶点的连通无向图，其边的个数至少为（A）。A）n-1B）nC）n+1D）nlogn,图-相关算法以及应用,（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所示图的相邻矩阵adjacency matrix 表示;（b）画出这个图的邻接表adjacency list表示;（c）如果每个指针需要4个字节，每个顶点的标号占用两个字节，每条边的权需要两个字节，则该图采用哪种表示方法需要的空间更多？（d）如果每个指针需要4个字节,每个顶点的标号需要一个字节，每条边的权需要两个字节，那么采用哪种表示方法需要的空间更多？,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)对于无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。,5.以右图为例，按Dijkstra算法计算得到的从顶点(A)到其它各个顶点的最短路径和最短路径长度。(讲解),