清华大学2000年硕士生入学考试数据结构与程序设计试题.pdf
版权申诉
195 浏览量
2024-04-25
12:19:52
上传
评论
收藏 93KB PDF 举报
清华大学 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)。这种排存算法对一个待排序的
表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中
所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一
资源评论
