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

同学情

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

: ~3 l/ n! }4 c2 a; `0 `8 i学期：2020年秋季                                       
( H" K$ b* r  k: O课程名称【编号】：数据结构【0012】                         A卷                                
:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
________________________________________
+ X( O" j/ B. c) v$ Z! m一、大作业题目

- I2 w2 h9 I$ K7 S2 \1. 设无向图G（如图所示），给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。

- C8 O, N* Z, t; \1 b* c) i7 [
) ~" F# v/ Z( x8 G& t& P- J; w

3 u$ ?5 K- k5 g; z7 h/ @+ p
; J5 ], S# u2 U) d) c
2. 请画出下图的邻接矩阵和邻接表。

! }3 d! I" z' T: C& P8 s

0 _) f) G: @/ V* K* t1 `) C
/ I! N" C/ Z, W5 b5 p
2 O/ _  w, r/ U' I1 r: b7 T5 }
' n, ]* n& P. ]4 z
) n& \9 }/ \  Z8 b  u( j
% [$ N% C$ s. d7 w6 ~0 Z* j3、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。

4、字符a, b, c, d, e出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈夫曼树进行编码。
6 n" S6 o' ~8 |$ B1 g0 a( ^
5、已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知哈希函数为H(k)=k MOD 13，采用链地址法处理冲突，设计出该开哈希表的结构。
! R2 [, T6 z, ]
二、大作业要求
6 H) u* E3 J" G. h6 `+ U
每题50分，选作2题，更多资料下载：谋学网（www.mouxue.com）100分。
, ?/ C% @- o. f9 P
" y5 w$ k$ G4 e

; a! @, n$ K+ U5 b' o3 v
) t% d  |3 k+ U. c8 p
+ W' V8 C4 Q3 i( P1 C! Q) S& P
( j8 T0 t( G7 j% o* @2 c

, n8 q, m4 u9 K7 X* |( Q: m* v
" w+ o, F. m* [( h- l
' H0 U% q% d6 _' F7 u
; s& s1 x# ^/ @% _; \# r: y



) H+ H: o) Q2 |. _! F