西南大学2021年春季数据结构【0012】大作业参考答案.pdf

西南大学网络与继续教育学院课程考试试题卷西南大学网络与继续教育学院课程考试试题卷一、一、大作业题目大作业题目学期：2021 年春季课程名称【编号】：数据结构【0012】A 卷考试类别:大作业满分：100 分1.已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。答：A-B（左）D（右）（左）C（右）H（右）（左）F（右）F-G（左）空（右）H-空（左）空（右）叶子结点后序遍历：CBGFEHDA2.设一个无向图的邻接矩阵如右图所示：（1）画出该图；（2）画出从顶点 0 出发的深度优先生成树；3、请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。答：一 23,19,30,45,19,12 B-空 D-E（左）E-空二 12,19,30,45,19,23三 12,19,23,45,19,30四 12,19,19,45,23,30五 12,19,19,23,45,30六 12,19,19,23,30,454、编写算法，实现串的基本操作Replace(&S,T,V)。答：int Replace(Stringtype&S,Stringtype T,Stringtype V);/将串 S 中所有子串 T 替换为 V,并返回置换次数for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i+)/注意 i 的取值范围-1-if(!StrCompare(SubString(S,i,Strlen(T),T)/找到了与 T 匹配的子串/分别把 T 的前面和后面部分保存为 head 和 tailStrAssign(head,SubString(S,1,i-1);StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1);StrAssign(S,Concat(head,V);StrAssign(S,Concat(S,tail);/把 head,V,tail 连接为新串i+=Strlen(V);/当前指针跳到插入串以后n+;/ifreturn n;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 分。-2-