中国科学院计算技术研究所1999年硕士生入学试题数据结构与程序设计参考答案
一.选择题一.3;二.3;三.2,1,7;四.6,2;五.2,6,9; 二.填空题
1.集合,线性结构,树型结构,图结构
2.LOG[m/2]((n 1)/2) 1
3.O(elog2(e)),稀疏
4.2^(k-1),2^k-1,k=[log2(n)] 1或k=[log2(n 1)] 三.问答题
1.如:.即一有向树外加一个有向环所构成的所有有向图都不是一棵有向树.
2.将Kn 1插入数组的第n 1个位置(即作为一树叶插入),然后将其与双亲比较.若是大于等于
其双亲则终止调整,否则将Kn 1与其父亲交换.重复的将Kn 1与新的双亲比较,算法终止于
Kn 1大于等于其双亲或Kn 1本身已上升为根为止. 四.程序输出1,2,3,......100.本题主要考察学生对函数中修改指针的理解 五.
1.略. 2.思想:若已知b[0..i-1]的最长平台的长度为p,且b[i]是下一平台的开始位置,即b[i]!=b[i-1],则从
位置i开始计算下一平台的长度.若p<q,则更新最长平台的长度p.当i=N时,p即为所求: i:=0;p:=0;//初始化
whilei<Ndo{
q:=1;//b[i]构成长度为1的平台
i:=i 1;//改查下一元素
whilei<Nandb[i-1]=b[i]do{
q:=q 1;//当前平台长度加1
i:=i 1
}
ifq>pthenp:=q;
}
3.求树的直径的时间复杂度可为O(n),O(n^2)和O(n^3),若时间为O(n^3)适当扣分 解法一:先调用求所有点对见最短路径算法(每边权数为1)如FLOYD算法,然后对指代矩阵
求最大的COST[i,j]作为直径. 解法二:修改Bfs算法,使之遍历时,记录当前访问结点的深度(离根的边数),用存在度为1的结
点作起点调用Bfs,求出其他非根结点的深度,在各次调用Bps算法中求最大深度,即为树的
直径.时间O(n(n e))=O(n^2 ne)这里O(ne)是一次外部调用Bfs的运行时间,最多调用Bfs次
数(指外部调用)不超过O(n)(存储结构为邻接表时) 解法三:用邻接表作为存储结构
依次删去树叶(度为一的结点),将与树叶相连的结点度数减1.设在第一轮删去原树T的所有
树叶后,所得树为T1;再依次做第二轮删除,即删除所有T1的叶子;为此反复,若最后剩下一个
结点,则树直径应为删除的轮数*2.具体算法如下: m:=0;
fori:=1tondo
if(du(v[i])=1)then{
enqueue(Q,v[i]);//叶子vi入队m:=m 1;//m记录当前一轮叶子数
}
r:==0;//表示删除叶子轮数
whilem>=2do{//当前叶子轮数
j:=0;//j计算新一轮叶子数目
fori:=1tomdo{
dequeue(Q,v);//出队,表示删去叶子v将与v相邻的结点w的度数减1
ifdu(w)=1then{//w是新一轮的叶子
j:=j 1;
enqueue(Q,w);//w入队
}
}
r:=r 1;//轮数加1
m:=j;//新一轮叶子总数
}
ifm=0thenreturn2*r-1//m=0,直径为轮数*2-1
elsereturn2*r;//m=1,直径为轮数*2 NOTE:假定T结点数>1,否则在算法首部判定处理之.
页:
[1]