清华大学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函数有
enqueue(q:queue;value:datatype); 元素value进队
deQueue(q:queue):datatype; 出队列，返回队头值
isEmpty(q:queue):boolean; 判队列空否
7 （13分）
设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和在散列函数分别为,
H0(key)=key%13; 注：％是求余数运算（＝mod）
Hi=(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,…，m-1
其中，函数REV（x）表示颠倒10进制数x的各位，如REV(37)=73,REV(7)=7等。若插入的关键码序列为{2,8,31,20,19,18,53,27}。
①（8分）试画出插入这8个关键码后的散列表。
②（5分）计算搜索成功的平均搜索长度ASL。
8 （12分）
从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如图1所示。在图中的指针p指向当前正在访问的节点，指针pr指向指针p所指节点的左侧的节点。此时，指针p所指节点左侧的所有节点的连接方向都已逆转。
①（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p右移1个节点。如果p移出链表，则将p置为NULL，并让pr留在链表最右边的节点上。
②（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p左移一个节点。如果p移出链表，则将p置为NULL,并让pr停留在链表最左边的节点上。
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函数有
enqueue(q:queue;value:datatype); 元素value进队
deQueue(q:queue):datatype; 出队列，返回队头值
isEmpty(q:queue):boolean; 判队列空否
7 （13分）
设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和在散列函数分别为,
H0(key)=key%13; 注：％是求余数运算（＝mod）
Hi=(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,…，m-1
其中，函数REV（x）表示颠倒10进制数x的各位，如REV(37)=73,REV(7)=7等。若插入的关键码序列为{2,8,31,20,19,18,53,27}。
①（8分）试画出插入这8个关键码后的散列表。
②（5分）计算搜索成功的平均搜索长度ASL。
8 （12分）
从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如图1所示。在图中的指针p指向当前正在访问的节点，指针pr指向指针p所指节点的左侧的节点。此时，指针p所指节点左侧的所有节点的连接方向都已逆转。
①（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p右移1个节点。如果p移出链表，则将p置为NULL，并让pr留在链表最右边的节点上。
②（6分）使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针p左移一个节点。如果p移出链表，则将p置为NULL,并让pr停留在链表最左边的节点上。
