計算機常見演算法面試/筆試題集

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中的不同的整數。請寫出一個尋找序列中缺失整數的線性-時間演算法。

提示：累加求和