|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
吉林大学 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 的平衡性。试列出可能破坏ＨＴ的平衡性的所有情况，并论证
你的结论的正确性（即要证明你所列举的情况恰好是可能破坏ＨＴ的平衡性的所有情
况）。
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
