计算机常见算法面试/笔试题集

1.用最简单的方法判断一个LONG整形的数A是2^n(2的n次方)

若a为2的N次方，则a最高位为1，其他位为0，那么(a-1)正好相反，只有最高位为0，其他位为1，然后做a和(a-1)的 位与就行了，结果为0则a为2的N次方。

return (N-1)&N? FALSE : TRUE;

2.判断单链表是否存在环,判断两个链表是否相交：

3.五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球:

首先假定只要不把球从天平拿下来就还算一次，另外每个桶内的球是一样的：

从1 号和2 号桶各拿一个，放上天平(1 号左，2 号右)，如果平衡，说明这两桶球都是正常的，可以做为砝码。如果不平衡，那么1 号和2 号桶必有一个不正常，而其他3 ，4 ，5 桶是正常的，可以作为砝码。

首先考虑1 号2 号桶不平衡的情况，这时从1 号和3 号桶再各拿一个球，放上天平(1 号右，3 号左)，如果这时平衡了，说明1 号桶是不正常的'，如果还是不平衡，那么2 号桶是不正常的。

如果第一步1 号2 号桶是平衡的，那么也好办，把3 ，4 号桶各拿一个放上天平(3 号左，4 号右)，这时如果还是平衡的，那么5 号桶必然是不正常的。如果不平衡，说明不正常的就在3 ，4 号桶之中。我们再用2 )的方法找出来即可。

4.给两个烧杯，容积分别是m和n升(m!=n)，还有用不完的水，用这两个烧杯能量出什么容积的水?

m, n, m+n, m-n以及线性叠加的组合

5.写出一个算法，对给定的n个数的序列，返回序列中的最大和最小的数。你能设计出一个算法，只需要执行1.5n次比较就能找到序列中最大和最小的数吗?能否再少?

提示：先通过两两比较(比较0.5n次)，区分大小放入“大”，“小”两个数组中。从而最大数在“大”数组中，最小数在“小”数组中(比较0.5n+0.5n次)。

6.给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性-时间算法。

提示：累加求和