总体感觉：题目不难，考察很基础的东西，如C/C++编程，算法等。

题型：
选择题 15题 × 4分 = 60分
填空题 5题 × 8分 = 40分
附加题 20分 + 40分 = 60分

选择题：
C/C++编程基础的一些东西：
如：虚函数与重载函数的概念
指针： int a = 0;
Int *b = &a;
Int **c = &b;
**c = 5;
Print( “%d “, a );
A = 6;
Print( “%d “, **c );
*b = 10;
Print( “%d “, **c );
等。

还有一题：
Int a[3] = { 0, 1, 2 };
Int *p = a[0], *q = a[2];
求 a[q-p];

类的构造函数调用顺序：
例如，求下面代码的输出：
Class A
{
  A(){ cout << “A”; }
}
Class B : public A
{
  B(){ cout << “B”; }
}
Class C
{
C(){ cout << “C”; }
A a;
B b;
}

Void main()
{
  C c;
}

下面代码是否有内存泄漏：
Class A
{
A(){ pa = new int[100]; }
~A() { delete pa; }

Int *pa;
};
Class B : public A
{
B(){ pb = new int[100]; }
~B() { delete pb; }

Int *pb;
}

1.
Void main()
{
A *pa = new A[100];
Delete pa;
}

2.
Void main()
{
A *pa = new B;
Delete pa;
}

关于 IP, TCP, UDP 的一点概念

关于 VC 编译过程中出错信息的具体含义

二叉树的知识

快速排序的东西

线程，进程的关系等

填空题
主要是一个程序，里面有一些空行，要求填空

附加题：
1.有n 个人，从第一个人开始报数，报到 m 的出列，再从下一个开始报数，直到最后一个人为幸运者。 编程实现。

2.在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

对于最后一道题：
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。

我是这样想的：
基本思路：我们假定这个大数组已经经过了排序，也就是找出第n/2大的数~~于是我们可以借鉴选择算法得到这个效果~~而且并不用经过排序~~~

大家可以看看“select algorithm”的内容就知道具体实现了哈~~
平均时间复杂度是O(n)，最差的情况是O(n^2)，空间复杂度O(1)~~不过我们可以进一步的进行优化设计，得到一个最坏情况下也是O(n)的算法（这是可行的哈，已经尝试过了），

p.s.select的原理就是对数组进行partition


[ 此贴被zc1984在2007-04-21 23:31重新编辑 ]

Quote:

引用第2楼disneycheng于2007-04-21 23:23发表的:
顶一个，师兄这么快把差不多整份题搞到了。

呵呵，of course~~~

Quote:

引用第3楼gpstar811于2007-04-21 23:25发表的:


是全国[屏蔽]网络上机的原题！！！

这个题目又叫做“约瑟夫环”~~~

p.s.我的算法大补考成绩还没出来~~等待最后判决中……积累RP~~

利用对手论证法证明中位数问题的比较次数下界

5个数通过6次比较求中位数的方法如下：

5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所
关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在下
面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，*表示一般的
数，o表示下一次即将进行比较的两个数。

第1步，先任取两个数比较，结果为：

*
|
* o o *

第2步，再取另外两个数比较，结果为：

o o
| |
* * *

第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：

  *
/ \
*   o
|
*     o

第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

  *   o           *
/ \ /           / \
o   *           o   o
|             |   |
*             *   *

第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

*   *           *
/ \ / \         /
/   \/   \       /
|   /\   |       /
| / \ |       *
| /   \ |       | \
|/     \|       | \
o     o       |   \
|             o   o
|               |
|               |
*               *

第6步，按照上图比较其中两个标记为o的数，比较结果有两种情况：


*   *       *   *         *           *
\ /       \ /         |           |
x         x         *           *
|         / \         |           |
*       *   *         x           x
|                   |         / \
*                   *         *   *
                    |
                    *

其中的x就是中位数。


事实上，可以证明：对于n个数求中位数，至少需要3(n-1)/2次比较，并且存在一个O(n)次
比较的算法。

下面介绍如何利用对手论证方法来证明中位数问题的比较次数下界。

首先介绍“对手论证（Adversary Argument）”方法。

若用P表示所讨论的问题，I表示问题的输入，A表示求解问题P的基于比较运算的算法T(A,
I)表示对于输入I算法A的计算时间复杂性，那么，函数
    U(n)=min{max{T(A,I)}, for each I}, for each A，
是问题P当输入的大小为n时在最坏情况下的最好下界。它是问题所固有的。

问题P的这个最好下界通常很难按其定义计算得到，因为对于一个具体的A，要得到
    max{T(A,I)}, for each I
就是一件很难的事，更何况对于一切的A。因此，人们往往不去精确地求U(n)，而是退而求
其次，即找一个f(n)，它不大于U(n)但尽量地接近于U(n)，使f(n)成为问题P的一个好下界
。

