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

同学情

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

. ^4 T+ e7 r- V' x4 W学期：2021年春季                                       
" k9 p6 j4 B3 |+ W$ c( T5 S$ i课程名称【编号】：数据结构【0012】                        A卷                                
- T" d$ W) e0 z: B+ ]' Y( ^:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
0 q% p, t3 o5 R4 i! x) M0 m________________________________________
一、大作业题目
' Q; k  R0 D* x3 i  z& m$ j1.        已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。
2.        设一个无向图的邻接矩阵如右图所示：      
9 R" @7 t! B2 L3 J* ~（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；

4 k& ~: p3 B" b9 h  q; ?3 i7 L& X- V3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。
' l% I! V5 A0 ~- i3 R9 u' }3 _+ p4、编写算法，实现串的基本操作Replace(&S,T,V)。

5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
$ u7 r, H+ V3 R1 m& ]% p: d8 A                       0      1       2     3      4    5      6
  　        　        　        　        　        　       
" F. ]% ]" J8 G. g3 m: d （2）求出在查找每一个元素概率相等情况下的平均查找长度。
; m% p+ H' s: ]( o9 i
二、大作业要求
7 F) e2 {. {8 A( w
) G6 X1 d, R& e! P3 p! V% ]选作2题，每题50分，更多资料下载：谋学网（www.mouxue.com）100分。


* S6 ~5 |' ^' l  ?3 j  b) l


, N5 W4 m* f2 M+ c# Z: J) n- J


3 o6 S3 T1 @2 g
/ F% s& P6 l  k

4 ^. S5 A2 g  L- @* S! d
) i# t- d/ \* C& x5 z% u

7 K; p+ U* M5 Q- B; x+ L