|
西南大学培训与继续教育学院课程考试试题卷
( d! x) U! }5 Z9 m
, F3 e6 i4 z _4 Z+ p+ \# X7 _学期:2020年春季 8 I1 n0 K: l: u7 _9 E6 T
课程名称【编号】: 数据结构【0012】 A卷4 [4 X5 Z% A! B3 A; F& E' o
考试类别:大作业 满分:100 分________________________________________
: ^! C3 }, Y9 f8 v' C) ^: N/ Q3 k8 z j* Y0 Z! q+ N" p
1)编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表,并分析算法的时间复杂度。
9 @' _3 q9 p; U& D+ D* f2)已知二叉树的先序遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。然后写出该二叉树的后序遍历序列。/ t0 x: o6 ^$ _' ~
3) 试用权集合{12,4,5,6,1,2}构造哈夫曼树,并计算哈夫曼树的带权路径长度。- ?! @2 i# l" R P! u$ G- u
4) 已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)
' h( V0 l4 S9 K: G% e & |. O1 f7 l; R( R0 Z
5)设哈希表HT表长m为13,哈希函数为H(k)=k MOD m,给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表,并求出在等概率的情况下查找成功的平均查找长度ASL。
) A6 ?# ?, T# W, W# C# t+ P0 k3 k8 t0 R) r
二、大作业要求( n# O! R" F$ C2 Z* s7 D7 t" _
大作业共需要完成3道题:
) u$ _; J; _7 v5 ^1 U3 P- s第1大题必做,40分;
* L' d. j9 W. K! a+ p7 p第2,3大题选作1题,满分30分;1 d) a: F+ ]( j" U
第4,5大题选作1题,满分30分。% Z. w# B. u0 j, u
# z. J& X1 ~" s5 {
) L$ A5 v! y7 I/ C2 b* D6 p& m+ W' ~- A, i4 n
* s4 f* @* s% ?+ M
. f% R# a8 ]# @ X: Y9 v8 [& s6 L
& i3 G6 J$ P! l" E) H+ L |
|