|
|
西南大学培训与继续教育学院课程考试试题卷
; W! l/ w4 E3 A
- i V( H( Z# L- [# ^5 X学期：2020年春季
6 o$ f; L( O# K课程名称【编号】： 数据结构【0012】 A卷4 r7 y1 _0 ~/ d6 W4 I4 u
考试类别:大作业 满分：100 分________________________________________# M" g: n$ U# Z- V. l, F5 V$ V
# ?, C1 u( Z! R4 I- U! j1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。8 x" |! K; I& m: v% V) x
2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。然后写出该二叉树的后序遍历序列。
) Q$ l4 @' Y% K* U; n3） 试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。! U7 w( b4 Y8 H
4） 已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）
: w5 ?( `1 J# d1 P# @ , j7 x' d% s: o G& Z% G, H5 N
5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。1 @( s) A! a* S' t3 j3 S* A+ _5 d# C6 B
( O. s: @- Z% V: o! i二、大作业要求
# I' m6 X {9 b大作业共需要完成3道题：
. ?( _. a$ z6 Y3 b8 R8 f4 q1 S5 D第1大题必做，40分；7 f8 Q ~& ]; H) h
第2,3大题选作1题，满分30分；
/ ~9 G/ C9 h; s" q1 U3 g3 C0 \第4,5大题选作1题，满分30分。
- H+ v; u, m; P& X) C7 a2 u1 Q [ J
, n7 {! O3 C. p; \+ S, j3 h
9 L7 h: }+ G1 R9 B. ^# d- w, E% G4 r2 h
- Q3 C% p1 z7 `. r$ x6 | v" c
+ K- B; d9 Q" `' e" f# l
|
|
IP卡
狗仔卡
发表于 2020-6-10 15:53:57
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2020-6-10 16:18:16
客服一
