[quote]
coldsummer: Re:Re:07年考研试题集中贴
为了后来的学弟学妹们,我来补充一下!<!-- CETagParser ~/quote
</td></tr></table></td></tr></table><br>
继续
数据结构部分:
第一题:填空(1.5分*10)
考点无非是基本概念,逻辑结构物理结构,图邻接矩阵的0的个数,完全二叉树叶子结点数,邻接表查找的时间复杂度,拓扑排序,等等。
第二题:判断(1.5分×10)
考查基础知识,书一定得看透了。
第三题:算法设计(ms9分×2)
1. 统计2叉树中叶子节点树
题目背景:一个公司有两个子公司,每个子公司又最多拥有2个子公司,如果一个公司没有子公司,那么这样的公司叫做基层公司,每个基层公司配备一名基层经理,现在设计一个算法来统计公司有多少名基层经理?
2:带头节点的链表的倒置算法
一个班级的学生的成绩按学号从小到大排列,采用带头节点的单链表存储,现要求不新增节点,将学生按学号从大到小排列?
第四题(剩下的分就是了)
1. 用除留余数法和二次探测再散列处理冲突的方法,将题目中的key值序列构造一个harsh表,并计算在等概率的前提下的ASL(平均查找长度)。
2. 堆排序
1)将题中的关键字序列初始化一个堆,写出过程和初时态。
2)写出建立小顶堆的过程
3)写出选出最小的两个元素的过程
3.有向图关键路径的考察
1)画出题中有向图的邻接链表
2)问工程可否完成为什么(拓扑排序)
3)写出题中各个事件和活动的最早开始时间,最晚开始时间,给出完成工程的最短时间,给出关键路径