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

1、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12， 散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情 况下查找成功的平均查找长度。 查找成功的平均查找长度：ASL SUCC=14/10= 1.4 0123456789101112 78150357452031233612 设ag 7个字符出现的概率为: =3, 35, 13, 15, 20, 5, 9, 画出哈夫曼树，设计最优二进制 码并计算平均码长。 哈夫曼 编码： 平均码长：(4*3+2*35+3*13+3*15+2*20+4*5+3*9)/

2、100 abcdefg 011010110111000111010 给定如图所示二叉树给定如图所示二叉树T，请画出与其对应的中序线索二叉树，请画出与其对应的中序线索二叉树。 要遵循中序遍历的轨迹来画出每个前驱和后继。要遵循中序遍历的轨迹来画出每个前驱和后继。 中序中序遍历序列：遍历序列：55 40 25 60 28 08 33 54 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的nextj值。 next 0123456789 -1001001232 对于如图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按 照终点序号从小到大的次序链接的，试写出： (1)

3、试给图的邻接表； (2) 给出根据建立的邻接表从顶点出发进行深度优先搜索所得到的深度优先生成树； (3) 给出根据建立的邻接表从顶点出发进行广度优先搜索所得到的广度优先生成树。 DFS： BFS： 试对下图所示的AOE网络，解答下列问题。 (1) 求每个事件的最早开始时间Vei和最迟开始时间VlI。 (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (3) 确定哪些活动是关键活动。画出由所有关键活动构成的图。 关键路径是：， ， 即有两条关键路径：（v1，v2， v5，v7，v9）和（v1，v2，v5， v8，v9） 已知一个图的顶点集V各边集G如下： V = 0，1，2，3，

4、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，5 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 根据图 a, 用prim算法从顶点v2开始求最小生成树。画出求解的各步骤。 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (a) v2 v4 5 (b) (c) v5 3 v2 v4 5 (d) v1 4 v5 3 v2 v4 5 v3 6 (e) v1 4 v5 3 v2 v4 5 按按prime算法从算法从v2出发构造最小生成树的过程出发构造最小生成树的过程 对下图的无向带权图：对下图的无向带权图： 写出它的邻接矩阵，并按普里姆算法求其最