资源描述：
《17秋西南大学数据结构【0012】机考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2017年12月A卷满分：100分（2）求出在查找每一个元素概率相等情况下的平均查找长度。第一题A-B（左）D（右）B-空（左）C（右）D-E（左）II（右）E-空（左）F（右）F-G（左）空（右）H_空（左）空（右）［叶子结点］后序遍历序列：CBGFEHDA笫三题一23,19,30,45,19,12西南大学网络与继续教育学院课程考试试题卷类別：M专业：计算机科学与技术课程名称【编号】：数据结构［0012】大作业一、大作业题目1、己知一棵树的先序遍历为ABCDEFFGH,中序遍历为BCAEGFDHo根据已知先序和中序遍历序列画岀树，然后写岀后序遍历序列。ro1,：oon2、设一匸无向图的邻接矩
2、阵如右图所示：I；；：；：即（1）画出该图；I101011IIo011o1I（2）画出从顶点0出发的深度优先生成树；Lo00!1oj3、请描述数列（23,19,30,45,19,12）进行升序快速排序的过程。4、编写算法，实现串的基本操作Replace（&S,T,V）o5、已知待散列的线性表为（36,15,40,63,22）,散列用的一维地址空间为［0..6］,假定选用的散列函数是H（K）=Kmod7,若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表：0123456二、大作业要求大作业共需要完成3道题：第1大题必做，满分30分；第2-3大题选做1题，满分
3、30分；第4-5大题选作1题，满分40分。二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,45第四题二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,45第四题要求实现以下函数：vxmdReplace(StnngType&S,StmgTypeXStringT>peV);*以串vsais中出現的所若和串t相方的非空串*/SmngT、pe是串的一个
4、抽象数据类塑，它包含以下6种基本操作：voidInitStr(StringIype&s);//初始化s为空串。voidStrAssign(StnngType&tStnngTypes);〃将S的洁赋给tos的实际参数是串交里。intStrCompare(StrtngTypes,Stnt^Typet):〃比较s和t。若sX,返回值>0；若Ft,遞回值Nh若返回值intStrLength(StnngTypes);〃返回S中的元棗个数，即该殆的长度。StringTypeConcat(StnngTypeStnngTypet);〃返回由s和t联接而成的新串。StringTypeSdbStnng(Strmg
5、T>pes,intstartmtlen);〃当10start<=StrLength(s)且(K^leirc^StrLer»th(s)-starts1时>返回s中第!iart个宇符起长度为kn的子串，否则返回空串。〃注意，不要使用”s=”的形式为StnngTXpe类型的变重赋值，//而要使用StrAssign函数!!！voidReplac&Strii^Type&S：Slrir^IpeTStrir^IypeV)/*以串v置换苗s中出現的所看和串t相同矗非空串*/{intLflag;Stringjypestrl,str2,str3;InitStr(strl)^ntStr(str2);IfitSt(
6、str3);for(i"l”■StrLength(SyStri.engthfT)*1；汁+){str1・SubStnng(Sj,StrLeng1h(T));fla^Stx€ompar«(slrl,T);if(flag—0){str2=SubStnre(SJ>l);str3=SubString(SJ亠StrLenglh(T)‘StrLer^th(S)-i-SuLength(T)+1);StrAssign(S.str2);Concal(S?V):Concal(S：slr3);i-^StrLer^th(V)-l;}}}
