数据结构期末考试题目及答案-.ppt

一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。查找成功的平均查找长度：ASL SUCC=14/10=1.40123456789101112781503574520312336121设ag 7个字符出现的概率为:=3,35,13,15,20,5,9,画出哈夫曼树，设计最优二进制码并计算平均码长。哈夫曼 编码：平均码长：(4*3+2*35+3*13+3*15+2*20+4*5+3*9)/100abcdefg0110101101110001110102给定如定如图所示二叉所示二叉树T T，请画出与其画出与其对应的中序的中序线索二叉索二叉树。要遵循中序遍要遵循中序遍历的的轨迹来画出每个前迹来画出每个前驱和后和后继。中序遍中序遍历序列：序列：55 40 25 60 28 08 33 543在KMP算法中，已知模式串为ADABCADADA，请写出模式串的nextj值。next0123456789-10010012324对于如图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)试给图的邻接表；(2)给出根据建立的邻接表从顶点出发进行深度优先搜索所得到的深度优先生成树；(3)给出根据建立的邻接表从顶点出发进行广度优先搜索所得到的广度优先生成树。DFS：BFS：5试对下图所示的AOE网络，解答下列问题。(1)求每个事件的最早开始时间Vei和最迟开始时间VlI。(2)求每个活动的最早开始时间e()和最迟开始时间l()。(3)确定哪些活动是关键活动。画出由所有关键活动构成的图。关键路径是：，即有两条关键路径：（v1，v2，v5，v7，v9）和（v1，v2，v5，v8，v9）6已知一个图的顶点集V各边集G如下：V=0，1，2，3，4，5，6，7，8，9；E=（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）（1）画出图的邻接矩阵表示和邻接表表示，假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的（2）分别写出用邻接矩阵表示和邻接表表示时从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。图深度优先序列广度优先序列邻接矩阵表示时0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9邻接表表示时0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，57 画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。8根据图 a,用prim算法从顶点v2开始求最小生成树。画出求解的各步骤。v1v3v2v4v54857121136(a)v2v45(b)(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45按按prime算法从算法从v2出出发构造最小生成构造最小生成树的的过程程9对下下图的无向的无向带权图：写出它的写出它的邻接矩接矩阵，并按普里姆算法求其最小生成，并按普里姆算法求其最小生成树；写出它的写出它的邻接表，并按克接表，并按克鲁斯卡斯卡尔算法求其最小生成算法求其最小生成树10