|
吉林大学 1997 年研究生考试题目
数据结构
一、简要回答下列问题：（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 的平衡性的所
有情况）
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
