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

同学情

西南大学培训与继续教育学院课程考试试题卷
& y  J7 }  C9 l  ]% a
# l0 X$ ~' x/ I) D% H7 \学期：2021年春季                                       
9 F6 \1 p' O" X课程名称【编号】：数据结构【0012】                        A卷                                
:大作业                                    更多资料下载：谋学网（www.mouxue.com）：100分
________________________________________
一、大作业题目
1.        已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。
( \+ F- y: l4 X& ~2.        设一个无向图的邻接矩阵如右图所示：      
9 r# O- D6 W: P/ O- i" \; h（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；
: Q; x9 G7 d, r
7 C" }  s3 K( C) j3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。
4、编写算法，实现串的基本操作Replace(&S,T,V)。
( _$ m4 T6 \5 o9 J! M
5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
                       0      1       2     3      4    5      6
  　        　        　        　        　        　       
/ x$ r) C1 q# T% Z' n: v9 U （2）求出在查找每一个元素概率相等情况下的平均查找长度。

二、大作业要求

$ N5 x) I9 A3 S0 {" i( }选作2题，每题50分，更多资料下载：谋学网（www.mouxue.com）100分。
- q8 {: y, O* b, e. F% W




6 y9 w' W# C! l- `( W/ Q



$ X+ X, r. r) x8 U3 ?0 K+ P3 A
; G1 G# q$ R6 w# L1 z
8 {. ]) X/ \  w. y* A

, M- C' {3 O# I7 w6 F
5 J5 W# c% ^6 C* u0 x