精华3
威望-170
K币-336 元
注册时间2009-4-26
在线时间7 小时
最后登录2009-7-3
Beggar
- 精华
- 3
- 威望
- -170
- K币
- -336 元
- 注册时间
- 2009-4-26
|
北京大学2006年硕士研究生入学考试计算机软件基础试卷
Part1:数据结构,80分
一:填空序列:
3,5,9,18,37,66, 98,102,问用二分查找找5和6分别要查几次。(序列中所用数字与原题不符)只记住这一道。
二:简答
1。画出用带压缩的Union-Find算法查结点B311后的形状。
下图为一个有两颗树的森林:左树只有一个A结点;Bmn为Bm的第n个孩子。A B B1 B2 B3 B4 B21 B31 B311 B312 B31112。在(a, b, c, d)中加括号,问可以表示出多少个不同的广义表。要求不能有多余括号。((a), (b), (c), (d))内层的四对儿括号为多余括号。
三:辩析题目中给出了一个图,是个有两颗树的森林。首先要写出Print算法作用于所给森林后的生成序列。然后问这个算法是否能遍历整个森林,如果可以的话,就什么都不干吧,好像是;(记不清了,-_-)如果不可以,在这个算法的基础上给出一个新的算法,使之可以遍历整个森林。Print(TreeNode* rt) { if (rt == NULL) return; visit(rt); for (node = rt.leftmostchild(); node != NULL; node = node->rightsibling()) Print(node);}
四:算法填空(15分,5个空,每空3分):Floyd算法。for (i = 0; i < G.VNum(); i++) for (E e = G.FisrtE(v); G.IsE(e); e = NextE(e)) { 空缺一 G[G.ToV(e)].pre = i; }if(D[v].length==-∞ || D[v][j]==-∞) 空缺二else if (D[j].length == -∞) 空缺三else if (空缺四) 空缺五一些片段,只记得这么多了,而且不保证对,呵呵。
五:算法设计(好像是10分):设A,B是长为n的数表,已经按照非降顺序排好。如果将这2n个数全体排序,处于第n个位置的数称为中位数。设计一个最坏情况下时间复杂度为O(logn)的算法求A和B的中位数。第一问:描述算法的设计思想。第二问:证明算法的时间复杂度。注:这是本学期数据结构课的一道作业题(hw9.1)选自《学习指导》习题7.12 |
|