储;(3).基于邻接矩阵写出图的深度、广度优先遍历序列;30.30.一带权无向图的邻接矩阵如下图,试画出它的一棵最小生成树。12111113123456设顶点集合为{1,2,3,4,5,6},由右边的逻辑图可以看出,在{1,2,3}和{4,5,6}回路中,各任选两条边,加上(2,4),则可构成9棵不同的最小生成树。31.试写出用克鲁斯卡尔(Kruskal)算法构造下图的一棵最小支撑(或生成)树的过程。12564318412810202515523767V(G)={1,2,3,4,5,6,7}E(G)={(1,6,4),(1,7,6),(2,3,5),(2,4,8),(2,5,12),(1,2,18)}32.设哈希(Hash)表的地址范围为0~17,哈希函数为:H(K)=KMOD16,K为关键字,用线性探测再散列法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表,试回答下列问题:(1)画出哈希表示意图;(2)若查找关键字63,需要依次与哪些关键字比较?(3)若查找关键字60,需要依次与哪些关键字比较?(4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。(1)散列地址01234567891011121314151617关键字3217634924401030314647比较次数11631211133(2)查找关键字63,H(k)=63MOD16=15,依次与31,46,47,32,17,63比较。(3)查找关键字60,H(k)=60MOD16=12,散列地址12内为空,查找失败。(4)=23/1133.选取哈希函数H(key)=keymod7,用链地址法解决冲突。试在0-6的散列地址空间内对关键字序列{31,23,17,27,19,11,13,91,61,41}构造哈希表,并计算在等概率下成功查找的平均查找长度。
全文预览
