|
吉林大学 1998 年研究生考试题目
一．简要回答下列问题
1． 在有个结点的有向图中，会存在长度大于 n 的欧拉路吗？会存在长度小于 n 的欧拉路
吗？为什么？
2． 在权图中，两点 u,v 的最短路及距离是如何定义的？
3． 能否给出一个１０个顶点的图 G，且最小度为４，是 G 成为非 HALMILTON 图？证
明你的结论。
二．已知二叉树 T 的结点在先根次序下的排列为 A[1],A[2],…A[n]，在中根次序的排列为
B[1],B[2],…B[n]．其中，A 和 B 是一维数组，数组元素的值为 T 中相应节点的 INFO 字段
值，并假定二叉树中节点的 INFO 字段的值互不相同，试回答：
１．证明由 A[1:n]和 B[1:n]能唯一地确定二叉树的结构；
２．给出建造二叉树 T 的算法，要求所建造的二叉树以 LLINK/RLINK 链接结构表
示，且该算法是非递归算法；
３．分析你所给算法的时间复杂性，该过程包括如何确定基本运算，如何推导出期望
复杂性和最坏复杂性。
三．假定Ｇ＝（Ｖ，Ｅ）是有向图，Ｖ＝｛１，２，．．．，Ｎ｝，Ｎ＞＝１，Ｇ以邻接矩阵
方式存储，Ｇ的邻接矩阵为Ａ，即Ａ是一个二维数组，如果Ｉ到Ｊ有边，则Ａ［I,j］=1，
否则 A[I,j]=0，请给出一个算法，该算法能判断 G 是否是非循环图（即 G 中是否存在回
路），要求算法的时间复杂性为 O(n*n)。
四．设二叉树 HT 是一棵高度平衡树，当使用二叉查找树的查找与插入算法插入一个新的节点
时，该操作可能会破坏 HT 的平衡性。试列出可能破坏ＨＴ的平衡性的所有情况，并论证
你的结论的正确性（即要证明你所列举的情况恰好是可能破坏ＨＴ的平衡性的所有情
况）。
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
