资源描述:
《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;}}}