清华大学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所指节点左侧的所有节点的连接方向都已逆转。
图1题8图
①(6分)使用Pascal或C语言编写一个算法,从任一给定位置(pr,p)开始,将指针p右移1个节点。如果p移出链表,则将p置为NULL,并让pr留在链表最右边的节点上。
②(6分)使用Pascal或C语言编写一个算法,从任一给定位置(pr,p)开始,将指针p左移一个节点。如果p移出链表,则将p置为NULL,并让pr停留在链表最左边的节点上。
【清华大学2000年研究生考试数据结构与程序设计专业试题】相关文章:
★ 湛江海洋大学2004年硕士研究生考试经济学专业基础课试卷
★ 上海财经大学1994年硕士研究生入学考试外国经济思想史试题
★ 中国政法大学1995年硕士研究生入学考试中国法律思想史试题
- 2020-06-28【专业课试题】2021考研管综逻辑300道推理题及答案(21)
- 2020-05-27【专业课试题】2020考研管理类联考综合全国硕士研究生考试试题及答案(网友版)
- 2020-05-27【专业课试题】2020考研管综逻辑演绎推理类型试题及答案解析(查字典考研网版)
- 2020-05-27【专业课试题】2020考研管综逻辑分析推理类型试题及答案解析(查字典考研网版)
- 2020-05-27【专业课试题】2020考研管综初等数学算术部分试题解析及往年对比
- 2020-05-27【专业课试题】2020考研管综初数条件充分性判断部分试题答案及解析(查字典考研网版)
网友关注
- 【专业课试题】2001年厦门大学高分子物理考研试题
- 【专业课试题】2001年厦门大学会计学考研试题
- 【专业课试题】2001年厦门大学市场流通经济学考研试题
- 【专业课试题】2001年厦门大学产业经济学考研试题
- 【专业课试题】2001年厦门大学高分子化学考研试题
- 【专业课试题】2001年厦门大学分析化学考研试题
- 【专业课试题】2000年厦门大学政治经济学考研试题
- 【专业课试题】2001年厦门大学综合考试(国际贸易学专业)考研试题
精品推荐
- 2021考研管综逻辑300道推理题及答案(21)
- 2020考研管理类联考综合全国硕士研究生考试试题及答案(网友版)
- 2020考研管综逻辑演绎推理类型试题及答案解析(查字典考研网版)
- 2020考研管综逻辑分析推理类型试题及答案解析(查字典考研网版)
- 2020考研管综初等数学算术部分试题解析及往年对比
- 2020考研管综初数条件充分性判断部分试题答案及解析(查字典考研网版)
- 2020考研管理类联考初数问题求解部分试题答案及解析(查字典考研网版)
- 2020考研管综初等数学数据分析部分试题解析及往年对比
- 2020考研管综初等数学平面图形部分试题解析及往年对比
- 2020考研管综初等数学空间几何体部分试题解析及往年对比