21春西南大学课程名称 数据结构【0012】大作业

同学情

西南大学培训与继续教育学院课程考试试题卷
. B8 j. g8 Z. t7 n* _7 Q8 B4 p& U
学期：2021年春季                                       
# I$ d+ r- x+ L" `课程名称【编号】：数据结构【0012】                        A卷                                
, D' k- y+ [2 Z: S' u:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
________________________________________
& ]+ Y1 N* _) F  B% `* u一、大作业题目
1 t! f9 P7 a2 v7 d0 r1.        已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。
2.        设一个无向图的邻接矩阵如右图所示：      
（1）画出该图；
0 O  l% r; |4 b( |# ]（2）画出从顶点0出发的深度优先生成树；

' @  w& j% H  }7 X' D" M3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。
4、编写算法，实现串的基本操作Replace(&S,T,V)。

+ N* h: g4 L8 J. Z3 f: J7 |  x$ F5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
                       0      1       2     3      4    5      6
  　        　        　        　        　        　       
$ D1 S$ {* u5 U （2）求出在查找每一个元素概率相等情况下的平均查找长度。
+ b) h5 D- R+ q9 p9 l( S$ n
二、大作业要求
: w2 _- M0 M# _2 b0 w: e( P
选作2题，每题50分，更多资料下载：谋学网（www.mouxue.com）100分。
8 t0 i# Y& o3 s, B1 u: Y; K' z* O
) w3 ]2 H+ ^& R$ }/ `: U  F2 D( p: ?
# {  y, z3 B; P* W  g  F# y




& |% a! T  N- Q4 q4 V

1 E" y& H  O' v' D+ ?2 K5 T8 L) T
4 v- U, |0 M$ o- a) M6 B



! |0 K6 I8 d. B8 q* d* B  u