清华大学美术学考研历年真题|考研历年真题：清华大学2000年“数据结构”试题
【shitiku.jxxyjl.com--考研】
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中的所有元素逆置。
[1] [2] 下一页
相关试题
- 【南京林业大学园林植物考研】南京林业大学2003年园林植物学考研试题
- 东北大学数据结构考研真题_东北大学2000年数据结构考研试题
- 北京大学历史考研历年真题_考研历年真题：北京大学2000年微观经济学考研试题
- 上海财经大学金融学考研科目|上海财经大学2000年金融学考研试题
- 清华大学美术学考研历年真题|考研历年真题：清华大学2001年编译原理和操作系统试题
- 【东北大学计算机组成与系统结构】东北大学2000年计算机组成原理考研试题
- [南京林业大学2003年快题]南京林业大学2003年土壤农化分析考研试题
- 【北京大学历史考研历年真题】考研历年真题：北京大学2000年宏观经济学考研试题
- 上海财经大学西方经济学考研真题_上海财经大学2000年西方经济学考研试题
- 【1980年北京广播学院分数线】北京广播学院2004年传播学理论与历史考研试题
-
【复旦大学企业管理考研】复旦大学2003年“企业管理”专业硕士研究生复试（笔试）考题详细阅读
一、试述我国企业管理的现状及发展的主要趋势（10分）。二、试用系统管理思想分析企业生产经营管理中某一种理论或方法的应用（10分）。三、分析以下案例（20分）。百事可乐公司与可口可乐公司1886年5月，名叫John Styth Pemberton的医生发明了可口可乐，它是将“可可”提取精与“可...
-
首都经济贸易大学会计学硕考研_首都经济贸易大学1999年会计学考研试题详细阅读
首都经济贸易大学1999年会计学考研试题注意事项：1、本卷共十二题，计100分。2、请将答案写在答卷上，不要写在试卷上。3、计算题答案取小数点后两位。4、试卷中所用“时间价值”自己计算。5、计算题应列出计算过程，不能只写答案。计算分析题：一、(本题18分)某企业销售一批商品，总价款400万元，分4年...
-
河南农业大学农业经济研究生|河南农业大学2003年农业经济管理复试试题详细阅读
河南农业大学2003年农业经济管理复试试题1、 试论农业企业生产经营风险的防范。(50分)2、 试论农业与工业的相互依存关系。(10分)3、 试论家庭承包经营体制的完善与发展。(40分)...
-
【武汉大学古代文学考研真题】武汉大学2004年古代文学考研试题详细阅读
一 名词解释:扬马花间词派 一祖三宗 桐城派 常州词派 (共六个三十分,不记得其他的了 顺序也不对)二 简答1 春秋战国时期散文有那些特点?2 简述沈,宋对近体诗的贡献3 试述你对词别是一家的理解4 清代传奇与元杂剧体制上的区别 三 论述1 以阮籍为代表的正始诗风对建安诗风有那些延续?2 清人...
-
考研西医综合考哪些科目_2002复旦考研西医综合科目试题详细阅读
一。a型题：共92个小题。在每小题给出的a、b、c、d、e五个选项中，只有一项是最符合题目要求的。 1 破坏反射弧中的任何一个环节，下列哪一种调节将不能进行？ a 神经调节 b 体液调节 c 自身调节 d 旁分泌调节 e 自分泌调节 2 可兴奋细胞兴奋的共同标志是 a 反...
-
首都经济贸易大学财务管理期末考试|首都经济贸易大学97年财务管理考研试题详细阅读
首都经济贸易大学97年财务管理首都经济贸易大学1997财务管理(会计专业)试题注意事项：1 本卷共十题，每题十分，共100分。2 请将答案写在答卷上(不要写在试卷上)3 计算题答案取小数点两位，如0 27或12 27%一、解释下列名词：理财环境 现金流量 金融资产 认股权证 最优资本结构二、简述通货...
-
【湖南师范大学古代汉语考研真题】湖南师范大学2004年古代汉语考研试题详细阅读
湖南师范大学2004年古代汉语考研试题学科、专业：汉语言文字学(050103)考试科目：古代汉语(327)一、写出下列各字的小篆或者古文字形体(20分)。心兵向毛豆至朱武牧取大聿水行衣自鸟犬女首二、解释下列术语(40分)：(1)古今字(2)指事(3)同...
-
武汉大学心理学研究生_武汉大学2003年心理学史考研试题详细阅读
科目；心理学史 代码：906一：名词解释1， 洛克的白板说2， 休莫的习惯原则3， 冯特的民族心理学4， 机能主义心理学5， 桑代克的效果律二：问答1简述亚里士多德关于人类灵魂的思想2简述西那的官能心理学3试述休莫的人类心理内容的分类4铁钦那在三种生物学和三种心理学间作了怎样的类比5适应心理学的本质...
-
华东师范大学心理学院_华东师范大学2000年心理统计与测量考研试题详细阅读
考试科目：心理统计与测量(需带计算器) 招生专业：心理学 心理统计部分 一、是非题(10分)：请仔阅读以下句子，判断其是否正确，用T表示正确，用F表示错误，填写在前面的括号中。注意，不得使用任何其他符号。 ( )1 差异系数是一种相对差异量。 ( )2 抽样分布指的是抽取的样本中个体数值的次数分布...
-
考研冲刺的推文_考研冲刺：中国古代文化史专题导练详细阅读
【知识梳理】一、百家争鸣的春秋战国文化春秋战国时期是我国由奴隶制向封建制转变的社会大变革时期。经济的发展、社会的变革，成为春秋战国时期科技文化大发展的前提和条件。铁器的使用和推广是这个时期生产力发展的重要标志。生产力的空前发展，促成科学技术的迅速发展，在天文学、物理学、医学等方面取得了具有当时世界先...