清华大学2000年硕士生入学考试数据结构与程序设计试题 1(12分) 请回答下列关于图( Graph)的一些问题: ①(4分)有n个顶点的有向连通图最多有多少条边?最少有多少条边? ②(4分)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵? ③(4分)对于一个有向图,不用拓扑排序,如何判断图中是否存在环? 2(12分) 斐波那契数列Fn定义如下: F0=0,F1=1,Fn=Fn-1+Fn-2,n=2,3 请就此斐波那契数列,回答下列问题 ①(7分)在递归计算Fn的时候,需要对较小的Fn-1,Fn-2,…,F1,F0精确计 算多少次? ②(5分)若干有关大O表示法,试给出递归计算Fn时递归函数的时间复杂度是多少? 3(17分) 有一种简单的排序算法,叫做计数排序( count sorting)。这种排存算法对一个待排序的 表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中 所有待排序的关键码互不相同。计数排序算法针对表中的每个记录,扫描待排序的表清华大学 2000 年硕士生入学考试数据结构与程序设计试题 1 (12 分) 请回答下列关于图(G raph)的一些问题： ①（4 分）有 n 个顶点的有向连通图最多有多少条边?最少有多少条边？ ②（4 分）表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？ ③（4 分）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 2 (12 分) 斐波那契数列 Fn 定义如下： F0=0, F1=1, Fn= Fn-1 + Fn-2, n=2,3,… 请就此斐波那契数列，回答下列问题： ①（7 分）在递归计算 Fn 的时候，需要对较小的 Fn－1，Fn－2，…，F1，F0 精确计 算多少次？ ②（5 分）若干有关大 O 表示法，试给出递归计算 Fn 时递归函数的时间复杂度是多少？ 3 （17 分） 有一种简单的排序算法，叫做计数排序(count sorting)。这种排存算法对一个待排序的 表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中 所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一