西南大学1906课程考试[0012]《数据结构》大作业（资料）

skystar

一、        大作业题目

            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）求出在查找每一个元素概率相等情况下的平均查找长度。

             二、大作业要求
             大作业共需要完成2道题，每题50分，满分100分。