清华大学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)。这种排存算法对一个待排序的 表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中 所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一
趟,统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录,统计 出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c ①(3分)给出适用于计数排序的数据表定义; ②(7分)使用 Pascal或C语言编写实现计数排序的算法 ③(4分)对于有n个记录的表,关键码比较次数是多少? ④(3分)与简单选择排序相比较,这种方法是否更好?为什么 4(10分) 在一棵表示有序集S的二叉搜索树( binary search tree)中,任意一条从根到叶节点 的路径将S分为3部分:在该路径左边节点中的元素组成的集合S1:在该路径上的节 点中的元素组成的集合S2;在该路径右边节点中的元素组成的集合S3。S=S1US2 US3。若对于任意的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中的所有元素逆置
趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计 出的计数值为 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: stac k;vaue: dataty pe);新元素vaue进栈 pop(s: stack) dataty pe;出栈,返回栈顶值 is Empty(s: stack) boolean;判栈空否 队列的ADT函数有 enqueue( A queue; value: dataty pe);元素 value进队 de Queue( q queue): dataty pe;出队列,返回队头值 is Em pty( q:queue): boolean;判队列空否 7(13分) 设散列表为HT[0.12]即表的大小为m=13。现采用双散列法解决冲突。散列函数和在 散列函数分别为: H0(key)=key%13;注:%是求余数运算(=mod) Hi=(Hi-1+REV(key+1)%11+1)%13;=1,2,3,…,m-1 其中,函数REV(x)表示颠倒10进制数x的各位,如REV(37)=73REV(7)=7等。若 插入的关键码序列为{28,31,2019,185327}。 ①(8分)试画出插入这8个关键码后的散列表 ②(5分)计算搜索成功的平均搜索长度AsL
栈的 ADT 函数有： m akeEm pty(s:stack); 置空栈 push(s:stack; value:datatype); 新元素 value 进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEm pty(s:stack):boolean; 判栈空否 队列的 ADT 函数有 enqueue(q:queue;value:datatype); 元素 value 进队 deQ ueue(q:queue):datatype; 出队列，返回队头值 isEm pty(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 i或￠语言编写一个算法,从任一给定位置(pr;p)开始,将指 针p右移1个节点。如果p移出链表,则将p置为NULL,并让pr留在链表最右边的 节点上。 ②(6分)使用 Pasca或C语言编写一个算法,从任一给定位置(pr,p)开始,将指 针p左移一个节点。如果p移出链表,则将p置为NULL,并让pr停留在链表最左边的 节点上
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 停留在链表最左边的 节点上
