西南大学网络与继续教育学院课程考试答题卷 1） 编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答： void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR; while(p->next!=NULL) p=p->next; p->next=head; } 设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。 学号： 姓名： 201 7 年 6 月 课程名称【编号】：数据结构【0012】 （横线以下为答题区） 答题不需复制题目，写明题目编号，按题目顺序答题 1、选择题 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 2、填空题 1. 联系 图（或图结构） 2. 尾 首 3. top==0 4. O（1） O（n） 5. 128 44 108 6. 3 3 2） 已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。 答：二叉树形态 ABCEDFGH 3) 试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答： 3012187114567. 有序 n-1 3128. 有序序列 后缀表达式（或逆波兰式） 9. 2n n-1 n+1 10.2i+1 2i+2 (i-1)/2 3、应用题（第3大题选作2题） WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 - 1 - 4) 已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程） 5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。 解： (1)表形态： 0114122723681455256191720188439102311110212112 (2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6 - 2 -