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

同学情

西南大学培训与继续教育学院课程考试试题卷
+ c- V2 N1 a; Q4 ?1 z; S4 j" w
学期：2020年秋季                                       
; ^" p7 |/ {6 w6 P5 Q2 s课程名称【编号】：数据结构【0012】                         A卷                                
:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
2 A% B2 X* A9 O! V8 n5 i% E________________________________________
+ `+ i6 Y, t6 k3 |8 Z$ Z一、大作业题目
2 Z7 l) w( W4 A8 x$ t
1. 设无向图G（如图所示），给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。


3 z8 l  `7 }7 I6 ~
$ _  |, `8 N2 ?2 \

8 Y9 A% }2 C7 p; R
2. 请画出下图的邻接矩阵和邻接表。
! O! _, y6 f+ b5 e' O1 S* c+ }
) y# A+ o( J5 f9 R
, b7 K2 q4 A& `2 k1 b& _  N

" O6 E+ Y' w7 h4 s
% s) z2 R' a2 I0 v! |* y8 T
1 Z7 z% D9 U  v4 T% {, ^/ Y8 Q
. }6 O# ]* O" L% w
+ x4 z) y% G4 H* u3、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
/ t0 Z( B: L2 b# Y3 ~* G  W
( U) F3 C5 s1 [' G4、字符a, b, c, d, e出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈夫曼树进行编码。

5、已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知哈希函数为H(k)=k MOD 13，采用链地址法处理冲突，设计出该开哈希表的结构。

二、大作业要求
5 ^% d' ~7 X0 a, \% E# |2 ~! y
: F* L( u9 _" e5 _3 P每题50分，选作2题，更多资料下载：谋学网（www.mouxue.com）100分。
9 a! }4 `+ N6 K/ `4 y: W, j
* B* U& w4 z4 e( A# q3 K+ u

+ o, I/ w  E/ d/ ?
+ ?( [: C/ r# A. j1 J
! S8 m$ o" H" K7 I& |+ Y
7 s3 P6 A1 h% D6 P. ]% ]

9 ~- ?1 g) |9 u4 v

* V/ I+ |4 ?! S7 h! m
4 H. ~$ K3 \4 B) G$ h, x2 R
+ M7 U2 ^$ p8 N' Z6 X1 m
4 J  @, p7 N, S5 z3 H. Y

  b: t$ J" Q3 w5 L: H