吉林大学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。试解答：
（1） 证明由A[1：n]和B[1：n]能唯一的确定二叉树T的结构；
（2） 给出建造二叉树T的算法，要求所建造的二叉树以LLINK/RLINK链接结构表示，且该算法是非递归算法；
（3） 分析你所给算法的时间复杂性，该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性。
二叉树公式五、（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的平衡性的所有情况）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。