《西南大学2020年春季数据结构【0012】大作业课程考试参考答案.pdf》由会员分享，可在线阅读，更多相关《西南大学2020年春季数据结构【0012】大作业课程考试参考答案.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、西南大学网络与继续教育学院课程考试试题卷西南大学网络与继续教育学院课程考试试题卷类别：网教专业：计算机科学与技术 2020 年 5 月课程名称【编号】：数据结构【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，则该算法的时间主要花费在查找链
2、表最后一个结点上（算法中的 while 循环），所以该算法的时间复杂度为 O（N）。-1-2）已知二叉树的先序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。答：二叉树形态3）试用权集合12,4,5,6,1,2构造哈夫曼树，并计算哈夫曼树的带权路径长度。答：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二、大作业要求二、大作业要求大作业共需要完成 3 道题：第 1 大题必做，满分 30 分；第 2-3 大题选做 1 题，满分 30 分；第 4-5 大题选作 1 题，满分 40 分。-2-WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=694）已知图 G 如下所示，根据 Prim 算法，构造最小生成树。（要求给出生成过程）答：-3-