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

同学情

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

学期：2021年春季                                       
4 u' T- ^0 }, n+ G" M& ^- }# Z课程名称【编号】：数据结构【0012】                        A卷                                
5 H( [# W$ k$ O. p: K8 q3 p:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
________________________________________
1 t1 E# Y: k% @7 N一、大作业题目
) j0 E, {* ]# }: Y8 _8 e% ^3 q  Z1.        已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。
. z6 ?' A) ]: g% T2.        设一个无向图的邻接矩阵如右图所示：      
（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；
" Q: c: U- ]8 ]( G' W
3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。
2 C" b) I! u/ ?7 a4、编写算法，实现串的基本操作Replace(&S,T,V)。

2 C& ]' @& _; z1 b5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
* N, e( N) L% Z+ z（1）计算出每一个元素的散列地址并在下图中填写出散列表：
! h" x/ p$ S8 J                       0      1       2     3      4    5      6
  　        　        　        　        　        　       
（2）求出在查找每一个元素概率相等情况下的平均查找长度。

: X: H) Y4 u' L# C0 i2 Y( U二、大作业要求

- j7 L6 r( C; _9 F. @0 o$ Y选作2题，每题50分，更多资料下载：谋学网（www.mouxue.com）100分。

4 \+ f. k5 ^9 i9 j
% j7 l/ |; _0 V
4 `; ?9 ]+ u6 R& O' V4 H. Z% ?  _
, O7 J- j( }4 H  t8 N) Z
1 |  g+ C, n/ @9 y


2 x  s: R  j8 H
# L6 Z/ h( d3 J" n9 J" p- u. f
6 v( J+ K- z" ?. |
5 }  h: g& z. g, [
# r8 G7 B2 d( G3 L, |. i
( P7 y3 ~# Q0 k9 X% {