《西南大学网络教育19.6月0012数据结构（答案）》由会员分享，可在线阅读，更多相关《西南大学网络教育19.6月0012数据结构（答案）（3页珍藏版）》请在金锄头文库上搜索。
1、西南大学网络与继续教育学院课程考试试题卷类别： 网教 专业： 计算机科学与技术 2019年06月课程名称【编号】： 数据结构【0012】 A卷大作业 满分：100 分一、 大作业题目1. 已知一棵树的先序遍历为ABCDEFFGH，中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树，然后写出后序遍历序列。2. 设一个无向图的邻接矩阵如右图所示： （1）画出该图； （2）画出从顶点0出发的深度优先生成树；答：3、 请描述数列（23，19，30，45，19，12）进行升序快速排序的过程。答：一23,19,30,45,19,12二12,19,30,45,19,23三12,19,23,45,1
2、9,30四12,19,19,45,23,30五12,19,19,23,45,30六12,19,19,23,30,45a(23,19,30,45,19,12)do until a(1)a(2) and a(2)a(3) and a(3)a(4) and a(4)a(5) and a(5)a(6)for i=1 to 5 if a(i)a(i+1) then a(i)=temp a(i)=a(i+1) a(i+1)=temp end ifnext iloopfor i=1 to 6print a(i)next i4、编写算法，实现串的基本操作Replace(&S,T,V)。答：算法如下：int S
3、tring_Replace(Stringtype &S,Stringtype T,Stringtype V); /将串S中所有子串T替换为V,并返回置换次数 for(n=0,i=1;iT0) /找到了与T匹配的子串:分三种情况处理 if(T0=V0) for(l=1;l=T0;l+) /新子串长度与原子串相同时:直接替换 Si+l-1=Vl; else if(T0=i+T0;l-) Sl+V0-T0=Sl; for(l=1;l=V0;l+) Si+l-1=Vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+V0;l=S0+V0-T0;l+) Sl=Sl-V0+T0; fo
4、r(l=1;l=V0;l+) Si+l-1=Vl; S0=S0-T0+V0; i+=V0;n+; /if /for return n;/String_Replace 5、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。答：（1）H(36)=36 mod 7=1; H (22)=(1+1) mod 7=2; . 冲突 H(15)=15 mod 7=1;. 冲突 H2(22)=(2+1) mod 7=3; H (15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; . 冲突 0 1 2 3 4 5 663 36152240（2）二、大作业要求大作业共需要完成2道题，每题50分，满分100分。 - 3 -
