免费提供各学校计算机考研试题 (4月21日更新)
我自己找的，绝对真实。！ 不信看大家的回复就可以了.
http://master.csai.cn
北京大学2006年数据结构试题
一、 填空
序列：3，5，9，18，37，66，98，102，问用二分查找5和66分别要查几次。（序列中所用数字与原题不同）
二、 简答
1、 画出用带压缩的Union-Find 算法查结点B311后的形状。下图为一个有两颗树的森林：左树只有一个A结点；Bmn为Bm的第n个孩子。
A B
B1 B2 B3 B4
B21 B31
B311 B312
B3111
2、 在（a,b,c,d）中加括号，问可以表示出多少个不同的广义表。要求不能有多余括号。
三、 辩析
题目中给出一个图，是个有两颗树的森林。首先要写出Print算法作用于所给森林后的生成序列。然后问这个算法是否能遍历整个森林，如果可以的话，就什么都不干吧， 如果不可以，在这个算法的基础上给出一个新的算法，使之可以遍历整个森林。
Print(TreeNode* tr){
if(rt= =NULL)
return;
visit(rt);
for (node = rt.leftmostchild();node!= NULL;node=node->rightsibling())
Print(node);
}
四、 算法填空
Floyd算法
For(i=0;i<G.VNum();i++)
For (Ee=G.FirstE(v);G.IsE(e);e=NextE(e)){
空缺一
G[G.ToV(e)].pre = i;
}
If (D[v].length = = -∞||D[v][j]= =-∞)
空缺二
Else if (D[j].lenth= =-∞)
空缺三
Else if (空缺四)
空缺五
五、 算法设计
设A、B是长为n的数表，已经按照非降顺序排好。如果将这2n个数全体排序，算于第n个位置的数称为中位数。设计一个最坏情况下时间复杂度为O(logn)的算法求A和B的中位数。
第一问：描述算法的设计思想。
第二问：证明算法的时间复杂度。
[此贴子已经被作者于2006-4-21 8:59:40编辑过]
