20年6月西南大学课程考试[0012]《数据结构》大作业（资料）

同学情

西南大学培训与继续教育学院课程考试试题卷

6 O+ H% g, D, l学期：2020年春季            
; q# X2 P) ~; b1 E: B& C0 _7 }课程名称【编号】： 数据结构【0012】          A卷
考试类别:大作业                             满分：100 分________________________________________
4 p/ S5 R6 p/ k# C( \$ Z6 {7 W
1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。
2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。
3）        试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。
4 u; i8 Q$ |2 G; H3 [! Z: C, |! x4）        已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）
  
5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。
( e& H6 U: F9 T+ z
! E: T2 I) V% s  i" W! g二、大作业要求
0 o1 m3 ~( p& g大作业共需要完成3道题：
2 H2 R3 U5 A0 ^+ z1 f. _: u! l第1大题必做，40分；
第2,3大题选作1题，满分30分；
! Z) t$ Y6 C7 f1 W) O: g& z第4,5大题选作1题，满分30分。
# l: u: [( x7 [. g( q; C
     
- d9 S7 c% C/ k+ N. `
7 ]2 e  c& F1 _5 o" a2 b
7 g. K) D3 e' r

8 o/ A, J+ f* a. C; b3 z* t! i1 f

万盆姬

谋学网还可以！

MIX

谢谢，满分