2、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABCDFGJEHKLIM 中序遍历序列： BAFDJGCKHLEIM。（7分） （1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
3、将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组散列函数：H(key)=(key×3)MOD T，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。（10分） 问题：（1）请画出所构造的散列表；
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
试卷A 第6页 共9页
4、请利用Dijkstra算法求图1中从顶点1 到其他个顶点间的最短路径。（10分）（注：写出 执行算法过程中各步的状态）
62 1 10 5 32 15 2 3 6
20 61 8 图1
3 6 7 15 4 6 8 3 10 7 试卷A 第7页 共9页
5、 如图2所示的AOE网，计算每个活动（弧）的最早开始时间e和最迟开始时间l，每个事
件（顶点）的最早开始时间Ve和最迟开始时间Vl，并给出关键路径。(10分)
B132C2524E6353F1GAD图2
试卷A 第8页 共9页
五、程序题（本大题共1小题，共8分） 1、已知一个带有表头结点的单链表，结点结构为
data link 假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求： （1）描述算法的基本设计思想 （2）描述算法的详细实现步骤
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C语言实现），关键之处请
给出简要注释。
试卷A 第9页 共9页