当前位置：查字典考研网 > 历年真题 > 专业课试题 > 清华大学2000年研究生考试数据结构和程序设计专业试题考研英语试题 | 考研数学试题 | 考研政治试题 | 专业课试题

清华大学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）。这种排存算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c.

①（3分）给出适用于计数排序的数据表定义；

②（7分）使用Pascal或C语言编写实现计数排序的算法；

③（4分）对于有n个记录的表，关键码比较次数是多少？

④（3分）与简单选择排序相比较，这种方法是否更好？为什么？

4、（10分）

在一棵表示有序集S的二叉搜索树（binary search tree）中，任意一条从根到叶节点的路径将S分为3部分：在该路径左边节点中的元素组成的集合S1；在该路径上的节点中的元素组成的集合S2；在该路径右边节点中的元素组成的集合S3.S＝S1∪S2∪S3.若对于任意的a∈S1，b∈S2，c∈S3，是否总有a<=b<=c？为什么？

5、（12分）请回答下列关于堆（Heap）的一些问题：

①（4分）堆的存储表示是顺序的，还是链接的？

②（4分）设有一个最小堆，即堆中任意节点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

③（4分）对n个元素进行初始建堆的过程中，最多做多少次数据比较（不用大O表示法）？

6、（12分）

已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。

栈的ADT函数有：

makeEmpty（s：stack）；置空栈

push（s：stack；value：datatype）；新元素value进栈

pop（s：stack）：datatype；出栈，返回栈顶值

isEmpty（s：stack）：boolean；判栈空否

队列的ADT函数有