西南大学网络与继续教育学院课程考试试题卷类别： 网教 专业：计算机科学与技术 课程名称【编号】： 数据结构 【0012】 B 卷大作业 满分：100 分一、 大作业题目1）编写算法,将一个头指针为 head 不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。void linklist_c（Lnode*heaD.{Lnode*p；p=head；if（!p）returnERROR；while（p->next!=NULL）p=p->next；p->next=head；}设单链表的长度（数据结点数）为 N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的 while 循环），所以该算法的时间复杂度为 O（N）。2）已知二叉树的先序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。答：二叉树形态3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。答：WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=694）已知图 G 如下所示，根据 Prim 算法，构造最小生成树。（要求给出生成过程） 答：- 1 - 5）设哈希表 HT 表长 m 为 13，哈希函数为 H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度 ASL。答：（1）表形态：(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6- 2 -