清华大学2000考研题
一、请回答下列关于图(Graph)的一些问题：
(1)（4分）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
(2)（4分）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？
(3)（4分）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
二、斐波那奇数列Fn定义如下
F0=0， Fl=1， Fn=Fn_1+Fn_2, n=2,3...
请就此斐波那奇数列，回答下列问题·
(1) (7分) 在递归计算Fn的时候，需要对较小的Fn_1，Fn_2，...,F1,F0精确计算多少次?
(2) (5分) 如果用人0表示法，试给出适归计算Fn时递归函数的时间复杂度录多少?
三、有一种简单的排序算法，叫做计数排序（count sorting）.这种排序算法对一个待排存的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的录，表中所有带排序的关键码互不相同，计数排序算法针对表中的每个计录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对其一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放住位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
（2）(7分)使用Pascal或C语言编写实现计数排序的算法；
（3）(4分)对于有n个记录的表，关键码比较次较次数是多少?
(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?
四、(l0分)在一棵表示有序集S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点的元素组成的集合Sl；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈Sl,b∈S2，c∈S3是否总有a≤b≤c?为什么?
五、请回答下列关于堆(Heap)的一些问题：
(1) (4分) 堆的存存储表示录顺序的，还是链接的?
（2） (4分) 设有一个最小堆，即堆中任意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方?
(3) (4分)对n个元素进行初始化堆的过程中，最多做多少次数据比较（不用大0表示法）?
六、(12分) 已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。
栈的ADT函数有
makeEmpty(s:stack); 置空栈
push(s:stack;value:dattype); 新元素value进栈
pop(s:stack):datatype; 出栈，返回栈顶值
isEmpty(q:queue):Boolean; 判栈空否
队列的 ADT函数有
emqueue(q:queue:value:datatype); 元素value进队
deQueue(q:queue):datatype; 出队列，返回队头值
isEmpty(q:queue):Boolean; 判队列空否
八、设散列表为HT [0..12],即表的人小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：
Ho(key)=key%13; 注:%是求余数运算(=mod)
H=(H +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，1918，53，27)。
(1)（8分）试画出插入这8个关键码后的散列表
(2) (5分)计算搜索成功的平均搜索长度ASL。
九、从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中连接方向逆转，如下图所示。在图中的指针P指向当前正在访问的结点，指针pr指向指针P所指 结点的左侧的结点。此时，指针P所指结点左侧的所有结点的链接方向都已逆转。
(1) (6分) 使用Pascal或C语言编写一个算法，从任一给定位置（pr,p）开始，将指针P右移l个始点。如果P移出链表，则将p置为NULL，并让pr停留在链表最右边的结点上。
(2) (6分)使用Pascal或c语言编写一个算法，从任一给定位置（pr,p）开始，将指针P左移l个结点。如果p移出链表，则将p置为NULL。并让pr停留在链表最左边的结点上。
