西南大学培训与继续教育学院课程考试试题卷数据结构【0012】

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