[0012]数据结构西南大作业答案
发布时间:2023-09-25 10:09:32浏览次数:9西南大学网络与继续教育学院课程考试试题卷类别: 网教 专业:计算机科学与技术 课程名称【编号】: 数据结构 【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 -