对手论证方法是找f(n)的一种有效方法。它的基本思想是对每一个A，构造一个输入特殊的
输入I'，使T(A,I')尽量地大，然后在所有A的集合上，求T(A,I')的尽量好的下界作为f(n)
。这种方法通过
  f(n) <= min{T(A,I')}, for each A <= min{max{T(A,I)}, for each I}, for each A
= U(n)
来保证f(n)是问题P的一个下界，又通过使T(A,I')尽量大来保证f(n)是一个好的下界。

对手论证方法的关键在于有一套对一切A都适用的构造符合要求的I'的策略，即对手策略。
这种策略，逐步地构造出一个输入I'，便算法A为得到与几相应的结果，要做尽量多次的比
较和判断，从而使T(A,I')尽量大。需要注意的是，一方面对手策略须具有一致性，即不能
前后矛盾，以保证I'的存在性；另一方面对手策略还须对一切A都适用，因为我们需要在一
切A组成的集合上求T(A,I')的下界。至于策略的具体内容将因问题而异。甚至同一个问题可
能有多种策略，要得到好的下界，需要有好的策略。

中位数问题的原型是：任给n个数，要求找出它们的中位数，即第[(n+1)/2]大的数。

下面我们用对手论证方法来证明中位数问题比较次数的下界为3(n-1)/2次。

不失一般性，这里假设所给的n个数互不相同，且n为奇数。


在这个求中位数问题中，要确定中位数，算法必须确定其他n-1个数相对于中位
数M的关系。我们称n个数中大于中位数的数为上部数，小于中位数的数为下部数。
显然，算法最终从n个数中分出(n-1)/2个上部数和(n-1)/2个下部数。如果算法
结束后，x最终被确定为上部数，则在算法执行过程中，要么x直接与中位数M比
较过且结果为x > M，要么x和另一个上部数y比较过且x > y；同理，如果x最终
被确定为下部数，则在算法执行过程中，要么x直接与中位数M比较过且结果为x
< M，要么x和某个下部数y比较过，x < y。因此，我们可以做如下定义：

定义：设M为n个数的中位数，设x,y为任意两个元素，如果x > y且y >= M，或者
x < y 且 y <= M，则x和y之间的比较称为“x的关键性比较”。

x的关键性比较将确定x和中位数M之间的关系。注意，上述定义并没有要求算法
在进行关键性比较的时候知道y和M的关系。

不妨设N1(A, I)为算法A对于输入I所需进行的关键性比较的次数。为了确定输入
中其他n-1个元素和中位数的关系，这n-1个元素中的每个元素至少要进行一次关
键性比较，所以有

N1(A,I) >= n - 1   ...... (1)

设N2(A, I)为算法A对于输入I所需进行的非关键性比较的次数，设T(A,I)为算法
A对于输入I所需进行的比较的总次数，则有

T(A, I) = N1(A, I) + N2(A, I) ..... (2)

下面我们将利用对手论证法构造一组输入I，使得对于该输入，任何一个算法A都
至少要进行(n-1)/2次非关键比较。

首先对手B任取一个数值M作为中位数的值(但并没有确定中位数到底为输入中的
哪个元素)。当算法A在执行过程中第一次比较某个元素时，对手B将给该元素赋
值。赋值的原则是，尽量让算法A所做的比较为非关键比较。在任一时刻，每个
元素处于下述三个状态之一：

L 表示该元素已经被赋值，且其值大于M
S 表示该元素已经被赋值，且其值小于M
N 表示该元素尚未被赋值

对手B的具体策略如下表所示：

A所比较的两个元素的状       对手B的策略
N, N           给其中一个元素赋小于M的值，另一个赋大于M的值
L, N 或 N, L     给处于状态N的元素赋一个小于M的值
S, N 或 N, S     给处于状态N的元素赋一个大于M的值

在算法A的执行过程中，对手B将按照上表，根据A每一步所比较的两个元素的状
态给尚未赋值的元素赋值。如果在某一步的时候处于S状态(或L状态)的元素已经
达到(n-1)/2个，则忽略上表定义的策略，而给处于N状态的元素赋一个大于(或
小于) M的值；如果在某步的时候只剩下最后一个元素尚未赋值，则给该元素赋
值M。这样就可以保证在算法A结束的时候，处于S状态和L状态的元素分别为
(n-1)/2个，且中位数的值一定等于M。

如果在算法A的执行过程中所做的某次比较牵涉到状态为N的元素，且这时状态为
S或L的元素都没有达到(n-1)/2个，则对手B总可以令该次比较成为一次非关键比
较，且该次比较最多能产生一个S状态的元素和一个L状态的元素。又因为算法A
结束后，S状态的元素应该恰好有(n-1)/2个，所以这样的非关键性比较至少要进
行(n-1)/2次，即

N2(A, I) >= (n - 1) / 2 ..... (3)

根据(1)(2)(3)可知

T(A, I) >= (n - 1) + (n - 1) / 2 = 3*(n - 1) / 2

即无论用什么算法求中位数，在最坏情况下至少要进行3(n-1)/2次比较。

Quote:

引用第7楼独飞の孤心于2007-04-22 09:25发表的:


二分查找？感觉以前学过的查找算法都用不上

我觉得应该从文件的角度出发，而且因为没有时间限制，意思就是说要把文件分段处理。。。

二分查找是建立在已经排序的基础上的哈~~
现在的情况是乱序~
而且内存小于数据源~~

目前我就只能想到Select算法和Select算法改进型~~~
能够达到时间复杂度O(n)~~~空间复杂度O(1)~~~

貌似有种感觉，应该存在时间复杂度为O(log(n))的方法~~

Quote:

引用第10楼liusum于2007-04-22 11:17发表的:
内存不够可以释放嘛~
先排序
再找中位数啊。
东西一定要放在内存吗？

你仔细想一下就知道为什么了~~~
最直接的方法就是用代码实现，编码的过程中你就会发现你的想法中的问题了~~

Quote:

引用第15楼lyly于2007-04-22 15:02发表的:
我当时写了个算法是o(n)的最坏情况时o(3n)的空间复杂度最坏情况是开个2^21大的数组
感觉楼主的方法不太可行，首先10G个数是不可能存的下来的，
o(1)的空间复杂度也不可以，何况楼主的算法最坏情况时o(n^2)估计几天也算不出来。
其次因该至少要对数据遍历一次的，除非用概率算法求出估计中位数，否则o(logn)的算法是
不存在的。。。。。

通过对select算法的改进，已经得到了时间复杂度最坏情况O(n)的了~~空间复杂度O(1)~~~
要不要我放代码？

Quote:

引用第20楼lyly于2007-04-22 15:44发表的:
楼主的算法没有看懂，不过如果是o(1)的空间复杂度，且是o(n)的时间复杂度
我就挺佩服的了，算法导论上也有o(n)的算法，不过当时没想到那个算法，只好自己想了，
不过感觉自己的方法应该没有问题，最坏只要遍历三次，不用交换数据。
不过o(n)的时间复杂度常系数必须要小，因为计算机每秒只能处理10^8次对于10G的数据
执行一边就需要1分钟所以有些o(n)的算法也不可取哈

就是算法导论上面的那个select算法啊~~~只不过使用改进后的select算法可以把最差的效率提升到O(n)而已~~

现在的处理器是10亿/秒级别的~~~例如我的机器Athlon64 3200+~~对应3200MHz的Pentium4的水平~~
（存在假设：一个时钟周期执行一条简单指令，利用流水线技术等优化措施~）

1分钟处理10G数据，瓶颈不在CPU，而在于硬盘~~你看一下数据传输速度就知道了~~现在的单个硬盘也就60MB/s~
只有使用SAN或者RAID技术~~


[ 此贴被zc1984在2007-04-22 15:52重新编辑 ]

Quote:

引用第22楼lyly于2007-04-22 15:56发表的:

对现在计算机技术不是很清楚哈，反正我们做acm题目的时候，如果达到10^8的次数，一秒的时限就会超时(不牵扯到文件读取速度的问题哈).

蝈蝈不错哈！！
但是关注现实的实现可能更具有意义~~毕竟ACM里面的东西都来源于实际问题，同样的，也会最终回到实际问题中~

p.s.有没有蝈蝈使用OpenMP之类的东西写并行算法参加ACM的啊？
p.s.2 如果我提交病毒源代码上去，ACM的服务器会怎么样啊？

Quote:

引用第24楼lyly于2007-04-22 16:02发表的:

没有用并行方法写的，
如果你提交病毒上去，编译器会识别不会予以处理，并且如果是比赛的时候你就挂了，取消比赛资格

编译器识别？貌似不可能~~~
有杀毒软件倒是可能，但是这可以预防未知病毒吗？怀疑~~

并行是未来的趋势，不知道什么时候ACM跟上这个趋势~~
现在双内核都不新鲜了，都开始叫卖4内核了~~
IBM Cell都已经是9核心了~~

而且ACM的题目多试基于随机存储的体系的，如果是磁带机？网络流？How？

算法啊~~很有趣的东西~~~被朱清新教成那样~~

Quote:

引用第28楼lyly于2007-04-22 16:09发表的:
以后还是扎实下基本算法和数据结构感觉公司就只考这东西，，，
本感觉自己的项目经验有些优势，但是关于软件开发和vc一点都没涉及。。。

这个就要看你的人生规划了~~
有项目经验是很好的~~
如果你真的喜欢算法和数据结构，那么就去学习数学吧，这才是王道~~

p.s.如果我有钱+有时间，那么我的精力都会花在数学和哲学上~~

Quote:

引用第29楼lyly于2007-04-22 16:12发表的:

编译器限制了你可以使用的库函数，以及可以调用的资源，并在超过规定时间后强行停止运行。。。。所以想用病毒攻击，是比较麻烦的事哈

可以不用库函数~~~
直接嵌入汇编代码~~~

Quote:

引用第43楼kangtalc于2007-04-22 18:29发表的:
不论找第几个大的数都是线性时间的 而且空间也能达到要求 算法设计书里就有 很详细的

恩~~就是~~
其实就是寻找第K大的数的问题~~~

Quote:

引用第46楼jiju84于2007-04-22 19:10发表的:



你可以找lyly

.......

都是算法强人~~~
顶~~~
偶算法大补考的成绩怎么还不出来~~泪奔~~~~

p.s.召唤研究并行算法的蝈蝈一起研究东东~~~~