西南大学网络与继续教育学院课程考试试题卷类别： 网教 专业： 计算机科学与技术 课程名称【编号】： 数 据结构【0012】 A 卷大作业 满分：100 分一、 大作业题目4、编写算法，实现串的基本操作 Replace(&S,T,V)。答：算法如下：int String_Replace(Stringtype &S,Stringtype T,Stringtype V); //将串 S 中所有子串 T 替换为 V,并返回置换次数{ for(n=0,i=1;i<=S[0]-T[0]+1;i++) { for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++); if(k>T[0]) //找到了与 T 匹配的子串:分三种情况处理 { if(T[0]==V[0]) for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l]; else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移 { for(l=S[0];l>=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } else //新子串长度小于原子串时:先将后部左移 { for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for return n;}//String_Replace5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 　 　 　 　 　 　 （2）求出在查找每一个元素概率相等情况下的平均查找长度。答：（1） 0 1 2 3 4 5 6 　63　 36　 15　 22　 40（2）ASL=二、大作业要求大作业共需要完成 2 道题，每题 50 分，满分 100 分。- 1 -