吉大数据结构11997.docVIP

吉林大学97考研题 简要回答下列问题：（30分） 1．设A={a,b}，试写出P（A）上的集合的包含关系。 2．给出A={1，2，3}上的一个关系，使它同时不具有反身性、反对称性及传递性。 3．若半序集A是一个无限集合，问A是否可能有最大元素、极大元素？证明你的结论。 4．有人说“映射只不过是关系的另外一种表示方法”，你认为如何？为什么？ 5．设G是命题公式，G1是与G等价的析取范式，不用真值表，如何将G画为住析取范式？ 6．设S={G1，…，Gn}是命题公式集合，且公式HS你能给出从S出发推出GiVH的演绎吗？证明你的结论。 7．在有n个点的有向图中，会存在长度大于n的欧拉路吗？会存在长度小于n的欧拉路吗？为什么？ 8．在权图中，两点u，v的最短路，及距离是如何定义的？ 9．能否给出一个10个顶点的图G，且最小度为4，使G成为非Hamilton图？证明你的结论。 10．给出同余方程 ax=b(mod m)有唯一解及无解的条件。 二、（10分）设I是如下一个解释： D={a,b} P(a,a) P(a,b) P(b,a) P(b,b) 1 0 0 1 试确定下列公式在I下的真值 三、（10分）证明一整数能被3整除的充分必要条件是它的十进制数码的和能被3整除。 四、（20分）已知二叉树T的结点在先根次序下的排列为A[1]，A[2]，…，A[n]，在中根次序下的排列为B[1]，B[2]，…，B[n]，其中，A和B是一维数组，数组元素的值为T中相应的结点的INFO字段得值，并假定二叉树T中结点的INFO字段的值互不相同，n=0。试解答： 证明由A[1：n]和B[1：n]能唯一的确定二叉树T的结构； 给出建造二叉树T的算法，要求所建造的二叉树以LLINK/RLINK链接结构表示，且该算法是非递归算法； 分析你所给算法的时间复杂性，该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性。 五、（16分）假定G=（V，E）是有向图，V={1，2，…，n }，n=1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到 j有边，则A[ i,j]=1，否则A[ i,j]=0。请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O（ ） 六、（14分）设二叉树HT是一棵高度平衡树，当使用二叉查找与插入算法插入一个新的结点时，该操作可能会破坏HT的平衡性。试列举出可能破坏HT的平衡性的所有情况，并论证你的结论的正确性（即要证明你所列举的情况恰好是可能破坏HT的平衡性的所有情况）