17秋西南大学数据结构【0012】机考答案

西南大学网络与继续教育学院课程考试试题卷Р类别:网教专业:计算机科学与技术 2017年12月Р课程名称【编号】:数据结构【0012】 A卷Р大作业满分:100分Р大作业题目Р1、已知一棵树的先序遍历为ABCDEFFGH,中序遍历为BCAEGFDH。根据已知先序和中序遍历序列画出树,然后写出后序遍历序列。Р2、设一个无向图的邻接矩阵如右图所示: Р(1)画出该图; Р(2)画出从顶点0出发的深度优先生成树;Р3、请描述数列(23,19,30,45,19,12)进行升序快速排序的过程。Р4、编写算法,实现串的基本操作Replace(&S,T,V)。Р5、已知待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为[0..6],假定选用的散列函数是H(K)= K mod 7,若发生冲突采用线性探查法处理,试: Р(1)计算出每一个元素的散列地址并在下图中填写出散列表: Р 0 1 2 3 4 5 6Р Р Р Р Р Р Р(2)求出在查找每一个元素概率相等情况下的平均查找长度。Р二、大作业要求Р大作业共需要完成3道题:Р第1大题必做,满分30分;Р第2-3大题选做1题,满分30分;Р第4-5大题选作1题,满分40分。Р第一题РA - B(左)D(右)РB - 空(左)C(右)РD - E(左) H(右)РE - 空(左) F(右)РF - G(左)空(右)РH - 空(左)空(右)[叶子结点]Р后序遍历序列:CBGFEHDAР第三题Р一23,19,30,45,19,12Р二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Р第四题