西南大学培训与继续教育学院课程考试试题卷课程名称【编号】：数据结构【0012】 A 卷 考试类别:大作业 满分：100 分一、大作业题目1. 已知一棵树的先序遍历为 ABCDEFFGH， 中 序 遍 历 为BCAEGFDH。根据已知先序和中序遍历序 列画出树，然后写出后序遍历序列。2. 设一个无向图的邻接矩阵如右图所示： （1）画出该图； （2）画出从顶点 0 出发的深度优先生成树；3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。4、编写算法，实现串的基本操作 Replace(&S,T,V)。5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 　 　 　 　 　 　 （2）求出在查找每一个元素概率相等情况下的平均查找长度。二、大作业要求选作 2 题，每题 50 分，满分 100 分。1.答：A - B（左）D（右）B - 空（左）C（右）D - E（左） H（右）E - 空（左） F（右）F - G（左）空（右）H - 空（左）空（右）[叶子结点]后序遍历：CBGFEHDA3.答： 23① ，19，30，45，19,12 12② ，19，30，45，19，23 12③ ，19，23，45，19，23 12④ ，19，23，45，19，30 12⑤ ，19，19，23，45，30 12⑥ ，19，19，23，30，454.答：void Replace(StringType &S, StringType T, StringType V)/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */{ int n,m,k,i; StringType sub; InitStr(sub); n = StrLength(S); m = StrLength(T); k = StrLength(V); i = 1; while(i <= n-m+1){ StrAssign(sub,SubString(S,i,m));//将串 C 中的子串逐个提取出来与串 T 进行匹配 if(StrCompare(sub,T) == 0){//匹配相等时 InitStr(sub); Concat(sub,SubString(S,1,i-1));//将匹配相等的子串的前面的子串连接到串 sub 后 Concat(sub,V);//将替换串连接到串 sub 后 Concat(sub,SubString(S,m+i,n-(m+i)+1));//将匹配相等的子串的后面的子串连接到串 sub 后- 1 - StrAssign(S,sub); i += k; n = StrLength(S);//操作完一次之后，串 S 已经改变，需要注意 } else{ ++i; } } }5.答：解答：（1）0 1 2 3 4 5 663 36 15 22 40（2）ASL=1+2+1+1+35=1. 6- 2 -