西南大学1912课程[0012]数据结构大作业
西南大学网络与继续教育学院课程考试试题卷 类别： 网教 专业：计算机科学与技术 2019年12月课程名称【编号】：数据结构【0012】 B卷大作业 满分：100 分一、 大作业题目1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。4）已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）http://www.ap5u.com/data/attachment/album/201911/29/120810qtvegbkqvuatk3ly.jpg5）设哈希表HT表长m为13，哈希函数为H(k)=k MODm，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。
二、大作业要求大作业共需要完成3道题：第1大题必做，满分30分；第2-3大题选做1题，满分30分；第4-5大题选作1题，满分40分。
页:
[1]